GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
139 views
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
asked in Combinatory by Veteran (51.5k points)  
retagged by | 139 views

1 Answer

+3 votes
Best answer

It is (N+1)th fibonacci number.

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

answered by Loyal (3.3k points)  
selected by
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.

Related questions



Top Users Sep 2017
  1. Habibkhan

    7142 Points

  2. Warrior

    2640 Points

  3. Arjun

    2480 Points

  4. rishu_darkshadow

    2466 Points

  5. A_i_$_h

    2214 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,133 questions
33,705 answers
79,886 comments
31,105 users