Combinatorial proof for an identity

Question

I'm trying to show the equality below using a combinatorial argument. For the left hand side; suppose there are n lands to build houses that can hold 3 families at once. First it counts the ways of building houses with n choose k in summation and then for each case of houses it puts 3 family inside those k houses. If I algebraically change right hand side getting a slightly longer equation, I can show that they are counting the same thing. However, I should be able to do so without changing the right hand side with algebraic manipulations. Can someone help me find the story of the right hand side?

$$\sum_{k=1}^{n} k^3{n \choose k}=n^2(n+3)2^{(n-3)}$$

Answer 1

I think of this expression probabilistically.Let's define a Random variable $X$,which counts the number of heads obtained when an unbiased Coin is thrown n times in a succession independently.So $\mathbb{P}(X=k)=\binom{n}{k}(\frac{1}{2})^n$.So if you multiply the LHS by $(\frac{1}{2})^{n}$ it becomes $\mathbb{E}(X^{3})$.And we know that $\mathbb{E}(X^{3})=\frac{n^{2}(n+3)}{8}$.Then you get the desired RHS.

Answer 2

There are 3 cases.

Case 1: The families occupy $1$ house.

There are $n$ ways to choose the land to build the occupied house.

For the remaining $n-1$ lands, a house can be built or not to be built, so there are $2^{n-1}$ ways.

Hence, there are $n\cdot 2^{n-1}$ ways for Case 1.

Case 2: The families occupy $2$ houses.

There are $n$ ways to choose the land to build the occupied house for $2$ families and then there are $n-1$ ways to choose the land to build the occupied house for $1$ family.

Then there are ${3 \choose 2}=3$ ways to choose $2$ families for the occupied house for $2$ families and the remaining $1$ family for the occupied house for $1$ family.

For the remaining $n-2$ lands, a house can be built or not to be built, so there are $2^{n-2}$ ways.

Hence, there are $n(n-1)\cdot 3\cdot 2^{n-2}=3n(n-1)\cdot 2^{n-2}$ ways for Case 2.

Case 3: The families occupy $3$ houses.

There are $n$ ways to choose the land to build the occupied house for the $1$st family, then there are $n-1$ ways to choose the land to build the occupied house for the $2$nd family and there are $n-2$ ways to choose the land to build the occupied house for the $3$nd family.

For the remaining $n-3$ lands, a house can be built or not to be built, so there are $2^{n-3}$ ways.

Hence, there are $n(n-1)(n-2)\cdot 2^{n-3}$ ways for Case 3.

Combining the 3 cases

\begin{align*} \text{The total number of ways} & =n\cdot 2^{n-1}+3n(n-1)\cdot 2^{n-2}+n(n-1)(n-2)\cdot 2^{n-3} \\ & =n[4+6(n-1)+(n-1)(n-2)]\cdot 2^{n-3} \\ & =n^2(n+3)\cdot 2^{n-3} \\ \end{align*}