GATE CSE 2014 Set 1 | Question: 49

Question

A pennant is a sequence of numbers, each number being $1$ or $2$. An $n-$pennant is a sequence of numbers with sum equal to $n$. For example, $(1,1,2)$ is a $4-$pennant. The set of all possible $1-$pennants is ${(1)}$, the set of all possible $2-$pennants is ${(2), (1,1)}$ and the set of all $3-$pennants is ${(2,1), (1,1,1), (1,2)}$. Note that the pennant $(1,2)$ is not the same as the pennant $(2,1)$. The number of $10-$pennants is________

Comments

..

---

$\color{red}{\text{Detailed Video Solution of this GATE question}}$(Click Below):

https://youtu.be/K8fQPHG3JII (Multiple Ways to Solve)

$\color{red}{\text{Complete Recurrence Relation Playlist}}$(Click Below):

Complete Recurrence Relations Playlist 

Answer 1

Every penannant consists of  certain number of 1s and 2s only such that their sum is equal to 10.

Let number of 2s in a penant = x, Number of 1s in a penant = y.
=> 2x+y = 10
Hence different values possible for (x,y) is = { (0,10), (1,8), (2,6), (3,4), (4,2), (5,0) }
Since (1,2) is a different pennant than (2,1) for 3-pennant hence we need to consider all the combinations for the 10-pennant too.

Therefore,
Number of pennants possible with x,y values (0,10) = (0+10)! / (0!*10!) = 1
similarly,
with x,y values (1,8) = (1+8)! / (1!*8!) = 9
with x,y values (2,6) = (2+6)! / (2!*6!) = 28
with x,y values (3,4) = (3+4)! / (3!*4!) = 35
with x,y values (4,2) = (4+2)! / (4!*2!) = 15
with x,y values (5,0) = (5+0)! / (5!*0!) = 1

Summing them up to get total pennants we get 89

 

 

 

Answer 2

For 10 pennants, the sequence of number can be ---

(assume n = 10.)

1. n 1s → (1 1 1 1 1 1 1 1 1 1 ) 
2. (n – 2) 1 and one 2 → (1 1 1 1 1 1 1 1 2)
3. (n – 4) 1 and two 2 → (1 1 1 1 1 1 2 2)
4. (n – 6) 1 and three 2 → (1 1 1 1 2 2 2)
5. (n – 8) 1 and four 2 → (1 1 2 2 2 2)
6. (n – 10) 1 and five 2 → (2 2 2 2 2)

No of permutations for above sequences–

1. 1
2. (n – 1)! / ((n – 2 )! 1!) = (n-1)
3. (n – 2)! / ((n – 4)! 1!) = (n-2)(n – 3) / 2!
4. ((n- 3)(n – 4)( n – 5) )/ 3!
5.  ((n – 4)( n – 5)(n- 6)(n- 7) )/ 4!
6. (( n – 5)(n- 6)(n- 7)( n – 8)(n – 9) )/ 5! 

therefore for no. of 10 pennant sequence = $1+ 9 + (8 * 7)/ 2! + (7* 6*5)/3! + (6*5*4*3)/ 4! + 1 = 89.$

Comments

The best answer here!

---

Thanks @Abhrajyoti00

Answer 3

i dunno if they actually exist or were framed for gate exam only, but
the order of elements matters in these sets called Pennants.

so according to what OSA thinks, this should be:
 

1 1 1 1 1 1 1 1 1 1
1 * 10

_1_1_1_1_1_1_1_1_
1*8 + 2 *1 (insert 2 in any of the 9 places)

_1_1_1_1_1_1_
1*6 + 2 * 2(twice, insert into any of the 7 places)

_1_1_1_1_
1*4 + 2 * 3(thrice, insert into any of the 5 places)
 

_1_1_
1*2 + 2 * 4(thrice and once more , insert into any of the 3 places)

2 2 2 2 2

2*5


this gives my answer as 1 + 9 + 7*7 + 5*5*5 + 3*3*3*3 + 1
= 11 +49 + 125 + 81

=60 + 125 + 81

=141 + 125

=266


why am i wrong?

Comments

1 1 1 1 1 1 1 1 1 1
1 * 10 - 1 way

_1_1_1_1_1_1_1_1_
1*8 + 2 *1 (insert 2 in any of the 9 places) - 9 ways

_1_1_1_1_1_1_
1*6 + 2 * 2(twice, insert into any of the 7 places) - (6 + 2)!/(6!2!) = 28 ways

_1_1_1_1_
1*4 + 2 * 3(thrice, insert into any of the 5 places) - (4+3)!/(4!3!) = 35 ways 
 

_1_1_
1*2 + 2 * 4(thrice and once more , insert into any of the 3 places) - (2+4)!/(2!4!) = 15 ways

2 2 2 2 2

2*5 - 1 way

So, totally 1 + 9 + 28 + 35 + 15 + 1 = 89.

Answer 4

Note that number is either $1\ or\ 2$, therefore Generating function for choosing either 1 or 2, $f(x)$ is $(x+x^{2})$. Since this activity can be carried out $n$ times,

$\implies G(x) =  \sum_{i=0}^{n}(x+x^2)^n$

$\implies G(x)= \frac{1}{1-x-x^2}$ which is nothing but a generating function of Fibonacchi series with $a_0 = 1$

Therefore $a_n = a_{n-1} + a_{n-2} , a_0 = 1, a_1=2$