Combinatorial Proof

Give a combinatorial proof of this identity: $$n(n+1)2^{n-2} = \sum_{k=1}^n k^2 {n \choose k}$$ Solution

Let's say in a class there are $n$ students and you are asked to select one or more students, with the caveat that Joe must be selected. For each student that is selected, the whole class gets 1 dollar. So what is the expected value of the class' income?

Or if you want a non-probabilistic way to think about it, then over all the possible ways to select students, what is the sum of class income in all of those scenarios?

First way to count: Say there are $k \geq 1$ students who are selected (including Joe). There are $n-1 \choose k-1$ ways to choose the students (because Joe must be selected). So this particular way of selecting the students has $k {n-1 \choose k-1} = \frac{k^2}{n} {n \choose k}$ income. So the sum of all income over all scenarios is $\sum_{k=1}^n \frac{k^2}{n} {n \choose k}$

Second way to count: Consider a student, not Joe. How many dollars does he contribute to the total class income? He contributes 1 dollar everytime he is selected, which is $2^{n-2}$ times (because both he and Joe must be selected for him to contribute, so the other $n-2$ students can be chosen freely, selected or not selected). There are $(n-1)2^{n-2}$ contributions from these, because there are $n-1$ students that are not Joe.

But how many dollars did Joe contribute? He ALWAYS contributes 1 dollar for every selection, and there are $2^{n-1}$ selections total. So there are $2^{n-1}$ contributions from Joe.

So the total contribution is $(n-1)2^{n-2} + 2^{n-1} = (n+1)2^{n-2}$

ABC String

How many strings of A's, B's, and C's are there that satisfy the following conditions:

1. There are $n$ A's and $2n$ total of B's and C's.

2. Every two adjacent letters are different.

2 Variable Recursion

This problem is written as an auxiliary lemma for the solution to this problem.

Suppose $f(m,n)$ is a function that is defined for non-negative integers $m,n$ where:

$f(m,n) = 0$ if $m < n$

$f(m,0) = 1 \forall m$

$\displaystyle f(m,n) = \sum_{k=1}^{n} f(k-1,k-1) f(m-k,n-k) + f(m-1,n) \forall m \geq n$

Prove that $f(m,n) = \frac{m-n+1}{m+1} \binom{m+n}{m}$