Results 1 to 7 of 7

Math Help - Combinatorial proof

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

    Combinatorial proof

    Give a combinatorial proof: For n and k satisfying 1\leq k\leq n,

    _{n}P_{k}=(n)_{k}=\sum_{j=k}^{n}k*(j-1)_{k-1}.

    \sum_{j=k}^{n}k*(j-1)_{k-1}
    =k(k-1)_{k-1}+k(k)_{k-1}+k(k+1)_{k-1}+\ldots+k(n-2)_{k-1}+k(n-1)_{k-1}

    =\frac{k*(k-1)!}{[(k-1)-(k-1)]!}+\frac{k*k!}{[k-(k-1)]!}+\frac{k(k+1)!}{[(k+1)-(k-1)]!}+\ldots+\frac{k(n-2)!}{[(n-2)-(k-2)]!}+\frac{k(n-1)!}{[(n-1)-(k-1)]!}<br />
    =\frac{k(k-1)!}{0!}+\frac{k*k!}{1!}+\frac{k(k+1)!}{2!}+\ldots  +\frac{k(n-2)!}{(n-k-1)!}+\frac{k(n-1)!}{(n-k)!}. When we factor out k(k-1)! we are left with

    1+k+\frac{k(k+1)}{2!}+\ldots+\frac{(n-k-1)!}{(n-k-1)!}+\frac{(n-k)!}{(n-k)!}=(n-k)??

    Now take (n-k)k(k-1)!=(n-k)k! and if we multiply by (n-k)!/(n-k)! we get (n-k)k!(n-k)!/(n-k)! = (n-k)n!/(n-k)!

    This would equal _{n}P_{k}=(n)_{k}=n!/(n-k)! except for the extra (n-k) in the numerator. Can someone please point out my mistake?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    115
    Quote Originally Posted by oldguynewstudent View Post
    Give a combinatorial proof: For n and k satisfying 1\leq k\leq n,

    _{n}P_{k}=(n)_{k}=\sum_{j=k}^{n}k*(j-1)_{k-1}.
    If I understand the question correctly, (n)_k stands for Falling factorial.

    I don't thinks the above forumla is true.
    Try n=3, k=1.
    Then the formula gives:
    3=1.1+1.2+1.2!

    Also, I think that would you tried is just manipulation sums, which is different form what I understand under combinatorial proof.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Quote Originally Posted by kompik View Post
    If I understand the question correctly, (n)_k stands for Falling factorial.

    I don't thinks the above forumla is true.
    Try n=3, k=1.
    Then the formula gives:
    3=1.1+1.2+1.2!

    Also, I think that would you tried is just manipulation sums, which is different form what I understand under combinatorial proof.
    For n=3, k=1 the formula gives 1*(0)_0 + 1*(1)_0 + 1*(2)_0 = 1+1+1=3

    I am new to combinatorial proofs, but this is the way I understand my professor did it in class. Just count things one way, then show that the other side comes out with the same counting result. I may be wrong but I will probably go see him before class on Tuesday. He is very good and the class is interesting but I think I did poorly on the test last Thursday. I only knew 7 out of 10 problems but my friends say he gives partial credit so I will have to see how it goes. Rotten luck! I knew how to do most of the problems he said would be on the test and none were extremely difficult. There were about 75 problems we had to study though. I really appreciate your help. Thank you very much.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    115
    Sorry for my mistake above :-(

    Quote Originally Posted by oldguynewstudent View Post
    Give a combinatorial proof: For n and k satisfying 1\leq k\leq n,

    _{n}P_{k}=(n)_{k}=\sum_{j=k}^{n}k*(j-1)_{k-1}.
    You could notice, that if you divide this by k!, you get
    \binom nk=\sum_{j=k}^{n} \binom{j-1}{k-1},
    which is a well-known identity - identity (10) from Binomial coefficient - Wikipedia, the free encyclopedia ; proof can be found at Sum of k Choose m up to n - ProofWiki
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    115
    Quote Originally Posted by oldguynewstudent View Post
    When we factor out k(k-1)! we are left with

    1+k+\frac{k(k+1)}{2!}+\ldots+\frac{(n-k-1)!}{(n-k-1)!}+\frac{(n-k)!}{(n-k)!}=(n-k)??

    Now take (n-k)k(k-1)!=(n-k)k! and if we multiply by (n-k)!/(n-k)! we get (n-k)k!(n-k)!/(n-k)! = (n-k)n!/(n-k)!
    I think you have a typo in the last two summands of this equation.
    I do not understand, where do you get the RHS from.
    You have n-k summands, only one of them is equal to one, so this cannot be equal to (n-k).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Quote Originally Posted by kompik View Post
    I think you have a typo in the last two summands of this equation.
    I do not understand, where do you get the RHS from.
    You have n-k summands, only one of them is equal to one, so this cannot be equal to (n-k).
    1+k+\frac{k(k+1)}{2!}+\ldots+\frac{(n-k-1)!}{(n-k-1)!}+\frac{(n-k)!}{(n-k)!}=(n-k)??
    You are correct in that the only way this adds to (n-k) is if k=1 which is an assumption that we cannot make. If k were 1, then we would have n-k terms equal to 1 which would be n-k.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    115
    Quote Originally Posted by kompik View Post
    Sorry for my mistake above :-(


    You could notice, that if you divide this by k!, you get
    \binom nk=\sum_{j=k}^{n} \binom{j-1}{k-1},
    which is a well-known identity - identity (10) from Binomial coefficient - Wikipedia, the free encyclopedia ; proof can be found at Sum of k Choose m up to n - ProofWiki
    You can find this as identity 135 in the book Benjamin, Quinn: Proofs that really count, together with a nice and easy combinatorial proof. Proofs that really count: the art of ... - Google Books

    I found also this document http://www.cs.columbia.edu/~cs4205/files/CM4.pdf which seems to be a good resource for identities involving binomial coefficients and their proofs. This formula is Corollary 4.1.5 (but is written differently). (I posted a wrong link to proofwiki in the above post by mistake.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorial proof?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 3rd 2011, 03:22 PM
  2. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: August 18th 2010, 04:08 AM
  3. Combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 10th 2009, 12:20 PM
  4. Combinatorial proof help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 30th 2009, 05:43 PM
  5. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 17th 2008, 04:40 PM

Search Tags


/mathhelpforum @mathhelpforum