Math Help - Combinatorial arguments

1. 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 .

2. um.... what?

3. How to justify equalities.

4. 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$

5. 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.
Originally Posted by chisigma
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$

6. Originally Posted by andreas
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.