# 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 $
x_1 ,x_2 ,x_3 \in \mathbb{N}
$
where $
x_1 \leqslant 6
$
and $
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 $\binom{15+3-1}{15}=\binom{17}{15}$ (1) ways

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

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

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

$

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

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

2. By Generating Functions

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

This is easy to calculate $
\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: $
\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 $
\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
$

$
\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: $
\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 $
\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)