$\sum_{k=1}^n \binom{n}{a_1,a_2, \cdots , a_k} \binom mk \binom{k}{b_1,b_2, \cdots , b_l}= m^n,$

Question

(Propio) Que $n,m$ ser enteros positivos tales que $m>n$. Demostrar que $$\sum_{k=1}^n \sum_{a_1+a_2 + \cdots +a_k=n} \binom{n}{a_1,a_2, \cdots , a_k} \binom mk \binom{k}{b_1,b_2, \cdots , b_l}= m^n,$$ where $1 \le a_i \; (1 \le i \le k) $ and $ a_1, a_2 + \cdots + a_k = n$. Aquí, $b_i$ es el número de $a_x \; (1 \le x \le k)$ que tienen el mismo valor. Por ejemplo, si $n=6$ y $6=3+1+1+1$ y $b_i$ $1$ es (un número $3$) y $3$ (tres números $1$).

Answer 1

Podemos probar esta igualdad por la reduce a un recuento problema, a saber: De cuántas maneras podemos poner $n$ distintos objetos en $m$ cajas distintas?

Este número es obviamente igual a $m^n$. Ahora, podemos encontrar el lado izquierdo de la igualdad mediante la siguiente estrategia de conteo:

1. Nota primero que desde $n<m$, se utiliza en la mayoría de las $n$ de la $m$ cajas.
2. Para cada una de las $k\in\{1,\ldots, n\}$, que nos permiten contar el número de maneras de organizar la $n$ objetos utilizando exactamente $k$ de las cajas. A continuación, le suma sobre todos los posibles $k$.
3. Fijar un $k$ ahora. Hay exactamente $\binom{m}{k}$ formas de elegir los $k$ cajas entre las $m$.
4. Para cada elección de $k$ cajas, ahora debemos contar el número de maneras de organizar la $n$ objetos en el interior de estas cajas. Primero escogemos cuántos objetos hay en cada una de las $k$ cajas: decir $c_1$ en el cuadro $1$, ..., $c_k$ en el cuadro de $k$. Así tenemos a $c_1+\ldots+c_k = n$, con cada una de las $c_i>1$. El número de maneras de organizar los objetos en estos $k$ cajas es, a continuación,$\binom{n}{c_1,\ldots, c_k}$. Tomamos la suma de estos números sobre todos los posibles ordenó particiones $c_1, \ldots, c_k$$n$.
5. Finalmente, podemos reescribir esta última suma de la siguiente manera. En lugar de tomar la suma de todos los ordenó particiones, vamos a tener más de todos los no-ordenó particiones $a_1, \ldots, a_k$$n$, y multiplicar el resultado por el número de maneras de ordenar. Este número, usando las notaciones de la cuestión, es exactamente $\binom{k}{b_1, \ldots, b_\ell}$.

Poniendo todo esto junto, obtenemos que el número de maneras de poner $n$ distintos objetos en $m$ cajas distintas es $$ \sum_{i=1}^n \sum_{a_1+\ldots + a_k=n} \binom{m}{k}\binom{n}{a_1, \ldots, a_k}\binom{k}{b_1, \ldots, b_\ell}, $$ donde la segunda suma se toma sobre todos los no-ordenó particiones de $n$ exactamente $k$ enteros positivos $a_1, \ldots, a_k$. Esto termina la prueba.

Answer 2

Supongamos que usted necesita para producir n números, c_1,..., c_n, cada uno de ellos entre 1 y m.

Usted puede hacerlo de esta manera -

1. Seleccionar los k, el número de los distintos números enteros en la lista
2. Elija k distintos números entre 1 y m
3. Seleccione el número de veces que a_i los números aparecerán
4. Elija una correspondencia de la cuenta a_i a los k números, observando que necesitamos para que coincida con distintas en cuenta - elegir b_i números de los k para cada uno de los distintos contar
5. Elegir las posiciones de todos estos k números

Este es el lado izquierdo.

También el número de maneras es m^n, que es la rhs.