Results 1 to 3 of 3

Math Help - Combinatorics

  1. #1
    Junior Member
    Joined
    Mar 2011
    Posts
    31

    Combinatorics

    Show that:

    \[ \left( \begin{array}{cc}<br />
n   \\<br />
k   \\  \end{array} \right)\] \[ \left( \begin{array}{cc}<br />
n-k   \\<br />
j   \\  \end{array} \right)\]= \[ \left( \begin{array}{cc}<br />
n   \\<br />
j   \\  \end{array} \right)\] \[ \left( \begin{array}{cc}<br />
n-j   \\<br />
k   \\  \end{array} \right)\]


    j+k\leq n

    need some help here, only thing that came to my mind was that

    \[ \left( \begin{array}{cc}<br />
n   \\<br />
k   \\  \end{array} \right)\]= \[ \left( \begin{array}{cc}<br />
n   \\<br />
n-k   \\  \end{array} \right)\]

    then what?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,909
    Thanks
    771
    Hello, mechaniac!

    \displaystyle \text{Show that: } {n\choose k}{n-k\choose j} \;=\; {n\choose j}{n-j\choose k}

    Start with the left side:

    \displaystyle {n\choose k}{n\!-\!k\choose j} \;=\;\frac{n!}{k!\,(n\!-\!k)!}\cdot\frac{(n\!-\!k)!}{j!(n\!-\!j\!-\!k)!} \;=\;\frac{n!}{j!\,k!\,(n\!-\!j\!-\!k)!}


    \text{Multiply by }\dfrac{(n\!-\!j)!}{(n\!-\!j)!}

    . . \displaystyle \frac{(n\!-\!j)!}{(n\!-\!j)!}\cdot\frac{n!}{j!\,k!\,(n\!-\!j\!-\!k)!} \;=\;\frac{n!\,(n\!-\!j)!}{j!\,k!\,(n\!-\!j)!(n\!-\!j\!-\!k)!}


    . . \displaystyle =\;\frac{n!}{j!(n\!-\!j)!} \cdot \frac{(n\!-\!j)!}{k!\,(n\!-\!j\!-\!k)!} \;=\;{n\choose j}{n\!-\!j\choose k}

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2011
    Posts
    31
    of course! thanks for the good explanation!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Combinatorics.
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: July 20th 2010, 03:29 AM
  2. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 18th 2010, 09:14 PM
  3. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 3rd 2010, 06:24 PM
  4. combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2010, 11:53 PM
  5. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 10th 2009, 07:03 AM

Search Tags


/mathhelpforum @mathhelpforum