Results 1 to 2 of 2

Math Help - Combinatorial problem

  1. #1
    Member
    Joined
    Oct 2007
    Posts
    159

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    We have <br />
x_1 ,x_2 ,x_3  \in \mathbb{N}<br />
where <br />
x_1  \leqslant 6<br />
and <br />
x_1  + x_2  + x_3  = 15<br />

    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 <br />
x_1  \leqslant 6<br />
we have to substract the cases in which <br />
7 \leqslant x_1  \leqslant 15<br />
from (1)


    If <br />
7 \leqslant x_1  \leqslant 15 \Rightarrow x_1  = a_1  + 7{\text{ where 8}} \geqslant a_1  \geqslant 0<br />

    <br />
a_1  + 7 + x_2  + x_3  = 15 \Leftrightarrow a_1  + x_2  + x_3  = 8<br /> <br />

    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 <br />
\left. \begin{gathered}<br />
  1 + x + ... + x^6  = \frac{{1 - x^7 }}<br />
{{1 - x}} \hfill \\<br />
  1 + x + ... = \frac{1}<br />
{{1 - x}} \hfill \\ <br />
\end{gathered}  \right] \Rightarrow p\left( x \right) = \frac{{1 - x^7 }}<br />
{{\left( {1 - x} \right)^3 }}<br />

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

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

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

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

    (Here notice that again we are substracting the extra we'd have without the restriction)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. a combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 23rd 2011, 07:04 AM
  2. Combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 4th 2011, 09:05 AM
  3. combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 18th 2010, 12:22 PM
  4. combinatorial problem??
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 23rd 2009, 10:29 PM
  5. Combinatorial problem
    Posted in the Statistics Forum
    Replies: 2
    Last Post: June 13th 2008, 06:22 PM

Search Tags


/mathhelpforum @mathhelpforum