$r-$ combinaciones de conjuntos múltiples

Question

Tengo el tema $r-$ combinaciones de conjuntos múltiples en mis notas

Sea $S=\{\infty a_1,\infty a_2,\ldots ,\infty a_k\}$ ,
entonces la fórmula para el $r-$ *combinaciones de S* se da como:
$$\binom{r+k-1}{k-1}$$

pero no sé cómo llegamos a la fórmula...
Por favor, ayúdenme con esto...

Answer 1

$r$ - combinaciones de conjuntos múltiples

Puede consultarlo en "Prinicples and Techniques in Combinatorics", un excelente libro de introducción a la combinatoria escrito por Chen Chuan-chong y Koh Khee-Meng.

Se lo reproduciré. Podemos representarnos $r$ -combinación de $M$ considerando cada $a_i$ como una caja. Por ejemplo, el $10$ -combinación $\{3\cdot a_1,2\cdot a_2,0\cdot a_3,\cdots,5\cdot a_k\}$ puede interpretarse como la secuencia binaria $00010011\cdots100000$ como se muestra a continuación. (Hemos utilizado $1$ como separador entre casillas)

$a_1 \;\; |\; a_2 \; | \; a_3 |\; \cdots\; | \;a_k$

$000 \; 1 \; 00 \;\; 1 \;\;\;\;\; 1 \cdots \;\;\;1\; 00000$

Se trata efectivamente de una biyección y, por tanto, el número de $r$ -combinaciones de $M$ es igual al número de secuencias binarias de longitud $r+(n-1)$ [aquí, $n-1$ representa el separador $1$ 's] que contiene $(n-1)$ número de $1$ 's. Este último es $C(r+n-1,n-1)$ .

Answer 2

Creo que te refieres simplemente al coeficiente multinomial. Puedes encontrar una buena derivación en la página de Wikipedia Estrellas y barras sitio.