Lesson Math circle level problem on binomial coefficients

Algebra ->  Permutations -> Lesson Math circle level problem on binomial coefficients      Log On


   


This Lesson (Math circle level problem on binomial coefficients) was created by by ikleyn(52781) About Me : View Source, Show
About ikleyn:

Math circle level problem on binomial coefficients


Problem 1

In how many ways could five different envelopes be distributed into three mailboxes?

Solution 1

I will consider consequently the cases when where is no envelopes in the box #3;
                                        when there is 1 envelope  in the box #3;
                                        when there is 2 envelopes in the box #3;
                                        when there is 3 envelopes in the box #3;
                                        when there is 4 envelopes in the box #3;
                                        when there is 5 envelopes in the box #3.

For each of these cases, I will calculate the number of different distributions of the envelopes in three mailboxes, as follows.



a)  0 envelopes in the box #3:  N%5B0%5D = C%5B5%5D%5E0 + C%5B5%5D%5E1 + C%5B5%5D%5E2 + C%5B5%5D%5E3 + C%5B5%5D%5E1 + C%5B5%5D%5E0 = 1 + 5 + 10 + 10 + 5 + 1 = 32 ways.


b)  1 envelope in the box #3:  N%5B1%5D = 5*(C%5B4%5D%5E0 + C%5B4%5D%5E1 + C%5B4%5D%5E2 + C%5B4%5D%5E3 + C%5B4%5D%5E4) = 5*(1 + 4 + 6 + 4 + 1) = 80 ways.


c)  2 envelopes in the box #3:  N%5B2%5D = 10*(C%5B3%5D%5E0 + C%5B3%5D%5E1 + C%5B3%5D%5E2 + C%5B3%5D%5E3) = 10*(1 + 3 + 3 + 1) = 80.


d)  3 envelopes in the box #3:  N%5B3%5D = 10*(C%5B2%5D%5E0 + C%5B2%5D%5E1 + C%5B2%5D%5E2) = 10*(1 + 2 + 1) = 40 ways.


e)  4 envelopes in the box #3:  N%5B4%5D = 5*(C%5B1%5D%5E0 + C%5B2%5D%5E1) = 5*2 = 10 ways.


f)  5 envelopes in the box #3:  N%5B5%5D = 1 way.



The total is the sum   32 + 80 + 80 + 40 + 10 + 1 = 243 ways.


Answer.  243 ways.

-----------------

The formulas in this post are SELF-EXPLANATORY.

If you have questions or if you need explanations, look into the formulas until they tell you the whole story.


==================


Notice that   243 = 3%5E5,  and it is not eventually.

There is another way to calculate it,  which gives the same result,  but is much shorter and much more elegant.


Solution 2

You need to consider the binomial expansion of  %28x%2By%2Bz%29%5E5 as the sum 

    %28x%2By%2Bz%29%5E5 = sum of all  A%5Bi%2Cj%2Ck%5D%2Ax%5Ei%2Ay%5Ej%2Az%5Ek with the coefficients  A%5Bi%2Cj%2Ck%5D,  i + j + k = 5.


Each particular term  x%5Ei%2Ay%5Ej%2Az%5Ek  with i + j + k = 5 "marks" some possible particular distribution 
of envelopes in the three boxes called "x", "y" and "z",
and the coefficient  A%5Bi%2Cj%2Ck%5D  at this term represents the "multiplicity" of the given concrete distribution 
(i,j,k) in the boxes x, y, and z.


The number of all possible distributions is the sum of all coefficients  A%5Bi%2Cj%2Ck%5D, and it is equal to 

the value of  %28x%2By%2Bz%29%5E5   at  x= 1, y= 1, z= 1,  which is exactly  %281%2B1%2B1%29%5E5 = 3%5E5 = 243.


This problem is for an advanced Math circle / Math Olympiad level.

Therefore,  I will not go further into details - the idea is just presented very clearly for an adequate person.


My lessons on Binomial Theorem, Binomial Formula, Binomial Coefficients and Binomial Expansion in this site are
    - Binomial Theorem, Binomial Formula, Binomial Coefficients and Binomial Expansion
    - Remarkable identities for Binomial Coefficients
    - The Pascal's triangle
    - Solved problems on binomial coefficients
    - Solving equations that include binomial coefficients and numbers of permutations
    - Math circle level problem on binomial coefficients                                                                          (this lesson)
    - OVERVIEW of lessons on Binomial Expansion, Binomial coefficients and the Pascal's triangle


Use this file/link  ALGEBRA-II - YOUR ONLINE TEXTBOOK  to navigate over all topics and lessons of the online textbook  ALGEBRA-II.


This lesson has been accessed 1417 times.