Results 1 to 6 of 6

Math Help - Permutation/Combination

  1. #1
    mlg
    mlg is offline
    Junior Member
    Joined
    Oct 2013
    From
    Ireland
    Posts
    54

    Permutation/Combination

    I need help with this question please.
    If n is positive whole number, show that (n)(2nCn)= (n+1)(2nCn-1)

    As 2nCn - 2nCn-1 is a whole number show that (1/n+1)(2nCn) is a whole number
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,616
    Thanks
    1578
    Awards
    1

    Re: Permutation/Combination

    Quote Originally Posted by mlg View Post
    I need help with this question please.
    If n is positive whole number, show that (n)(2nCn)= (n+1)(2nCn-1)
    As 2nCn - 2nCn-1 is a whole number show that (1/n+1)(2nCn) is a whole number
    $(n)\dbinom{2n}{n}=\dfrac{(n)(2n)!}{(n!)^2}~\&~(n+ 1)\dbinom{2n}{n-1}=\dfrac{(n+1)(2n)!}{(n+1)!(n-1)!}$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    mlg
    mlg is offline
    Junior Member
    Joined
    Oct 2013
    From
    Ireland
    Posts
    54

    Re: Permutation/Combination

    Thanks for the quick response.
    I will now study your reply in more detail.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,845
    Thanks
    715

    Re: Permutation/Combination

    If your teacher wants a more combinatorial proof, then $\binom{2n}{n}$ is the number of $n$-element subsets of a $2n$-element set. Similarly, $\binom{2n}{n-1}$ is the number of $(n-1)$-element subsets of a $2n$-element set.

    So, number the elements of the $2n$-element set $1,2,\ldots, 2n$. Consider a pair, $(i,\{a_1,\ldots, a_n\})$ where $1\le i \le n$ and $\{a_1,\ldots, a_n\}$ is an $n$-element subset of the $2n$-element set where $a_1<a_2 <\cdots <a_n$. The product principle tells us there are $n\binom{2n}{n}$ such pairs.

    Given any such pair, $(i,\{a_1,\ldots, a_n\})$, remove the $i$-th element from the set, so that $\{a_1,\ldots, a_{i-1},a_{i+1},\ldots, a_n\}$ remains. Consider the remaining elements of the $2n$-element set: $\{b_1,\ldots, b_{n+1}\}$ (there are $n+1$ elements not in the set after one element is removed). Let $k$ be the index of the removed element. This allows us to create a pair, $(k,\{a_1,\ldots, a_{i-1},a_{i+1},\ldots, a_n\})$ where $1\le k \le n+1$ and the set is an $(n-1)$-element subset of the $2n$-element set. Again, the product principle tells us there are $(n+1)\binom{2n}{n-1}$ such pairs.

    Now, given any such pair consisting of a number from 1 to $n+1$ and an $(n-1)$-element subset of the $2n$-element set: $(k,\{a_1,\ldots, a_{n-1}\})$, consider the remaining $n+1$ elements of the $2n$-element set: $\{b_1,\ldots, b_{n+1}\}$ where $b_1 < \cdots < b_{n+1}$. Add $b_k$ to the $n-1$-element subset. Reindex the set so that $\{a_1^\prime, \ldots, a_n^\prime\}$ satisfies $a_1^\prime < \cdots < a_n^\prime$. Let $i$ be the index of $b_k$ in this new index. This allows us to create a pair, $(i,\{a_1^\prime,\ldots, a_n^\prime\})$. These are inverse operations, implying a bijective process. If there is a bijection between two sets, they must have the same number of elements, so $n\binom{2n}{n} = (n+1)\binom{2n}{n-1}$.

    The proof is a bit longer, but it also a bit stronger combinatorially.
    Last edited by SlipEternal; March 19th 2014 at 02:21 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,710
    Thanks
    629

    Re: Permutation/Combination

    Hello, mlg!

    \text{If }n\text{ is a natural number, show that: }\:n\left(_{2n}C_n\right)\:=\: (n+1)\left(_{2n}C_{n-1}\right)

    n\left(_{2n}C_n\right) \;=\;\rlap{/}n\cdot\frac{(2n)!}{\rlap{/}n!\,n!} \;=\;\frac{(2n)!}{(n-1)!\,n!}

    (n+1)\left(_{2n}C_{n-1\right)} \;=\;(\rlap{/////}n+1)\cdot\frac{(2n)!}{(n-1)!(\rlap{/////}n+1)!} \;=\;\frac{(2n)!}{(n-1)!\,n!}
    Follow Math Help Forum on Facebook and Google+

  6. #6
    mlg
    mlg is offline
    Junior Member
    Joined
    Oct 2013
    From
    Ireland
    Posts
    54

    Re: Permutation/Combination

    Thanks for your time and effort.
    Very much appreciated.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Permutation and Combination
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 2nd 2011, 05:01 AM
  2. Permutation and Combination
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: August 31st 2011, 09:44 PM
  3. Permutation/Combination?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 4th 2010, 08:01 PM
  4. Permutation and Combination
    Posted in the Statistics Forum
    Replies: 5
    Last Post: February 16th 2008, 01:17 PM
  5. Combination or permutation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 13th 2007, 10:15 AM

/mathhelpforum @mathhelpforum