1
$\begingroup$

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)}$$

$\endgroup$
0
$\begingroup$

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*}

$\endgroup$
  • $\begingroup$ I did this also but doesn't this include algebraic manipulation though? I wrote about this is in the explanation and I wasn't sure whether I could use this, whether it clashes with the idea of combinatorial proof. I'm just asking because I am not sure. $\endgroup$ – Stefan M. May 17 at 15:19
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.