Combinaciones sin repetición
Dados un conjunto de \(m\) elementos, las combinaciones sin repetición o simplemente combinaciones de \(m\) elementos tomados de \(n\) en \(n\) son los distintos subconjuntos de \(n\) elementos distintos que podemos hacer con los \(m\) elementos que tenemos, de forma que dos subconjuntos se diferencian solo en algún elemento y no en el orden de colocación. Se representan mediante la notación \( C_{m,n}\) o \(C_m^n\) .
Cada conjunto formado por \(n\) elementos distintos elegidos de entre los \(m\) dados da lugar a variaciones distintas de \(m\) elementos elegidos de \(n\) en \(n\). Es decir:
\[V_{m,n} = C_{m,n} \cdot P_m \Rightarrow C_{m,n} = \displaystyle \frac{V_{m,n}}{P_n} = \displaystyle \frac{m!}{n! \cdot (m-n)!}\]
\begin{equation} \boxed{C_{m,n} = C_m^n= \begin{pmatrix} m \\ n \end{pmatrix} } \end{equation}
Combinaciones con repetición
Dado un conjunto de \(m\) elementos, las combinaciones con repetición de \(m\) elementos tomados de \(n\) en \(n\) \((n \leq m) \) son los distintos subconjuntos de \(n\) elementos iguales o distintos que podemos hacer con los \(m\) elementos que tenemos, de forma que dos subconjuntos se diferencian solo en algún elemento y no en el orden de colocación. Se representan mediante la notación \(CR_{m,n}\) o \( CR_m^n\) .
El valor del número de variaciones sin repetición de m elementos tomados de n en n se calcula utilizando la expresión:
\begin{equation} \boxed{CR_{m,n} = CR_m^n = C_{m+n-1,n} = \begin{pmatrix} m+n-1 \\ n \end{pmatrix} =\displaystyle \frac{(m+n-1)!}{n! \cdot (m-1)!} } \end{equation}
Ejemplo:
Tomemos el conjunto \(A=\{a, e, i, o, u\}\). Vamos a construir todas la combinaciones con repetición posibles:
De 1 elemento. \(\{a\}\), \(\{e\}\), \(\{i\}\), \(\{o\}\), \(\{u\}\). El número de combinaciones posibles es 5. Para la combinación \(\{a\}\) podemos usar la siguiente representación \( \underbrace{1}_a 0000 \)
Para la combinación \(\{e\}\) podemos usar la siguiente representación \( 0\underbrace{1}_e 000 \)
Para la combinación \(\{i\}\) podemos usar la siguiente representación \( 00 \underbrace{1}_i 00 \)
Para la combinación \(\{o\}\) podemos usar la siguiente representación \( 000\underbrace{1}_o 0 \)
Para la combinación \(\{u\}\) podemos usar la siguiente representación \( 0000\underbrace{1}_u \)
Se observa que el número de combinaciones es precisamente el número formas de colocar 1 uno en 5 posiciones distintas, es decir, \( \begin{pmatrix} 5 \\ 1 \end{pmatrix} \), donde estas posiciones están diferenciadas por los 0.
De 2 elementos. Si añadimos un elemento más a las combinaciones que hemos obtenido de 1 elemento, tendremos:
\[\{aa\}, \{ae\}, \{ai\}, \{ao\}, \{au\}, \{ee\}, \{ei\}, \{eo\}, \]
\[\{eu\}, \{ii\}, \{io\}, \{iu\} \{oo\}, \{ou\}, \{uu\}\]
Recordando que el orden no importa. El número de combinaciones de 5 elementos tomados de 2 en 2 es 15\(\{aa\}\) la podemos representar por \( \underbrace{1,1}_a 0000 \)
\(\{ae\}\) la podemos representar por \( \underbrace{1}_a 0 \underbrace{1}_{e} 000\)
y así sucesivamente.
Se observa que el número de combinaciones es precisamente el número formas de colocar 2 unos en 6 posiciones distintas, es decir, \( \begin{pmatrix} 6 \\ 2 \end{pmatrix} \)
De 3 elementos. Si añadimos un elemento más a las combinaciones que hemos obtenido de 2 elemento, tendremos:
\[ \{aaa\}, \{aae\}, \{aai\}, \{aao\}, \{aau\}, \{aee\}, \{aei\}, \]
\[ \{aeo\}, \{aeu\}, \{aii\}, \{aio\}, \{aiu\}, \{aoo\}, \{aou\}, \]
\[\{auu\}, \{eee\}, \{eei\}, \{eeo\}, \{eeu\}, \{eii\}, \{eio\},\]
\[ \{eiu\}, \{eoo\}, \{eou\}, \{euu\}, \{iii\}, \{iio\}, \{iiu\},\]
\[\{ioo\}, \{iou\}, \{iuu\}, \{ooo\}, \{oou\}, \{ouu\}, \{uuu\} \]
Recordando que el orden no importa. El número de combinaciones de 5 elementos tomados de 3 en 3 es 35\(\{aaa\}\) la podemos representar por \( \underbrace{1,1,1}_{a} 0000 \)
\(\{aae\}\) la podemos representar por \(\underbrace{1,1}_{a} 0 \underbrace{1}_e 000\)
\(\{eio\}\) la podemos representar por \( 0 \underbrace{1}_e 0 \underbrace{1}_i 0 \underbrace{1}_o 0 \)
y así sucesivamente.
Se observa que el número de combinaciones es precisamente el número formas de colocar 3 unos en 7 posiciones distintas, es decir \( \begin{pmatrix} 7 \\ 3 \end{pmatrix} \)
Podemos obtener todas las combinaciones de esta forma. Recopilando información:
\[CR_5^1 \rightarrow \underbrace{}_a 0\underbrace{}_e 0\underbrace{}_i 0 \underbrace{}_u 0 \underbrace{}_o \rightarrow \begin{pmatrix} 5-1 +1 \\ 1 \end{pmatrix} = 5 \]
\[CR_5^2 \rightarrow \underbrace{}_{aa} 0\underbrace{}_{ee} 0\underbrace{}_{ii} 0 \underbrace{}_{oo} 0 \underbrace{}_{uu} \rightarrow \begin{pmatrix} 5-1 + 2 \\ 2 \end{pmatrix} = 15 \]
\[CR_5^3 \rightarrow \underbrace{}_{aaa} 0\underbrace{}_{eee} 0\underbrace{}_{iii} 0 \underbrace{}_{ooo} 0 \underbrace{}_{uuu} \rightarrow \begin{pmatrix} 5-1 + 3 \\ 3 \end{pmatrix} = 35 \]
Y así sucesivamente.
Donde observamos el patrón \( CR_m^n = C_{m-1+n}^n = \begin{pmatrix} m-1 + n \\ n \end{pmatrix} \)
