Results 1 to 6 of 6

Math Help - Combinatorial Proof

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    Combinatorial Proof

    Attached is the section on Combinatorial Proofs from my text. I am a little confused. I understand the proof of the special case, then it goes on to say "It is no harder to prove in general."

    I would prove this identity in the following manner but I'm not sure if the following is a combinatorial proof or not. Please let me know if it is, or if it is not a combinatorial proof, please point me to a resource so I will understand it better.

    Prove the identity: (n)_{k}=(n-1)_{k}+k*(n-1)_{k-1}

    LHS (n)_{k}=\frac{n!}{(n-k)!}

    RHS (n-1)_{k}+k*(n-1)_{k-1}=\frac{(n-1)!}{(n-1-k)!}+\frac{k*(n-1)!}{(n-1-k+1)!}=
    \frac{(n-1)!}{(n-k-1)!}+\frac{k*(n-1)!}{(n-k)!}=\frac{(n-1)!}{(n-k-1)!}+\frac{k*(n-1)!}{(n-k)(n-k-1)!}=
    \frac{(n-k)(n-1)!+k*(n-1)!}{(n-k)(n-k-1)!}=\frac{(n-k+k)(n-1)!}{(n-k)!}=\frac{n(n-1)!}{(n-k)!}=\frac{n!}{(n-k)!}

    Since the LHS equals the RHS this completes the proof.

    Please let me know if the above is a combinatorial proof or not.
    Attached Thumbnails Attached Thumbnails Combinatorial Proof-comb_53.jpg   Combinatorial Proof-comb_54.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by oldguynewstudent View Post
    Attached is the section on Combinatorial Proofs from my text. I am a little confused. I understand the proof of the special case, then it goes on to say "It is no harder to prove in general."

    I would prove this identity in the following manner but I'm not sure if the following is a combinatorial proof or not. Please let me know if it is, or if it is not a combinatorial proof, please point me to a resource so I will understand it better.

    Prove the identity: (n)_{k}=(n-1)_{k}+k*(n-1)_{k-1}

    LHS (n)_{k}=\frac{n!}{(n-k)!}

    RHS (n-1)_{k}+k*(n-1)_{k-1}=\frac{(n-1)!}{(n-1-k)!}+\frac{k*(n-1)!}{(n-1-k+1)!}=
    \frac{(n-1)!}{(n-k-1)!}+\frac{k*(n-1)!}{(n-k)!}=\frac{(n-1)!}{(n-k-1)!}+\frac{k*(n-1)!}{(n-k)(n-k-1)!}=
    \frac{(n-k)(n-1)!+k*(n-1)!}{(n-k)(n-k-1)!}=\frac{(n-k+k)(n-1)!}{(n-k)!}=\frac{n(n-1)!}{(n-k)!}=\frac{n!}{(n-k)!}

    Since the LHS equals the RHS this completes the proof.

    Please let me know if the above is a combinatorial proof or not.
    I'm used to seeing (n)_k as P(n,k) but now that I see what we're talking about..

    The author writes that "It is no harder to prove in general" because you can follow the exact same methodology as the concrete proof for the general proof, only replacing 6 with n, 5 with n-1, 4 with k, and 3 with k-1. The only potentially sticky point is when n=1 or k=1.

    So, no need to write out all the long expressions you wrote. Just basically copy out the book proof with variables in place of numbers.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by oldguynewstudent View Post
    Attached is the section on Combinatorial Proofs from my text. I am a little confused. I understand the proof of the special case, then it goes on to say "It is no harder to prove in general."

    I would prove this identity in the following manner but I'm not sure if the following is a combinatorial proof or not. Please let me know if it is, or if it is not a combinatorial proof, please point me to a resource so I will understand it better.

    Prove the identity: (n)_{k}=(n-1)_{k}+k*(n-1)_{k-1}

    LHS (n)_{k}=\frac{n!}{(n-k)!}

    RHS (n-1)_{k}+k*(n-1)_{k-1}=\frac{(n-1)!}{(n-1-k)!}+\frac{k*(n-1)!}{(n-1-k+1)!}=
    \frac{(n-1)!}{(n-k-1)!}+\frac{k*(n-1)!}{(n-k)!}=\frac{(n-1)!}{(n-k-1)!}+\frac{k*(n-1)!}{(n-k)(n-k-1)!}=
    \frac{(n-k)(n-1)!+k*(n-1)!}{(n-k)(n-k-1)!}=\frac{(n-k+k)(n-1)!}{(n-k)!}=\frac{n(n-1)!}{(n-k)!}=\frac{n!}{(n-k)!}

    Since the LHS equals the RHS this completes the proof.

    Please let me know if the above is a combinatorial proof or not.
    Yes, this correctly proves that Np_K=[N-1]p_K+K[N-1]p_{K-1}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Hi oldguynewstudent,

    Your proof is correct, but it is not what is called a "combinatorial proof". See

    Combinatorial proof - Wikipedia, the free encyclopedia

    Some mathematicians feel that combinatorial proofs are better than other types of proof because they give more insight into the problems. I'm not sure everyone agrees with this.

    In order to have a combinatorial proof, you need to show that the two sides of your equation are essentially two different ways of counting the same set of objects. There may well be more than one way of doing this, but for example, (n)_k is the number of permutations of n objects taken k at a time. If you can show that the RHS also counts the same set of permutations, that will constitute a combinatorial proof.

    [Edit] Your book uses the number of ways to distribute k objects among n people in its sketch of the proof, which is another approach to the same identity. (I was a little slow to read the thumbnails.) But the idea of what it takes for a "combinatorial proof" is the same.[/edit]
    Last edited by awkward; June 3rd 2010 at 04:46 PM. Reason: addendum
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    ^{n-1} P_{k} is the number of ways to arrange k distinct elements from n-1 distinct elements.

    If we arrange k from a group of elements with one more element,
    then we will have all arrangements already counted by the ^{n-1}P_k formula,

    while extra arrangements will include the added element arranged with all
    original n-1 elements but taking k-1 of them at a time as the added element
    forms a group of k elements with them.

    This means that we will be arranging k-1 of the n-1 elements together with the
    added element, which can fit into any of the k positions, giving us k times
    the arrangements of k-1 from n-1.

    By this logic..

    ^{n-1}P_k+k\left(^{n-1}P_{k-1}\right) must equal ^nP_k

    Your proof then shows that this is the case.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Correct, that is a "combinatorial proof".
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 10th 2011, 01:42 PM
  2. Combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: July 4th 2010, 08:02 PM
  3. Combinatorial proof help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 30th 2009, 05:43 PM
  4. combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 30th 2008, 02:13 PM
  5. Combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 8th 2008, 11:45 PM

Search Tags


/mathhelpforum @mathhelpforum