Results 1 to 7 of 7

Math Help - Combinatorial arguments

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    50

    Combinatorial arguments

    Please tell me what are the combinatorial arguments that imply:



    5^5- \left(\begin{array}{cc}5\\4\end{array}\right) 4^5+ \left(\begin{array}{cc}5\\3\end{array}\right) 3^5- \left(\begin{array}{cc}5\\2\end{array}\right) 2^5+ \left(\begin{array}{cc}5\\1\end{array}\right) 1^5=5!

    6^4- \left(\begin{array}{cc}6\\5\end{array}\right) 5^4+ \left(\begin{array}{cc}6\\4\end{array}\right) 4^4- \left(\begin{array}{cc}6\\3\end{array}\right) 3^4+ \left(\begin{array}{cc}6\\2\end{array}\right) 2^4- \left(\begin{array}{cc}6\\1\end{array}\right) 1^4=0 .
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie Mirado's Avatar
    Joined
    Apr 2009
    From
    New York
    Posts
    18

    um.... what?

    I don't understand what you're asking. Please clarify.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2008
    Posts
    50
    How to justify equalities.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Apr 2009
    Posts
    2
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    If you remember the explicit formula for the Bernuoulli number of index m...

    B_{m}= \sum_{n=0}^{m} \frac{1}{n+1}\cdot \sum_{k=0}^{n} (-1)^{k}\cdot \binom{n}{k}\cdot k^{m}

    ... you can obtain...

    - \frac{1}{6}\cdot \sum_{k=0}^{5}(-1)^{k}\cdot \binom{5}{k}\cdot k^{5} =B_{5} - \sum_{n=0}^{4}\frac{1}{n+1}\cdot \sum_{k=0}^{n}(-1)^{k}\cdot \binom{n}{k}\cdot k^{5}

    ... and you are able to verify the first identity...

    For the second identity i need some more time...

    Kind regards

    \chi \sigma
    Last edited by chisigma; April 22nd 2009 at 06:42 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Nov 2008
    Posts
    50
    Thank you a lot for your helpful response. Your solution is very scary for me Pofessor has not taught us the formula that you use. I am sure there is an elegant solution that does not use complicated formulas.
    Quote Originally Posted by chisigma View Post
    If you remember the explicit formula for the Bernuoulli number of index m...

    B_{m}= \sum_{n=0}^{m} \frac{1}{n+1}\cdot \sum_{k=0}^{n} (-1)^{k}\cdot \binom{n}{k}\cdot k^{m}

    ... you can obtain...

    - \frac{1}{6}\cdot \sum_{k=0}^{5}(-1)^{k}\cdot \binom{5}{k}\cdot k^{5} =B_{5} - \sum_{n=0}^{4}\frac{1}{n+1}\cdot \sum_{k=0}^{n}(-1)^{k}\cdot \binom{n}{k}\cdot k^{5}

    ... and you are able to verify the first identity...

    For the second identity i need some more time...

    Kind regards

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

  7. #7
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by andreas View Post
    Please tell me what are the combinatorial arguments that imply:



    5^5- \left(\begin{array}{cc}5\\4\end{array}\right) 4^5+ \left(\begin{array}{cc}5\\3\end{array}\right) 3^5- \left(\begin{array}{cc}5\\2\end{array}\right) 2^5+ \left(\begin{array}{cc}5\\1\end{array}\right) 1^5=5!

    6^4- \left(\begin{array}{cc}6\\5\end{array}\right) 5^4+ \left(\begin{array}{cc}6\\4\end{array}\right) 4^4- \left(\begin{array}{cc}6\\3\end{array}\right) 3^4+ \left(\begin{array}{cc}6\\2\end{array}\right) 2^4- \left(\begin{array}{cc}6\\1\end{array}\right) 1^4=0 .
    Hi Andreas,

    The key phrase in the problem statement is "combinatorial argument". In combinatorics, a "combinatorial argument" or "combinatorial proof" is one that is based on showing a one-to-one relationship between two sets; the two sets must then have the same number of elements. Or perhaps you might take one set and count its members in two different ways; this is also viewed as "combinatorial". The feeling among some mathematicians is that combinatorial proofs exhibit a higher level of understanding than those based on mere computation. (Personally, I have enough trouble finding the merely computational results without looking for additional complications...)

    One way to look at your first example is to let E be the set {1,2,3,4,5}. 5! is the number of bijections from E to E. A function from E to E is a bijection if its range has exactly 5 elements.

    Let's see if we can count the bijections another way.

    5^5 is the number of functions from E to E without any restrictions.
    \binom{5}{4} 4^5 is the number of functions from E to E which have at most 4 distinct elements in their range.
    ...
    \binom{5}{k} k^5 is the number of functions from E to E which have at most k distinct elements in their range, for k = 1,2,3,4.

    So the RHS counts the bijections from E to E, and the LHS takes all the functions from E to E, breaks them out based on the number of elements in their range, and uses these counts to once again count the bijections. The reason for the alternating sum is that the set of all functions contains the set of functions with at most 4 elements in their range, which contains the set of elements with at most 3 elements in their range, etc.

    The second example looks like a similar approach may work there also.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. arguments for the distribution
    Posted in the Statistics Forum
    Replies: 1
    Last Post: June 5th 2010, 08:00 AM
  2. Help... proving arguments.!!!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 17th 2007, 08:53 AM
  3. Please help translate these arguments.....
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 21st 2007, 01:07 PM
  4. Arguments and Logarithms...
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 4th 2007, 08:24 AM
  5. [SOLVED] A Bit Of Help Please. Induction Arguments
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: November 11th 2006, 10:51 AM

Search Tags


/mathhelpforum @mathhelpforum