মঙ্গলবার, ২৬ ফেব্রুয়ারী, ২০১৩

Solution of Light OJ - 1102 - Problem Makes Problem

Problem Statement :

        As I am fond of making easier problems, I discovered a problem. Actually, the problem is 'how can you make n by adding k non-negative integers?' I think a small example will make things clear. Suppose n=4 and k=3. There are 15 solutions. They are
1.      0 0 4
2.      0 1 3
3.      0 2 2
4.      0 3 1
5.      0 4 0
6.      1 0 3
7.      1 1 2
8.      1 2 1
9.      1 3 0
10.  2 0 2
11.  2 1 1
12.  2 2 0
13.  3 0 1
14.  3 1 0
15.  4 0 0
As I have already told you that I use to make problems easier, so, you don't have to find the actual result. You should report the result modulo 1000,000,007.

Problem Logic :
    
 1.    Note that a similar classic problem is the following:

 2.  How many ways can 10 pieces of candy be divided among 4 children?

3. For this case we need to find the number of solutions to the equation

                                i+j+k+l = 10

                                where i, j, k, and l are non-negative integers. 

 4. We can find the answer using a technique popularly known as "stars and bars".  

5. The idea behind this method is the following:

                (*) We represent the objects to be divided by "stars": ****
                (*) To indicate dividing the object into groups, we use bars as "divider" symbols:  |||


6.For our problem, we have ten pieces of candy:

                          **********

7. To divide these ten objects into four groups, we need three dividers:

                          **********|||

8. The particular arrangement of the "stars and bars" shown above 
specifically represents the case where the first child gets all ten 
pieces of candy.  


9.  Each different arrangement of these stars and bars represents a distinct distribution of the ten pieces of candy among the four children.  


10. For example, the arrangement represents the case where the first child gets 3 pieces,


                                             ***|*|**|****

 the second child 1, the third child 2, and the fourth child 4.

11. So the number of different ways of distributing 10 pieces of candy 
among 4 children is the number of distinct arrangements of the stars 
and bars.  


12. With 10 stars and 3 bars, this number is, as you probably 
know,

                            (10+3)!                                 13*12*11
                          --------- = "13 choose 3" = -------- = 13*2*11 = 286
                           (10!)(3!)                                   3*2*1

13. So the number of terms in the expansion of (a+b+c+d)^10 is 286.

14. If we are raising an expression with "m" terms to the "n"th power, 
then we have n "stars" and (m-1) "bars"; the number of terms in the 
expansion is then

  (n+(m-1))!
  ---------- = "(n+m-1) choose (m-1)"
  (n!)(m-1)!


15. Note this agrees with what you noted about the number of terms in the 
expansion of (a+b)^n.  Here the number of terms, "m", is 2; so the 
number of terms in the expansion of (a+b)^n is

  "(n+m-1) choose (m-1)" = "n+1 choose 1" = n+1
এর দ্বারা পোস্ট করা এই সময়ে
লেবেলসমূহ: , , , ,

৮টি মন্তব্য:

এতে সদস্যতা: মন্তব্যগুলি পোস্ট করুন (Atom)