Results 1 to 4 of 4

Math Help - Give a combinatorial proof

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    4

    Give a combinatorial proof

    n! 2(n 1)! = (n 1)(n 2)(n 2)!


    I don't understand how to even start, an algebraic proof isn't an acceptable answer
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    Take into account that is n!= n\ (n-1)!, so that (n-1)! is 'common factor'...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,409
    Thanks
    1294
    Quote Originally Posted by KrazEcat01 View Post
    n! 2(n 1)! = (n 1)(n 2)(n 2)!


    I don't understand how to even start, an algebraic proof isn't an acceptable answer
    A combinatorical proof will also involve algebra. \displaystyle \chi \sigma's answer is the best...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    The LHS is the number of permutations of \{1,...,n\} such that 1 ends up neither in the first nor in the second position.
    ( n! permutations in all, (n-1)! permuations with 1 in the first position, and (n-1)! permutations with 1 in the second position , hence n!-2(n-1)! permutations ...)

    So let's count this in a different way, first, let's choose a number for the first position, we have (n-1) choices since we can't choose 1, for the second position we have (n-2) choices -since we can't choose 1 and we can't the number that we have chosen for the first position.
    To complete the rest we have (n-2)! ways, thus: (n-1)\cdot (n-2)\cdot (n-2)! ways in all.
    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: July 4th 2010, 08:02 PM
  2. How to give combinatorial proofs
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 20th 2010, 11:06 PM
  3. Combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 10th 2009, 12:20 PM
  4. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 17th 2008, 04:40 PM
  5. Combinatorial proof?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 24th 2008, 06:20 PM

Search Tags


/mathhelpforum @mathhelpforum