# Factorial Identity - True or False?

Let $x$ and $y$ be positive integers. Then, is

\begin{align} \frac{x^{xy}}{(xy)!} = \sum_{k_1+...+k_x = xy} \frac{1}{(k_1)!...(k_x)!} \end{align}

true, where $k_1$, ..., $k_x$ are all positive integers? If so, what kind of approach should I take to prove it?

-

There are $x^{xy}$ sequences $\langle a_1,a_2,\dots,a_{xy}\rangle$ such that $a_k\in\{1,\dots,x\}$ for $k=1,\dots,xy$; let $S$ be the set of such sequences. For each $s\in S$ and each $i\in\{1,\dots,x\}$ let $k_i(s)$ be the number of $i$’s in $s$; clearly $k_1(s)+k_2(s)+\ldots+k_x(s)=xy$. For each $x$-tuple $\vec \ell=\langle \ell_1,\dots,\ell_x\rangle$ of non-negative integers such that $\ell_1+\ldots+\ell_x=xy$ let $$S(\vec \ell)=\{s\in S:k_i(s)=\ell_i\text{ for }i=1\dots,x\}\;.$$ Then

$$|S(\vec\ell)|=\binom{xy}{\ell_1,\dots,\ell_x}=\frac{(xy)!}{\ell_1!\ell_2!\dots\ell_x!}\;.$$

Can you put this information together to prove the identity? There’s still a bit of work to be done, but I’ve given you all of the main pieces.

-
Thanks. This is very clear. – tatterdemalion Oct 17 '12 at 4:52
@Joe: You’re welcome. – Brian M. Scott Oct 17 '12 at 4:56