Combinatorial problem

**Frostking** · April 19th 2008, 12:59 PM

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.

**PaulRS** · April 19th 2008, 06:19 PM

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)

Thread: Combinatorial problem

LinkBack

Thread Tools

Display