The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+28 votes
2.1k 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________
asked in Combinatory by Veteran (111k points)
edited by | 2.1k views

10 Answers

+61 votes
Best answer
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.$
answered by Boss (11.3k points)
edited by
+2
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
+54 votes
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.$
answered by Veteran (103k points)
edited by
+3
Nice elegant
+1
thnks shrestha for nice soln:)
+7 votes

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 .

answered by Veteran (99.7k points)
edited by
+3 votes
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.
answered by (193 points)
+2 votes
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
answered by Loyal (8.7k 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
+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

answered by Active (1.6k points)
+1 vote
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
answered by Junior (607 points)
0 votes

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?

answered by Active (3.3k 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.

0 votes
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$
answered by Loyal (6.3k points)
0 votes

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

 

 


 

answered by (115 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

43,942 questions
49,497 answers
162,337 comments
65,748 users