0
$\begingroup$

Prove that $$1!\cdot S(n, 1) + 2!\cdot S(n, 2) + \cdots + k!\cdot S(n,k) = k^n,$$

where $k!\cdot S(n,k)$ represents the number of ways to place $n$ distinct objects into $k$ distinct boxes.

Answer: The right-hand side counts the number of ways to place $n$ objects into $k$ boxes.

Each term on the left-hand side is counting the number for of ways to place $n$ distinct objects into $i$ distinct boxes, for $i = 1,2,3,\ldots, k$.

However, my problem is why does the sum of the $i!\cdot S(n,i)$ terms result in the right-hand side?

$\endgroup$

1 Answer 1

1
$\begingroup$

Left hand side and right hand side are not equal.

$ \displaystyle 1!\cdot S(n, 1) + 2!\cdot S(n, 2) + \cdots + k!\cdot S(n,k) \ne k^n$

Rather,

$ \displaystyle {k \choose 1} \cdot 1!\cdot S(n, 1) + {k \choose 2} \cdot 2!\cdot S(n, 2) + \cdots + {k \choose k} \cdot k!\cdot S(n,k) = k^n$

Right hand side: $k^n$ is count of ways to place $n$ distinct objects into $k$ distinct boxes where each object has choice of $k$ boxes. In other words, the count will include cases where all objects are placed into one single box and rest are empty, placed into two boxes and rest are empty and so on.

Left hand side: $ ~ {k \choose i} \cdot i! \cdot S(n, i)$ counts number of ways of placing $n$ objects into $i$ boxes chosen out of $k$ boxes and rest of the boxes are empty. When you sum them for all $i$ between $1$ and $k$, that would be equivalent to RHS.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .