Number of solutions

Question

Number of non negative integer solutions to the equation X₁ + X₂ + X₃ + X₄ = 15, where $1 \leqslant X1,X2,X3,X4 \leqslant6$ is ________

Comments

https://gateoverflow.in/65803/find-number-integral-solutions-using-generating-function

Answer 1

$$\begin{align*} Equation,\\ &\Rightarrow x_1+x_2+x_3+x_4 = 15 \;\;\; 1\leq x_i\leq 6 \\ &\Rightarrow y_1+y_2+y_3+y_4 = 11 \;\;\; 0\leq y_i\leq 5 \\ \end{align*}$$

Using $\large\color{green}{\text{generating function}}$ $\rightarrow$

$$\begin{align*} &=\left [ y^{11} \right ]\left [ \frac{1-y^6}{1-y} \right ]^{4} \\ &=\left [ y^{11} \right ]\left [ \sum_{r=0}^{4}\binom{4}{r}(-1)^r.y^{6r} \right ] \ \left [ \sum_{r=0}^{\infty}\binom{3+r}{r}.y^r \right ] \\ &=1*\binom{14}{11} + (-1)^1.4.\binom{8}{5} \;\;\;\;\; \left \{ \text{for } r=(0,11) \;\; \text{and }\;\; r=(1,5) \right \} \\ &=140 \end{align*}$$

---

more example:

NOTE:

1. $1+x+x^2+x^3+.....x^n = \frac{1-x^{n+1}}{1-x}$

2. $\frac{1}{(1-x)^n} = \sum_{r=0}^{\infty}\binom{n+r-1}{r}.x^r$

3. $\left [ x^{11} \right ]$ means coefficient of $x^{11}$ of the whole expression.

Comments

Actually that is not :)

It is like saying x1,x2, x3, x4 >= 1    and   x1, x2, x3, x4 <=6

---

Thanks Kapil. Got confused. :)

---

How generating function is formed can u explained please

Answer 2

140 is the right answer i think.

Comments

364-264 = 140 ??????????????

---

No, but 56*4 = 224, so 364-224=140. The writer must have missed it.

Answer 3

They are asking for number of solutions where x₁>= 1  and x₂,x₃,x₄ <=6

Method 1: Inclusion-Exclusion

Lets find total solutions where x₁>= 1.

So, x₁ + 1 + x₂ + x₃  + x₄ = 15

So, that comes as   $\binom{17}{3}$   = 680   ............(1)

Now, we need to find solution where (x₂>=7 or x₃>=7 or x₄>=7).

Lets denote such events as E(x₂>=7 or x₃>=7 or x₄>=7).

$\therefore$ E(x₂>=7 or x₃>=7 or x₄>=7)

= E(x₂>=7) + E(x₃>=7) + E(x₄>=7) - E(x₂>=7 $\cap$ x₃>=7) - E(x₄>=7 $\cap$ x₃>=7) - E(x₄>=7 $\cap$ x₂>=7)  ..........(2)

   (only 2 of x₂, x₃, x₄ can be more than 7 at the same time)

Now, when x₂>=7, then equation will become x₁ + 1 + x₂ + 7 + x₃  + x₄ = 15

Thus, E(x₂>=7) = $\binom{10}{3}$ = 120

$\therefore$ E(x₂>=7 or x₃>=7 or x₄>=7) = 120 + 120 + 120 - 1 - 1 - 1 = 357

Thus, answer = 680 - 357 = 323

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

Method 2: Generating functions

For the given equation, generating function is as follows:

(x¹ + x² + .......+ x¹⁵) ( 1+ x¹ + .....+ x⁶)  ( 1+ x¹ + .....+ x⁶)  ( 1+ x¹ + .....+ x⁶)

We have to find coefficient of x¹⁵ in the above equation.

So, above equation becomes

= (x¹ + x² + .......+ x¹⁵) ( 1+ x¹ + .....+ x⁶)³

= x¹(x⁰ + x¹ + .....+ x¹⁴)( 1+ x¹ + .....+ x⁶)³

= x^{1 *} $\frac{1-x^{15}}{1-x}$  *  $(\frac{1-x^{7}}{1-x})^{3}$

Now, we cancel $x^{15}$ in the second term because we need max of x¹⁴ from second and third terms.

So, above equation becomes

= x¹ * $(1-x^{7})^{3}$ * $(1-x)^{4}$

= x¹ * (1 - 3x + 3x¹⁴) * ( 680x¹⁴ + 120x⁷ + 1)    

I have selected only those components out of expansion for $(1-x)^{4}$ which will give me x¹⁴ out of second and third components above.

So, just calculating the coefficients of x¹⁴ from above equation,

answer = 323