2.8k views
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________

edited | 2.8k views
0
..

Let us denote number of $n-$pennants by $f(n)$, so $f(10)$ is number of ${10}$-pennants.

A ${10}-$pennant means sum of numbers in sequence is ${10}$. If we look at any $9-$pennant, we can make it a ${10}-$pennant by adding $1$ into that sequence. Similarly, we can make any $8-$pennant a ${10}-$pennant by adding $2$ into that sequence.

So all ${10}-$pennants can be formed by $8-$pennants and $9-$pennants, and no other pennant (since we can add only $1$ or $2$ into a sequence)

So $f(10) = f(9) + f(8)$

This is in fact a Fibonacci sequence, in which $f(1) = 1, f(2) = 2$, so this sequence becomes

$1, 2, 3, 5, 8, 13, 21, 34, 55, 89\ldots$

So $f(10) = 89.$
by Boss (11.2k points)
edited by
+3
Any reason why this turn to fibonacci sequence or its just coincidence/observation ...finding all possible permutation and then arrange it also gave same result but it will be very difficult if they ask F(50) so anyone can provide why this behavior of fibonnacci no occur it will be a great help ...
+1

Best solution.Thanks :)

0
yes its sum of 2 previous but its base condition is not same fib series ,in fib series f(0)=0 f(1)=1 , f(2)= 1,but here f(1) = 1 , f(2)= 2 .. so it gives result of fib by shifting 1 term rt ?
0
best explanation @happy mittal
0
I still don't understand how f(10) = f(9) + f(8). What am I missing here?
Numbers could be any one of

$\{(1,1,1,1,1,1,1,1,1,1),(1,1,1,1,1,1,1,1,2),(1,1,1,1,1,1,2,2),$
$(1,1,1,1,2,2,2),(1,1,2,2,2,2),(2,2,2,2,2)\}$

So, the number of ${10}$ pennants $=1+ \frac{9!}{8!} + \frac{8!}{6!2!} +\frac{7!}{4!3!} + \frac{6!}{2!4!} +1 =89.$
by Veteran (113k points)
edited
+5
Nice elegant
+1
thnks shrestha for nice soln:)

For calculating no of 4 - pennants , we have to take cases :

Case 1 : We have 2 2's :

So in this case no of ways the 2 2's can be permuted = 2! / 2! = 1

Case 2 : We have 4 1's :

So in this case no of ways the 4 1's can be permuted = 4! / 4! = 1

Case 2 : We have 2 1's  and 1  2:

So here we have 3 objects with 1 repetition i.e. corresponding to no of 1's which is 2 in this case.

No of ways if have 2 1's and 1 2 to make sum = 4   :   3! / (2)!   = 3

With this all possibilities are exhausted to get the sum of 4 using 1 and 2 only.

Hence total no of 4 pennants = 1 + 1 + 3  = 5

Proceeding in the similar manner , we get no of 5 pennants = 8

no of 6 pennants = 13

hence following the fibonacci series.

Hence no of  7 pennants  =   21

no of  8 pennants  =   34

no of  9 pennants  =   55

Finally no of 10 pennants  = 89

Hence no of 10 pennants = 89.

In such questions , which seem to be of non trivial nature we should try to form the solution of a smaller problem and construct the solution of larger problem using the smaller problem .

by Veteran (101k points)
edited
This is quite straight forward if we think of the set elements as combination of 1s and 2s where elements are repeated or are similar.

Number of ways of arranging n elements when some number us repeated q1 time,  another q2 time... and so on is n!/q1! *q2!

For this problem,  in any set element we need combination of 1s and 2s. If we find all possible combinations we have our answer...

First,  we can have two 1s and Four 2s. Number of different arrangements = 6!/(2!*4!)  = 15

Then Four 1s and Three 2s. Number of different arrangements = 7!/(4!*3!) = 35

Then,  Six 1s and Two 2s. Number of different arrangements = 8!/(6!*2!) = 28

Then we have,  Eight 1s and One 2. Number of different arrangements = 9!/8! = 9

Finally,  we have 1 possible combination of ten 1s and 1 possible combination of five 2s.

Total different combinations = number of ten pennants = 15 + 35 + 28 + 9 + 1 + 1 = 89.
by (271 points)
1-pennant {(1)} - #1

2-pennant {(1,1),(2)} - #2

3-pennant {(1,1,1),(1,2),(2,1)} - #3

4-pennant {(1,1,1,1),(2,2),(1,1,2),(1,2,1),(2,1,1)} - #5

5-pennant {(1,1,1,1,1),(2,1,1,1),(1,2,1,1),(1,1,2,1),
(1,1,1,2),(2,2,1),(2,1,2),(1,2,2)} - #8

If one observe carefully they are the terms(part of) a Fibonacci series. (0,1,1,2,3,5,8,13 ....). Hence the # of 10-pennant is the 12th term of the series ie. 89
by Loyal (9.4k points)
0
Yes! it is fibonacci series but the fibonacci sequence is 1,2,3,5,8,13,21,34,55,89,144,233,377,,,,,,,

because f(1)=1 and f(2)=2 .So # 10 pennants = f(10) = 89
If the pennant has all 1s, then the no. of such pennants = 1

If the pennant has a single 2 and remaining 1s, then it would be of the form x2y, and no. of such pennants will be no. of solutions of the equation x+y = 8 which is $\binom{8+2-1}{8} = \binom{9}{8} = 9$

If the pennant has two 2 and remaining 1s, then it would be of the form x2y2z, and no. of such pennants will be no. of solutions of the equation x+y+z = 6 which is $\binom{6+3-1}{6} = \binom{8}{6} = 28$

If the pennant has three 2 and remaining 1s, then it would be of the form w2x2y2z, and no. of such pennants will be no. of solutions of the equation w+x+y+z = 4 which is $\binom{4+4-1}{4} = \binom{7}{4} = 35$

If the pennant has four 2 and a single 1, then it would be of the form v2w2x2y2z, and no. of such pennants will be no. of solutions of the equation v+w+x+y+z = 2 which is $\binom{2+5-1}{2} = \binom{6}{2} = 15$

If the pennant has all 2s, then no. of such pennants = 1.

Total = 1+9+28+35+15+1 = 89
by Junior (747 points)
0
appriciatable work brother :)
+1 vote

No of ways 10- pennant can be formed is:

1. 5(2's), 0(1's)=1 way

2. 4(2's), 2(1's)=6C4=15

3. 3(2's), 4(1's)=7C3=35

4. 2(2's), 6(1's)=8C2=28

5. 1(2's), 8(1's)=9C1= 9

6. 0(2's), 10(1's)=1 way

Total = 1+15+35+28+9+1= 89

by Active (2.2k points)
+1 vote

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

by (173 points)

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?

by Active (3.1k points)
+8

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.

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$
by Loyal (6.1k points)

1
2