Combinatorial proof: $\sum_k {n+1 \brack k}k = {n+2 \brack 2}$

Question

I need to prove that: $$\sum_k {n+1 \brack k}k = {n+2 \brack 2}$$ I know that this can be done by induction, but this is a bit tedious. Can you think of a combinatorial proof of this theorem?

Literally, the right hand side calculates in how many ways we can seat $n+2$ people at $2$ round tables.

The left hand side calculates in how many ways we can seat $n+1$ people at $k$ circular tables and then add the last person to one of the tables already occupied and then add them together with respect to $k$.

To be honest, I don't see any straightforward connection between these two. Any hints?

Answer 1

HINT: Your interpretation of the left side doesn't match the expression. Here's a different way:

The LHS is the number of ways to pick a permutation of $n+1$ elements and color a cycle.

How can you get this to match the RHS? Notice that the non-colored cycles form a permutation by themselves. Is there a bijection between $m+1$ cycles and $m$ permutations?

Answer 2

I don't have a combinatorial proof but I thought the following algebraic proof is interesting.

Let $$c(x) = x^{\bar n}$$

We have by definition, $\sum_k {n \brack k}x^k = c(x)$

Differentiating, we get:

$$\sum_{k=1}^n k{n \brack k}x^{k-1} = c'(x) = c(x)\left(\frac{1}{x+n-1} + \frac{1}{x+n-2} + ... + \frac{1}{x}\right)$$

Plugging $x=1$, we get

$$\sum_{k=1}^n k{n \brack k} = c(1)\left(\frac{1}{n} + \frac{1}{n-1} + ... + \frac{1}{1}\right)$$

We know $c(1) = n!$

So $$\sum_{k=1}^n k{n \brack k} = n!\left(\frac{1}{n} + \frac{1}{n-1} + ... + \frac{1}{1}\right)$$

Now there is a completely separate proof for: $$n!\left(\frac{1}{n} + \frac{1}{n-1} + ... + \frac{1}{1}\right) = {n+1 \brack 2}$$

Answer 3

Let $A=\{a_1,\cdots,a_m \} $ be a finite set, that does not contain the element $n+1$. We begin by noting a one to one correspondence between permutations of this set and the conjugacy class of $A \cup \{n+1 \}$. Given an element $\pi \in S_A$ ($\pi(a_i)=\pi_{a_i}$) we form an element of $S_{A \cup \{n+1 \}}$ by \begin{eqnarray*} \pi \rightarrow (\pi_{a_1}, \cdots , \pi_{a_m},n+1 ). \end{eqnarray*} We shall now use this to establish the following formula \begin{eqnarray*} \sum_{k=j}^{n} {n \brack k} \binom{k}{j} = {n+1 \brack j+1}. \end{eqnarray*} Let $ \sigma$ be an element of $S_n$ with $k$ cycles. Choose $j$ of these cycles and let $A$ be the set of elements in the other $k-j$ cycles. Now form an element of $S_{n+1}$ consisting of the $k$ chosen cycles and a cycle formed by the correspondence $S_A \rightarrow S_{A \cup \{n+1 \}}$ defined above. Now let $k$ vary over its admissable values and the formula is proven.

To recover the result you require, replace $n$ with $n+1$ and let $j=1$.