Lesson Stars and bars method for Combinatorics problems

Source code of 'Stars and bars method for Combinatorics problems'

This Lesson (Stars and bars method for Combinatorics problems) was created by by ikleyn(52781)

: View Source, Show
About ikleyn:

<H2>Stars and bars method for Combinatorics problems</H2>

The problems and the method of their solutions in this lesson are of highest peaks in Combinatorics.

They are at the level of a School Math circle at the local or &nbsp;(better to say) &nbsp;of a renowned &nbsp;University.

<H3>Problem 1</H3>How many solutions &nbsp;(using only positive integers) &nbsp;are there to the following equation

x1 + x2 + x3 + x4 + x5 = 36 ?

<B>Solution</B>

<pre>
x1 + x2 + x3 + x4 + x5 = 36     (1)

Imagine 36 marbles on the table, placed in one straight line with small gaps between them.

Imagine you have 6 numbered bars, of which you place the first bar (bar N1) before the first marble and the last bar (bar N6) 
after the last marble in the row.

Let  {{{x[1]}}}, {{{x[2]}}},  {{{x[3]}}}, {{{x[4]}}}, {{{x[5]}}} be some solution to the given equation.

You then place bar N2 after {{{x[1]}}}-th marble in the gap in the row of marbles;

then you count next {{{x[2]}}} marbles  in the row of marbles after bar N2 and place bar N3 in the gap there;

then you count next {{{x[3]}}} marbles  in the row of marbles after bar N3 and place bar N4 in the gap there;

finally, you count next {{{x[4]}}} marbles  in the row of marbles after bar N4 and place bar N5 in the gap there.

At this moment, all 36 marbles are divided in 5 groups between bars (1-2), (2-3), (3-4), (4,5) and (5,6).

So, having the solution to equation (1) in positive integer number, you place 4 bars N2, N3, N4 and N5 in their 
corresponding positions in gaps in the row of marbles.

Vise versa, if you place 4 bars B2, B3, B4 and B5 in gaps in the row of 36 marbles, you divide marbles in 5 groups, 
and the numbers of marbles in each group form the solution to equation (1).

Thus, there is one-to-one correspondence between the set of solutions to equation (1) in positive integer numbers,

from one side, and all different possible placings of 4 bars in gaps in the row of 36 marbles.

Also note that no one pair of bars goes to any single gap between marbles,
because the numbers {{{x[1]}}}, {{{x[2]}}}, {{{x[3]}}}, {{{x[4]}}}, {{{x[5]}}} all are positive (!)

Thus, the number of solutions to equation (1) is equal to the number of COMBINATIONS of 35 (= 36-1) gaps taken 4 at a time.

Hence,  the number of all possible solutions to equation (1) in positive integer numbers is equal to  {{{C[35]^4}}} = {{{(35*34*33*32)/(1*2*3*4)}}} = 52360.

<U>ANSWER</U>.  The number of different solutions to equation (1)  is  {{{C[35]^4}}} = 52360.
</pre>

Solved.

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

<pre>
More general problem to find the number of positive integer solution to equation

{{{x[1]}}} + {{{x[2]}}} + {{{x[3]}}} + . . . + {{{x[k]}}} = n

where k <= n, can be solved in the same way and has the answer  {{{C[n-1]^(k-1)}}}.

We have then  &nbsp;(n-1) &nbsp;gaps between  "n"  "marbles"  and  (k-1)  movable dividing bars.

The method I used in the solution is called the  "<U>method of bars and stars</U>".

You can read about it in this Wikipedia article

https://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29
</pre>

The second problem seems to be similar to the first one, but is different in some important aspects.

<H3>Problem 2</H3>How many solutions &nbsp;(using non-negative integers) &nbsp;are there to the following equation