Results 1 to 4 of 4

Thread: 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
    6
    Take into account that is $\displaystyle n!= n\ (n-1)!$, so that $\displaystyle (n-1)!$ is 'common factor'...

    Kind regards

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

  3. #3
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    12,880
    Thanks
    1946
    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 \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 $\displaystyle \{1,...,n\}$ such that 1 ends up neither in the first nor in the second position.
    ( $\displaystyle n!$ permutations in all, $\displaystyle (n-1)!$ permuations with 1 in the first position, and $\displaystyle (n-1)!$ permutations with 1 in the second position , hence $\displaystyle 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 $\displaystyle (n-1)$ choices since we can't choose 1, for the second position we have $\displaystyle (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 $\displaystyle (n-2)!$ ways, thus: $\displaystyle (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: Jul 4th 2010, 08:02 PM
  2. How to give combinatorial proofs
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 20th 2010, 11:06 PM
  3. Combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 10th 2009, 12:20 PM
  4. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 17th 2008, 04:40 PM
  5. Combinatorial proof?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Feb 24th 2008, 06:20 PM

Search Tags


/mathhelpforum @mathhelpforum