document.write( "Question 1149895: x1 + x2 + x3 + x4 + x5 = 36
\n" ); document.write( "How many solutions (using only nonnegative integers) are there to the following equation? \n" ); document.write( "

Algebra.Com's Answer #771242 by ikleyn(52781) $\"\"$ $\"About$

You can put this solution on YOUR website!
.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " This problem and the method of its solution are of the highest peaks in Combinatorics.\r
\n" ); document.write( "\n" ); document.write( " They are at the level of a School Math circle at the local or (better to say) a renowned University.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "

\r\n" );
document.write( "x1 + x2 + x3 + x4 + x5 = 36     (1)\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Imagine 36 marbles on the table, placed in one straight line with small gaps between them.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "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) \r\n" );
document.write( "after the last marble in the row.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Let  , ,  , ,  be some solution to the given equation.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "You then place bar N2 after -th marble in the gap in the row of marbles; \r\n" );
document.write( "\r\n" );
document.write( "then you count next  marbles  in the row of marbles after bar N2 and place bar N3 in the gap there;\r\n" );
document.write( "\r\n" );
document.write( "then you count next  marbles  in the row of marbles after bar N3 and place bar N4 in the gap there;\r\n" );
document.write( "\r\n" );
document.write( "finally, you count next  marbles  in the row of marbles after bar N4 and place bar N5 in the gap there.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "At this moment, all 36 marbles are divided in 5 groups between bars (1-2), (2-3), (3-4), (4,5) and (5,6).\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Notice that if some  is zero, then the corresponding bars go to common respective gap.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "So, having the solution to equation (1) in non-negative positive integer number, you place 4 bars N2, N3, N4 and N5 in \r\n" );
document.write( "their corresponding positions in gaps in the row of marbles. \r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "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, \r\n" );
document.write( "and the numbers of marbles in each group form the solution to equation (1).\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Thus, there is one-to-one correspondence between the set of solutions to equation (1) in non-negative integer numbers, \r\n" );
document.write( "\r\n" );
document.write( "from one side, and all different possible placings of 4 bars in 35 gaps in the row between 36 marbles.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Thus we have 35+4 = 39 entities, 35 marbles and 4 bars; 35 marbles are indistiguishable and 4 movable bars \r\n" );
document.write( "are indistinguishable, too.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "The number of all possible indistinguishable arrangements of 39 items of two types with 35 indistinguishable of one type \r\n" );
document.write( "\r\n" );
document.write( "and 4 indistinguishable of the other type is   =  = 82251.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Hence,  the number of all possible solutions to equation (1) in non-negative integer numbers is equal to   = 82251.   \r\n" );
document.write( "\r\n" );
document.write( "ANSWER.  The number of different solutions to equation (1)  is  82251.\r\n" );
document.write( "

\r
\n" ); document.write( "\n" ); document.write( "Solved.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "------------------\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "

\r\n" );
document.write( "More general problem to find the number of non-negative integer solution to equation\r\n" );
document.write( "\r\n" );
document.write( "     +  +  + . . . +  = n    \r\n" );
document.write( "\r\n" );
document.write( "where k <= n, can be solved in the same way and has the answer  .\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "We have then   (n-1)  gaps between  \"n\"  \"marbles\"  and  (k-1)  movable dividing bars.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "The method I used in the solution is called the  \"method of bars and stars\".\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "You can read about it in this Wikipedia article\r\n" );
document.write( "\r\n" );
document.write( "https://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29\r\n" );
document.write( "

\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "

\n" );