Permutation

Question

Given a integer N greater than zero.

How many sequences of 1's and 2's are there such that sum of the numbers in the sequence = N ?

(not necessary that every sequence must contain both 1 and 2 )

example :

for N = 2 ; 11,2 => ans = 2 sequences of 1's and 2's

for N = 3 ; 11,12,21 => ans = 3 sequences of 1's and 2's

Answer 1

Let T(n) be the number of possible sequences of 1's and 2's having sum 'n',

Now we will divide these sequences into 2 cases: Sequences starting with 1 and starting with 2.

if a sequence of 1's and 2's having sum 'n' starts with 1 then, our problem reduces to finding the sequences of 1's and 2's with sum n-1, which is T(n-1).

similarly, if a sequence starts with 2, our problem reduces to T(n-2).

Hence T(n)= T(n-1) + T(n-2), where T(1)=1, T(2)=2.

Answer 2

It is (N+1)th fibonacci number.

Observe the pattern: http://ideone.com/QLb1CZ

Comments

thanks this can be solved by dynamic as well as generating function or matrix exponentiation. similar to domino tiling

---

Yes, the recurrence relation is $F(0) = 1$, $F(1) = 1$ and $F(n) = F(n-1) + F(n-2)$, $\forall$ $n$ $\geq$ $2$.

---

@Air1. Hats off bro for you thought about the recurrance :)

---

The chapter on generating function from concrete mathematics, well described for this kind of problem.