Foro de preguntas y respuestas de matemáticas, de cualquier nivel. Cuánto más interesantes, divertidas o intrépidas, mejor.
Aviso: Te invitamos a conocer la página de Facebook de la UCIM

Ganas puntos al hacer preguntas, contestarlas y, sobre todo, si tu respuesta es seleccionada como la mejor.
Registrate como usuario para participar en el foro. También puedes utilizar tu identidad de FB Utiliza el botón azul para ingresar (si usas tu identidad de FB y estás logeado en FB, automáticamente te reconoce).

El irracional tiene una página en FB. El Irracional






+1 voto
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) $
por (1,3m puntos) en Básicas
editado por
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.

1 Respuesta

+1 voto
 
Mejor respuesta
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)$.
por (8m puntos)
seleccionada por
Licencia Creative Commons
Este obra está bajo una Licencia Creative Commons Atribución-NoComercial-CompartirIgual 2.5 México.

powered by UCIM

...