# Combinatorial problem

• Apr 19th 2008, 12:59 PM
Frostking
Combinatorial problem
I have having trouble yet again!

x sub one + x sub 2 + x sub 3 = 15 These are all nonnegative integers and

x sub one is greater or = to 0 and less than or equal to 6

x sub 2 and x sub 3 are both greater than or equal to 0

Should I reduce k by 6 in the formula C(9 + 3-1,3-1)???? Please advise.
• Apr 19th 2008, 06:19 PM
PaulRS
We have $\displaystyle x_1 ,x_2 ,x_3 \in \mathbb{N}$ where $\displaystyle x_1 \leqslant 6$ and $\displaystyle x_1 + x_2 + x_3 = 15$

There are several ways to solve this.

1. We first consider the number of possibilities without the restriction

We have $\displaystyle \binom{15+3-1}{15}=\binom{17}{15}$ (1) ways

Now we will consider the restriction, indeed if $\displaystyle x_1 \leqslant 6$ we have to substract the cases in which $\displaystyle 7 \leqslant x_1 \leqslant 15$ from (1)

If $\displaystyle 7 \leqslant x_1 \leqslant 15 \Rightarrow x_1 = a_1 + 7{\text{ where 8}} \geqslant a_1 \geqslant 0$

$\displaystyle a_1 + 7 + x_2 + x_3 = 15 \Leftrightarrow a_1 + x_2 + x_3 = 8$

So there are $\displaystyle \binom{8+3-1}{8}=\binom{10}{8}$ ways to do this.

Therefore the final answer would be $\displaystyle \binom{17}{15}-\binom{10}{8}=91$

2. By Generating Functions

Note that it is the coefficient of $\displaystyle x^{15}$ in the product $\displaystyle p(x)=(1+x+...+x^6)\cdot{(1+x+...)^2}$

This is easy to calculate $\displaystyle \left. \begin{gathered} 1 + x + ... + x^6 = \frac{{1 - x^7 }} {{1 - x}} \hfill \\ 1 + x + ... = \frac{1} {{1 - x}} \hfill \\ \end{gathered} \right] \Rightarrow p\left( x \right) = \frac{{1 - x^7 }} {{\left( {1 - x} \right)^3 }}$

By the Binomial Theorem: $\displaystyle \frac{1} {{\left( {1 - x} \right)^n }} = \sum\limits_{r = 0}^\infty {\left( {\begin{array}{*{20}c} {n + r - 1} \\ r \\ \end{array} } \right)} \cdot x^r$ so $\displaystyle \frac{1} {{\left( {1 - x} \right)^3 }} = \sum\limits_{r = 0}^\infty {\left( {\begin{array}{*{20}c} {r + 2} \\ r \\ \end{array} } \right)} \cdot x^r$

$\displaystyle \frac{{1 - x^7 }} {{\left( {1 - x} \right)^3 }} = \sum\limits_{r = 0}^\infty {\left( {\begin{array}{*{20}c} {r + 2} \\ r \\ \end{array} } \right)} \cdot x^r - \sum\limits_{r = 0}^\infty {\left( {\begin{array}{*{20}c} {r + 2} \\ r \\ \end{array} } \right)} \cdot x^{r + 7}$

Thus: $\displaystyle \frac{{1 - x^7 }} {{\left( {1 - x} \right)^3 }} = \sum\limits_{r = 0}^\infty {\left( {\begin{array}{*{20}c} {r + 2} \\ r \\ \end{array} } \right)} \cdot x^r - \sum\limits_{r = 7}^\infty {\left( {\begin{array}{*{20}c} {r - 5} \\ {r - 7} \\ \end{array} } \right)} \cdot x^r$

Then the coefficient is $\displaystyle \Rightarrow \left( {\begin{array}{*{20}c} {15 + 2} \\ {15} \\ \end{array} } \right) - \left( {\begin{array}{*{20}c} {15 - 5} \\ {15 - 7} \\ \end{array} } \right) = \left( {\begin{array}{*{20}c} {17} \\ {15} \\ \end{array} } \right) - \left( {\begin{array}{*{20}c} {10} \\ 8 \\ \end{array} } \right)$

(Here notice that again we are substracting the extra we'd have without the restriction)