Results 1 to 2 of 2

Thread: 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 $\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)
    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: Oct 23rd 2011, 07:04 AM
  2. Combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Oct 4th 2011, 09:05 AM
  3. combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Apr 18th 2010, 12:22 PM
  4. combinatorial problem??
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Sep 23rd 2009, 10:29 PM
  5. Combinatorial problem
    Posted in the Statistics Forum
    Replies: 2
    Last Post: Jun 13th 2008, 06:22 PM

Search Tags


/mathhelpforum @mathhelpforum