# 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 = [*3 for _ in range(n)]
a = 1
a = 1
a = 1
summ = 3
for i in range(1, n):
a[i] = summ - a[i-1]
a[i] = summ
a[i] = 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.

Scroll to Top