I was asked by PM to comment.A mocktail is to be prepared from 3 kinds of whiskies, 4 kinds of soda and 5 kinds of fruit juices. How many mocktails can be made that include at least 1 kind of each ingredient?
A. 135
B. 235
C. 325
D. 3255
E. 5235
Its very nice that we have a formula for choosing at least 1 from nGMATGuruNY wrote: Given n choices, the number of ways to select at least 1 of the n choices = 2^n - 1.
For example, given 3 people, the number of ways to choose at least 1 of the 3 people = 2^3 - 1 = 8-1 = 7.
Here all the ways to choose at least 1 of the 3 people:
3C1 = 3
3C2 = 3
3C3 = 1
3+3+1 = 7. Same answer as above.
1 thing can be selected in nC1 ways, 2 things can be selected in nC2 ways.....n things can be selected in nCn ways.Its very nice that we have a formula for choosing at least 1 from n
Can we proof
How you did this i m not able to understand.Rahul@gurome wrote:1 thing can be selected in nC1 ways, 2 things can be selected in nC2 ways.....n things can be selected in nCn ways.Its very nice that we have a formula for choosing at least 1 from n
Can we proof
So the number of ways of selecting at least 1 thing out of n things is nC1 + nC2 +...+nCn.
Now the binomial expansion of (1+x)^n = 1+nC1*x + nC2*x^2 + ......+nCn*x^n.
Replace x by 1 on both sides of the equation.
So we get (1 + 1)^n = 1+nC1*1 + nC2*1^2 + ......+nCn*1^n.
Or 2^n = 1+nC1*1 + nC2*1^2 + ......+nCn*1^n = 1+nC1 + nC2 +....+nCn.
So 2^n - 1 = nC1 + nC2 +...+nCn.
Hence the number of ways of selecting at least 1 thing out of n things is 2^n - 1.
The Bold part is a Binomial Expansion, which describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the power (x + y)^n into a sum involving terms of the form a(x^b)(y^c), where the coefficient of each term is a positive integer, and the sum of the exponents of x and y in each term is n.goyalsau wrote:How you did this i m not able to understand.Rahul@gurome wrote: Now the binomial expansion of (1+x)^n = 1+nC1*x + nC2*x^2 + ......+nCn*x^n.
Thanks Buddy i asked for the Proof Because Its very Hard for me to remember the Formula , at times when I saw the same problem again I can always recall the basic reasoning behind the formula so its easy for me to recall formulas...shovan85 wrote:As per the concept this is what I understand:
Two ppl say A and B:
Total possible selection in 2^2 = 4 ways
This 4 ways can be A, B, AB or BA.
At least one person is selected = 2^2 - 1 = 3 ways
This 3 ways can be either A, AB,BA or B, AB, BA. (See in first set A is the at least person to selected and in second B s the at least person to selected )
The Bold part is a Binomial Expansion, which describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the power (x + y)^n into a sum involving terms of the form a(x^b)(y^c), where the coefficient of each term is a positive integer, and the sum of the exponents of x and y in each term is n.goyalsau wrote:How you did this i m not able to understand.Rahul@gurome wrote: Now the binomial expansion of (1+x)^n = 1+nC1*x + nC2*x^2 + ......+nCn*x^n.
The general formula is:
(1+x)^n = 1+nC1*x + nC2*x^2 + ......+nCn*x^n.
For more info: https://en.wikipedia.org/wiki/Binomial_theorem
So what we need to prove by applying this? We need to show 2^n - 1 = nC1 + nC2 + .... +nCn
2^n
= (1 + 1) ^ n
Apply Binomial Expansion (See x = 1)
1 + nC1 * 1 + nC2 * 1^2 + .... + nCn * 1^n
Thus, 2^n = 1 + nC1 * 1 + nC2 * 1^2 + .... + nCn * 1^n
=> 2^n - 1 = nC1 * 1 + nC2 * 1^2 + .... + nCn * 1^n
=> 2^n - 1 = nC1 + nC2 + .... +nCn.
If you have any doubt about Binomial Expansion then you can refer the above link. I personally feel when asked with at least one is used the remember to use the formula rather thinking about the proof.
