The Gateway to Computer Science Excellence
+36 votes
3k 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________
in Combinatory by Veteran (104k points)
edited by | 3k views
0
..

11 Answers

+78 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.$
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?
0

yes me too @commenter commenter

Did you understand this?

0

yes me too @commenter commenter

Did you understand this?

can you please explain this to me

+81 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.$
by Veteran (117k points)
edited by
+5
Nice elegant
+1
thnks shrestha for nice soln:)
0

@srestha mam

can U tell me why this approach is going wrong??

1 + 10C2 + 10C4 + 10C6 + 10C8 + 1

1st there is 10 1's - (1 1 1 1 1 1 1 1 1 1)

then we can chose any two 1's to make 2 like - (2 1 1 1 1 1 1 1 1) or (1 1 1 1 1 1 1 1 2) ........

then we can choose 4 1's from 10 1's to make two 2, like - (2 2 1 1 1 1 1 1)..........

like this so on choose 6 , choose 8 ,   choose 10

If u get my approach then please tell me why this technique is not working, where it's going wrong???

Thanks in advance

0

@srestha mam

can U tell me why this approach is going wrong??

1 + 10C2 + 10C4 + 10C6 + 10C8 + 1

1st there is 10 1's - (1 1 1 1 1 1 1 1 1 1)

then we can chose any two 1's to make 2 like - (2 1 1 1 1 1 1 1 1) or (1 1 1 1 1 1 1 1 2) ........

then we can choose 4 1's from 10 1's to make two 2, like - (2 2 1 1 1 1 1 1)..........

like this so on choose 6 , choose 8 ,   choose 10

If u get my approach then please tell me why this technique is not working, where it's going wrong???

Thanks in advance

0
In your pattern it will be $1+\binom{9}{1}+\binom{8}{2}+\binom{7}{3}+\binom{6}{4}+\binom{5}{5}$

because, when we r including one $2$, same time we are removing two $1's$
0

 

because, when we r including one 2, same time we are removing two 1′s

but 10C2 also including one 2 by removing two 2's, isn't it???

9C1 is like - 1st we remove one 1 & then from remaining 9 we're choosing one 1 & finally make those two 1's into a 2. 

+1

No, thinking like this might be easy.

Say , u have bought $10$ same type mobile phone from a company.

Now, u like a  iPhone , which cost $2$ mobile of previously purchased.

So, u gave previously purchased $2$ phone, to get one new iPhone.

Now, compare mobile phone as  '1'

and iPhone as '2'

So, when removing 2 phones and adding 1 phone, total phone will be $\left ( 10-2+1 \right )=9$ phones total

Now arrange among them in $\frac{9!}{8!\times 1!}$ ways.$=\binom{9}{1}$ ways

 

+8 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 .

by Veteran (101k points)
edited by
+4 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.
by (295 points)
+3 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
by Loyal (9.6k 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
+3 votes
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.3k 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 (209 points)

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
50,650 questions
56,242 answers
194,289 comments
95,941 users