Count permutation with duplicates and restriction

It is clear that:
-valid sequence of length K ending with 1 might be composed
adding 1 to any valid sequence of length K-1

-valid sequence of length K ending with 2 might be composed
adding 2 to any valid sequence of length K-1

-valid sequence of length K ending with 0 might be composed
adding 0 to valid sequences of length K-1 ending with 0 or 2

So simple Python program

def valid123(n):
    a = [[0]*3 for _ in range(n)]
    a[0][0] = 1
    a[0][1] = 1
    a[0][2] = 1
    summ = 3
    for i in range(1, n):
        a[i][0] = summ - a[i-1][1]
        a[i][1] = summ
        a[i][2] = summ
        summ = sum(a[i])
    return summ

for i in range(1,10):
    print(i, valid123(i))

gives

1 3
2 8
3 21
4 55
5 144
6 377
7 987
8 2584
9 6765

Corresponding OEIS sequence has simple recurrent representation a(n) = 3*a(n-1) - a(n-2) – subset of Fibonacci, and some closed formula does exist:

a(n) = (ap^n - am^n)/(ap-am), with ap := (3+sqrt(5))/2, am := (3-sqrt(5))/2

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top