3
$\begingroup$

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?

1 Answers 1

2

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.

  • 0
    @Joe: You’re welcome.2012-10-17