Home » Uncategorized » Number of solutions

Number of solutions

Find the number of solutions of the equation:

    \[x_1+x_2+\cdots + x_{100} = 2017\]

in the positive integers.

Solution

We set y_n=x_n-1 \;\;, \;\; 1\leq n \leq 100. It suffices to find the number of solutions of the equation

(1)   \begin{equation*} y_1+y_2+ \cdots + y_n =1917 \end{equation*}

in the non negative numbers. We represent each sum z_1+\cdots+z_m of non negative integers with a sequence of z_1 dots (\bullet) followed by a vertical bar (\big \mid), after z_2 dots another one vertical bar etc, till we place the last z_m dots ( without the vertical bar at the end.) For example the sum 5+2+0+1=8 can be represented as

    \[\bullet \bullet \bullet  \bullet \bullet \mid \bullet \bullet \mid \mid \bullet\]

 

We note that every solution of (1) matches a sequence that has 1917 dots in total and 99 vertical bars. Conversely, every such sequence matches a solution of (1).

Thus, in total there are

    \[\binom{1917+99}{99} = \binom{2016}{99}\]

solutions.

Comment: In general the equation

    \[x_1+x_2+\cdots+x_m=n\]

has \displaystyle  \binom{n-1}{m-1} solutions in the positive integers and \displaystyle \binom{n+m-1}{m-1} solutions in the non negative integers.

 

Read more

Leave a comment

Who is Tolaso?

Find out more at his Encyclopedia Page.

Donate to Tolaso Network