Combinaciones con repetición

Question

Sean $k, n \in \mathbb{N}$, $k ≤ n$, $K:=\{1, ..., k\}$, $N:=\{1, ..., n\}$.
Definimos $P_{k}^{n}(cR):=\{(a_1, ..., a_k) | \forall i\in K, a_i \in N \}$ (El conjunto de permutaciones de n elementos en k lugares con repetición).
$C_{k}^{n}(cR):= \{(a_1, ..., a_k) \in P_{k}^{n}(cR) | \forall r, s \in K, r < s \rightarrow a_r \leq a_s \}$ (el conjunto de las combinaciones de n elementos en k lugares con repetición).
Probar que
$| C_{k}^{n}(cR) | = \left( \begin{array}{center} n+k-1 \\ k \end{array} \right) $

Comments

Me parece que hay un error en el enunciado, debe decir, en la definición de $C_k^n$: $r<s\to a_r\leq a_s$, porque si no no hay repeticiones.

---

Es verdad, una disculpa, ya está corregido, gracias por la observación.

Answer 1

Primero que nada, para que sea "con repetición" tienes que tomar en cuenta el comentario de Yarza.

Ahora toma un elemento de $C_k^n$, digamos $a=(a_1,a_2,\ldots,a_k)$. Para cada $i=1,\ldots,n$ define $r_i$ como la cantidad de veces que aparece $i$ en $a$, es decir, $r_i:=|\{j\in K:a_j=i\}|$. Ahora define $f(a)$ como una secuencia que tiene $r_0$ veces 1, luego un 0, luego $r_1$ veces 1, luego un 0, etc. (no hace falta poner un 0 después de los últimos $r_n$ unos).

Por ejemplo si $k=3, n=4, a=(3,3,4)$ se tiene que $f(a)=(0,0,1,1,0,1)$, pues $r_1=0, r_2=0, r_3=2$ y $r_4=1$. Nota que hay $k$ unos y $n-1$ ceros, pues debe haber tantos unos como coordenadas en $a$ y después de los $r_i$ unos hay un 0 excepto por $r_n$.

$f$ es una biyección entre $C_k^n$ y el conjunto $S$ de secuencias de ceros y unos con longitud $n+k-1$ con exactamente $k$ unos. Puedes construir su inversa fácilmente, por darte un ejemplo, a la secuencia en $S$ dada por $(1,1,0,0,1,0)$ le corresponden 2 veces el 1, 0 veces el 2, 1 vez el 3, y 0 veces el 4, es decir $a=(1,1,3)$.

Por lo tanto la cardinalidad de $C_k^n$ es la misma que la de $S$, pero un elemento en $S$ está determinado por en qué posiciones hay 1. De $n+k-1$ posiciones, $k$ deben ser unos, por lo tanto $|C_k^n|=|S|=\left(\begin{array}{c} n+k-1\\ k \end{array}\right)$.