1.8: Estructuras combinatorias

\(\newcommand{\N}{\mathbb{N}}\)\(\newcommand{\R}{\mathbb{R}}\)\(\newcommand{\bs}{\boldsymbol}\)

El propósito de esta sección es estudiar varias estructuras combinatorias que son de importancia básica en probabilidad.

Permutaciones

Supongamos que\(D\) es un conjunto con\(n \in \N\) elementos. Una permutación de longitud\(k \in \{0, 1, \ldots, n\}\) de\(D\) es una secuencia ordenada de\(k\) distintos elementos de\(D\); es decir, una secuencia de la forma\((x_1, x_2, \ldots, x_k)\) donde\(x_i \in D\) para cada uno\(i\) y\(x_i \ne x_j\) para\(i \ne j\).

Estadísticamente, una permutación de longitud\(k\) de\(D\) corresponde a una muestra ordenada de tamaño\(k\) elegida sin reemplazo de la población\(D\).

El número de permutaciones de longitud\(k\) de un conjunto de\(n\) elementos es\[ n^{(k)} = n (n - 1) \cdots (n - k + 1) \]

Prueba

Esto se desprende fácilmente del principio de multiplicación. Hay\(n\) formas de elegir el primer elemento,\(n - 1\) formas de elegir el segundo elemento, y así sucesivamente.

Por convención,\(n^{(0)} = 1\). Recordemos que, en general, un producto sobre un conjunto de índices vacío es 1. Tenga en cuenta que\(n^{(k)}\) tiene\(k\) factores, comenzando en\(n\), y con cada factor posterior uno menos que el factor anterior. Algunas notaciones alternativas para el número de permutaciones de tamaño\(k\) de un conjunto de\(n\) objetos son\(P(n, k)\),\(P_{n,k}\), y\({_n}P_k\).

El número de permutaciones de longitud\(n\) del conjunto de\(n\) elementos\(D\) (estas se llaman simplemente permutaciones de\(D\)) es\[ n! = n^{(n)} = n (n - 1) \cdots (1) \]

La función on\( \N \) dada por\( n \mapsto n! \) es la función factorial. La fórmula general de permutación en (2) se puede escribir en términos de factoriales:

Para\(n \in \N\) y\(k \in \{0, 1, \ldots, n\}\)\[ n^{(k)} = \frac{n!}{(n - k)!} \]

Aunque esta fórmula es sucinta, no siempre es una buena idea numéricamente. Si\( n \) y\( n - k \) son grandes,\( n! \) y\( (n - k)! \) son enormes, y la división de la primera por la segunda puede llevar a errores significativos de redondeo.

Tenga en cuenta que la fórmula de permutación básica en (2) se define para cada número real\(n\) y entero no negativo\(k\). A esta extensión se le hace referencia a veces como la fórmula de permutación generalizada. En realidad, a veces necesitaremos una fórmula aún más general de este tipo (particularmente en las secciones de la urna de Pólya y el proceso beta-bernoulli).

Para\(a \in \R\)\(s \in \R\), y\(k \in \N\), definir\[ a^{(s, k)} = a (a + s) (a + 2 s) \cdots [a + (k - 1) s] \]

1. \(a^{(0, k)} = a^k\)
2. \(a^{(-1, k)} = a^{(k)}\)
3. \(a^{(1, k)} = a (a + 1) \cdots (a + k - 1)\)
4. \(1^{(1, k)} = k!\)

El producto\(a^{(-1, k)} = a^{(k)}\) (nuestra fórmula de permutación ordinaria) a veces se llama el poder descendente\(a\) del orden\(k\), mientras que\(a^{(1, k)}\) se llama el poder ascendente\(a\) del orden\(k\), y a veces se denota\( a^{[k]} \). Tenga en cuenta que\(a^{(0, k)}\) es el\(k\) poder ordinario de\(a\). En general, señalar que\(a^{(s, k)}\) tiene\(k\) factores, comenzando en\(a\) y con cada factor posterior obtenido sumando\(s\) al factor anterior.

Combinaciones

Considera de nuevo un conjunto\(D\) con\(n \in \N\) elementos. Una combinación de tamaño\(k \in \{0, 1, \ldots, n\}\) de\(D\) es un subconjunto (desordenado) de\(k\) distintos elementos de\(D\). Así, una combinación de tamaño\(k\) de\(D\) tiene la forma\(\{x_1, x_2, \ldots, x_k\}\), donde\(x_i \in D\) para cada uno\(i\) y\(x_i \ne x_j\) para\(i \ne j\).

Estadísticamente, una combinación de tamaño\(k\) de\(D\) corresponde a una muestra desordenada de tamaño\(k\) elegida sin reemplazo de la población\(D\). Tenga en cuenta que para cada combinación\(k\) de tamaño de\(D\), hay ordenamientos\(k!\) distintos de los elementos de esa combinación. Cada uno de estos es una permutación de longitud\(k\) de\(D\). El número de combinaciones de tamaño\(k\) de un conjunto\(n\) -elemento se denota por\(\binom{n}{k}\). Algunas notaciones alternativas son\(C(n, k)\),\(C_{n,k}\), y\({_n}C_k\).

El número de combinaciones de tamaño\(k\) de un conjunto de\(n\) elementos es\[ \binom{n}{k} = \frac{n^{(k)}}{k!} = \frac{n!}{k! (n - k)!} \]

Prueba

Un algoritmo para generar todas las permutaciones\(k\) de tamaño\(D\) es seleccionar primero una combinación de tamaño\(k\) y luego seleccionar un orden de los elementos. Del principio de multiplicación se deduce eso\(n^{(k)} = \binom{n}{k} k!\). De ahí\( \binom{n}{k} = n^{(k)} / k! = n! / [k! (n - k)!] \).

El número\(\binom{n}{k}\) se denomina coeficiente binomial. Tenga en cuenta que la fórmula tiene sentido para cualquier número real\(n\) y entero no negativo\(k\) ya que esto es cierto para la fórmula de permutación generalizada\(n^{(k)}\). Con esta extensión,\(\binom{n}{k}\) se denomina coeficiente binomial generalizado. Tenga en cuenta que si\(n\) y\(k\) son enteros positivos y\(k \gt n\) luego\(\binom{n}{k} = 0\). Por convención, también definiremos\(\binom{n}{k} = 0\) si\(k \lt 0\). Esta convención a veces simplifica las fórmulas.

Propiedades de los Coeficientes Binomiales

Para algunas de las identidades a continuación, hay dos pruebas posibles. Una prueba algebraica, por supuesto, debe basarse en (5). Se construye una prueba combinatoria mostrando que los lados izquierdo y derecho de la identidad son dos formas diferentes de contar la misma colección.

\(\binom{n}{n} = \binom{n}{0} = 1\).

Álgebraicamente, el último resultado es trivial. También tiene sentido combinatorialmente: Solo hay una forma de seleccionar un subconjunto de\(D\) con\(n\) elementos (\(D\)en sí mismo), y solo hay una forma de seleccionar un subconjunto de tamaño 0 de\(D\) (el conjunto vacío\(\emptyset\)).

Si\(n, \, k \in \N\) con\(k \le n\) entonces\[ \binom{n}{k} = \binom{n}{n - k} \]

Prueba combinatoria

Tenga en cuenta que si seleccionamos un subconjunto\(k\) de tamaño de un conjunto de tamaños\(n\), entonces dejamos\(n - k\) atrás un subconjunto de tamaño (el complemento). Así\(A \mapsto A^c\) es una correspondencia uno a uno entre subconjuntos de tamaño\(k\) y subconjuntos de tamaño\(n - k\).

El siguiente resultado es uno de los más famosos e importantes. Se le conoce como regla de Pascal y lleva el nombre de Blaise Pascal.

Si\(n, \, k \in \N_+\) con\(k \le n\) entonces\[ \binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k} \]

Prueba combinatoria

Supongamos que tenemos\(n\) personas, una llamada Fred, y que queremos seleccionar un comité de tamaño\(k\). Hay\(\binom{n}{k}\) diferentes comisiones. Por otro lado, hay\(\binom{n - 1}{k - 1}\) comités con Fred como miembro, y\(\binom{n - 1}{k}\) comités sin Fred como miembro. La suma de estos dos números es también el número de comisiones.

Recordemos que el tablero Galton es una matriz triangular de clavijas: las filas están numeradas\(n = 0, 1, \ldots\) y las clavijas en fila\(n\) están numeradas\(k = 0, 1, \ldots, n\). Si cada clavija en el tablero Galton es reemplazada por el coeficiente binomial correspondiente, la tabla resultante de números se conoce como triángulo de Pascal, llamado nuevamente por Pascal. Por (8), cada número interior en el triángulo de Pascal es la suma de los dos números directamente encima de él.

El siguiente resultado es el teorema binomial, y es la razón del término coeficiente binomial.

Si\(a, \, b \in \R\) y\(n \in \N\) es un entero positivo, entonces\[ (a + b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k} \]

Prueba combinatoria

Tenga en cuenta que para obtener el término\(a^k b^{n-k}\) en la expansión de\((a + b)^n\), debemos seleccionar\(a\)\(k\) de entre los factores y\(b\) de los\(n - k\) factores restantes. El número de formas de hacerlo es\(\binom{n}{k}\).

Si\(j, \, k, \, n \in \N_+\) con\(j \le k \le n\) entonces\[ k^{(j)} \binom{n}{k} = n^{(j)} \binom{n - j}{k - j} \]

Prueba combinatoria

Considerar dos procedimientos para seleccionar un comité\(k\) de tamaño de un grupo de\(n\) personas, con\(j\) distintos miembros del comité como directivos (presidente, vicepresidente, etc.). Para el primer procedimiento, seleccionar el comité de la población y luego seleccionar al miembro del comité para que sea la Mesa. El número de formas de realizar el primer paso es\(\binom{n}{k}\) y el número de formas de realizar el segundo paso es\(k^{(j)}\). Entonces, por el principio de multiplicación, el número de formas de elegir el comité es el lado izquierdo de la ecuación. Para el segundo procedimiento, seleccionar a la Mesa del Comité de la población y luego seleccionar a\(k - j\) otros integrantes del comité de entre los restantes\(n - j\) integrantes de la población. El número de formas de realizar el primer paso es\(n^{(j)}\) y el número de formas de realizar el segundo paso es\(\binom{n - j}{k - j}\). Entonces, por el principio de multiplicación, el número de comisiones es el lado correcto de la ecuación.

El siguiente resultado se conoce como la identidad de Vandermonde, llamada así por Alexandre-Théophile Vandermonde.

Si\(m, \, n, \, k \in \N\) con\(k \le m + n\), entonces\[ \sum_{j=0}^k \binom{m}{j} \binom{n}{k - j} = \binom{m + n}{k} \]

Prueba combinatoria

Supongamos que\(k\) se elige un comité de tamaño formando un grupo de\(m + n\) personas, compuesto por\(m\) hombres y\(n\) mujeres. El número de comisiones con exactamente\(j\) hombres y\(k - j\) mujeres es\(\binom{m}{j} \binom{n}{k - j}\). La suma de este producto sobre\(j\) es el número total de comisiones, que es\(\binom{m + n}{k}\).

El siguiente resultado es una identidad general para la suma de coeficientes binomiales.

Si\(m, \, n \in \N\) con\( n \le m \) entonces\[ \sum_{j=n}^m \binom{j}{n} = \binom{m + 1}{n + 1}\]

Prueba combinatoria

Supongamos que elegimos un subconjunto\(n + 1\) de tamaño del conjunto\(\{1, 2, \ldots m + 1\}\). For\(j \in \{n, n + 1, \ldots, m\}\), el número de subconjuntos en los que se encuentra el elemento más grande\(j + 1\) es\(\binom{j}{n}\). De ahí que la suma de estos números sobre\(j\) sea el número total de subconjuntos de tamaño\(n + 1\), que también es\(\binom{m + 1}{n + 1}\).

Para una versión aún más general del último resultado, consulte la sección de Estadísticas de Orden en el capítulo sobre Modelos de Muestreo Finito. La siguiente identidad para la suma de los primeros enteros\(m\) positivos es un caso especial del último resultado.

Si\(m \in \N\) entonces\[ \sum_{j=1}^m j = \binom{m + 1}{2} = \frac{(m + 1) m}{2} \]

Prueba

Dejar\(n = 1\) en resultado anterior.

Existe una correspondencia uno a uno entre cada par de las siguientes colecciones. De ahí que el número de objetos en cada una de estas colecciones sea\(\binom{n}{k}\).

1. Subconjuntos de tamaño\(k\) de un conjunto de\(n\) elementos.
2. Cuerdas de bits de longitud\(n\) con exactamente\(k\) 1's.
3. Caminos en el tablero de Galton desde\((0, 0)\) hasta\((n, k)\).

Prueba

Dejar\(S = \{x_1, x_2, \ldots, x_n\}\) ser un conjunto con\(n\) elementos. Una correspondencia uno a uno entre los subconjuntos\(A\) de\(S\) con\(k\) elementos y las cadenas\(\bs{b} = b_1 b_2 \ldots b_n\) de bits de longitud\(n\) con\(k\) 1's puede ser construida por la regla que\(x_i \in A\) si y solo si\(b_i = 1\). A su vez, una correspondencia uno a uno entre las cadenas de bits\(\bs{b}\) en la parte (b) y las rutas en el tablero de Galton en la parte (c) se puede construir mediante la regla de que en fila\(i \in \{0, 1, \ldots, n - 1\}\), gire a la derecha si\(b_{i+1} = 1\) y gire a la izquierda si\(b_{i+1} = 0\).

La siguiente identidad se conoce como la identidad de suma alterna para los coeficientes binomiales. Resulta útil en la distribución de probabilidad Irwin-Hall. Damos la identidad en dos formas equivalentes, una para los poderes decrecientes y otra para los poderes ordinarios.

Si\( n \in \N_+ \),\( j \in \{0, 1, \ldots n - 1\} \) entonces

1. \[ \sum_{k=0}^n \binom{n}{k}(-1)^k k^{(j)} = 0\]
2. \[ \sum_{k=0}^n \binom{n}{k}(-1)^k k^j = 0\]

Prueba

1. Usamos la identidad anterior y el teorema binomial teorema binomial:\ begin {align*}\ sum_ {k=0} ^n (-1) ^k k^ {(j)}\ binom {n} {k} & =\ sum_ {k=j} ^n (-1) ^k k^ {(j)}\ binom {n} {k} =\ sum_ {k_ {=j} ^n (-1) ^k n^ {(j)}\ binom {n - j} {k - j}\\ & = n^ {(j)} (-1) ^j\ suma_ {k=j} ^n (-1) ^ {k-j}\ binom {n - j} {k - j} = n^ {(j)} (-1) ^j\ suma_ {i=0} ^ {n-j} (-1) ^i\ binom {n - j} {i}\\ & = n^ {(j)} (-1) ^j (-1 + 1) ^ {n - j} = 0. \ end {align*} Tenga en cuenta que es el último paso donde necesitamos\( j \lt n \).
2. Esto se desprende de (a), ya que\( k^j \) es una combinación lineal de\( k^{(i)} \) for\( i \in \{0, 1, \ldots j\} \). Es decir, existe\( c_i \in \R \) para\( i \in \{0, 1, \ldots, j\} \) tal que\( k^j = \sum_{i=0}^j c_i k^{(i)} \). De ahí\[ \sum_{k=0}^n (-1)^k k^j \binom{n}{k} = \sum_{i=0}^j c_i \sum_{k=0}^n (-1)^k k^{(i)} \binom{n}{k} = 0 \]

Nuestra siguiente identidad trata de un coeficiente binomial generalizado.

Si\(n, \, k \in \N\) entonces\[ \binom{-n}{k} = (-1)^k \binom{n + k - 1}{k}\]

Prueba

Tenga en cuenta que\ begin {align}\ binom {-n} {k} & =\ frac {(-n) ^ {(k)}} {k!} =\ frac {(-n) (-n - 1)\ cdots (-n - k + 1)} {k!} \\ & = (-1) ^k\ frac {(n + k - 1) (n + k - 2)\ cdots (n)} {k!} = (-1) ^k\ frac {(n + k - 1) ^ {(k)}} {k!} = (-1) ^k\ binom {n + k - 1} {k}\ end {align}

En particular, tenga en cuenta que\(\binom{-1}{k} = (-1)^k\). Nuestro último resultado en esta discusión se refiere al operador binomial y su inverso.

El operador binomial toma una secuencia de números reales\(\bs a = (a_0, a_1, a_2, \ldots)\) y devuelve la secuencia de números reales\(\bs b = (b_0, b_1, b_2, \ldots)\) por medio de la fórmula\[b_n = \sum_{k=0}^n \binom{n}{k} a_k, \quad n \in \N\] El operador binomial inverso recupera la secuencia\(\bs a\) de la secuencia\(\bs b\) por medio de la fórmula\[a_n = \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} b_k, \quad n \in \N\]

Prueba

Las funciones de generación exponencial se pueden utilizar para una prueba elegante. Las funciones de generación exponencial son el equivalente combinatorio de las funciones de generación de momento para distribuciones de probabilidad discretas en\(\N\). Así que vamos\(G\) y\(H\) denotan las funciones generadoras exponenciales de las secuencias\(\bs a\) y\(\bs b\), resepectivamente. Entonces\ comienza {alinear*} H (x) & =\ sum_ {n=0} ^\ infty\ frac {b_n} {n!} x^n =\ suma_ {n=0} ^\ infty\ frac {1} {n!} \ suma_ {k=0} ^n\ binom {n} {k} a_k x^n =\ suma_ {k=0} ^\ infty\ suma_ {n=k} ^\ infty\ frac {1} {n!} \ frac {n!} {k! (n - k)!} a_k x^n\\ & =\ suma_ {k=0} ^\ infty\ frac {1} {k!} a_k x^k\ suma_ {n=k} ^\ infty\ frac {1} {(n-k)!} x^ {n-k} = e^x\ suma_ {k=0} ^\ infty\ frac {1} {k!} a_k x^k = e^x G (x)\ end {align*} Así se deduce que\ begin {align*} G (x) & = e^ {-x} H (x) =\ sum_ {k=0} ^\ infty\ frac {1} {k!} b_k x^k\ suma_ {n=k} ^\ infty\ frac {1} {(n - k)!} (-1) ^ {n-k} x^ {n-k}\\ & =\ suma_ {k=0} ^\ infty\ suma_ {n=k} ^\ infty\ frac {1} {n!} \ frac {n!} {k! (n - k)!} (-1) ^ {n-k} b_k x^n =\ suma_ {n=0} ^\ infty\ frac {1} {n!} \ sum_ {k = 0} ^n\ binom {n} {k} (-1) ^ {n-k} b_k x^n\ end {align*} Pero por definición,\[G(x) = \sum_{n=0}^\infty \frac{a_n}{n!} x^n\] y así sigue la fórmula inversa.

Muestras

El experimento de dibujar una muestra de una población es básico e importante. Hay dos atributos esenciales de las muestras: si el orden es importante o no, y si un objeto muestreado es reemplazado o no en la población antes del siguiente sorteo. Supongamos ahora que la población\(D\) contiene\(n\) objetos y nos interesa dibujar una muestra de\(k\) objetos. Repasemos lo que sabemos hasta ahora:

• Si el orden es importante y se reemplazan los objetos muestreados, entonces las muestras son solo elementos del conjunto de productos\(D^k\). De ahí que el número de muestras sea\(n^k\).
• Si el orden es importante y los objetos de muestra no se reemplazan, entonces las muestras son solo permutaciones de tamaño\(k\) elegido de\(D\). De ahí que el número de muestras sea\(n^{(k)}\).
• Si el orden no es importante y los objetos de muestra no se reemplazan, entonces las muestras son solo combinaciones de tamaño\(k\) elegidas\(D\). De ahí que el número de muestras sea\(\binom{n}{k}\).

Así, nos queda un caso por considerar.

Muestras desordenadas con reemplazo

Una muestra desordenada elegida con reemplazo de\(D\) se llama multiset. Un multiset es como un conjunto ordinario excepto que los elementos pueden repetirse.

Existe una correspondencia uno a uno entre cada par de las siguientes colecciones:

1. Conjuntos múltiples de tamaño\(k\) a partir de una población\(D\) de\(n\) elementos.
2. Cuerdas de bits de longitud\(n + k - 1\) con exactamente\(k\) 1s.
3. Soluciones enteras no negativas\((x_1, x_2, \ldots, x_n)\) de la ecuación\(x_1 + x_2 + \cdots + x_n = k\).

Cada una de estas colecciones tiene\( \binom{n + k - 1}{k} \) miembros.

Prueba

Supongamos que\(D = \{d_1, d_2, \ldots, d_n\}\). Considera un multiset de tamaño\(k\). Dado que el orden no importa, podemos enumerar todas las ocurrencias de\(d_1\) (si las hay) primero, luego las ocurrencias de\(d_2\) (si las hay), y así sucesivamente, hasta que por fin enumeremos las ocurrencias de\(d_n\) (si las hay). Si sabemos que estamos usando esta estructura de datos, en realidad no tenemos que enumerar los elementos reales, simplemente podemos usar 1 como marcador de posición con 0 como separador. En la cadena de bits resultante, 1 ocurre\(k\) veces y 0 ocurre\(n - 1\) veces. Por el contrario, cualquier cadena de bits define de manera única un multiconjunto de tamaño\(k\). A continuación, dado un multiset de tamaño\( k \) desde\( D \), vamos a\(x_i\) denotar el número de veces que\( d_i \) ocurre, para\( i \in \{1, 2, \ldots, n\} \). Entonces\((x_1, x_2, \ldots, x_n)\) satisface las condiciones en (c). Por el contrario, cualquier solución a la ecuación en (c) define de manera única un multiconjunto de tamaño\( k \) de\( D \). Ya sabemos contar la colección en (b): el número de cadenas de bits de longitud\( n + k - 1 \) con 1\( k \) veces que ocurren es\( \binom{n + k - 1}{k} = \binom{n + k - 1}{n - 1} \).

Resumen de fórmulas de muestreo

En la siguiente tabla se resumen las fórmulas para el número de muestras de tamaño\(k\) elegidas de una población de\(n\) elementos, con base en los criterios de orden y reemplazo.

Fórmulas de muestreo

Número de Muestras	Con orden	Sin
Con reemplazo	\(n^k\)	\(\binom{n + k - 1}{k}\)
Sin	\(n^{(k)}\)	\(\binom{n}{k}\)

Coeficientes Multinomiales

Particiones de un conjunto

Recordemos que el coeficiente binomial\(\binom{n}{j}\) es el número de subconjuntos de tamaño\(j\) de un conjunto\(S\) de\(n\) elementos. Tenga en cuenta también que cuando seleccionamos un subconjunto\(A\) de tamaño\(j\) de\(S\), efectivamente particionamos\(S\) en dos subconjuntos disjuntos de tamaños\(j\) y\(n - j\), a saber,\(A\) y\(A^c\). Una generalización natural es \(S\)dividir en una unión de\(k\) distintos subconjuntos disjuntos por pares\((A_1, A_2, \ldots, A_k)\) donde\(\#(A_i) = n_i\) para cada uno\(i \in \{1, 2, \ldots, k\}\). Por supuesto que debemos tener\(n_1 + n_2 + \cdots + n_k = n\).

El número de formas de dividir un conjunto de\( n \) elementos en una secuencia de\( k \) conjuntos de tamaños\( (n_1, n_2, \ldots, n_k) \) es\[ \binom{n}{n_1} \binom{n - n_1}{n_2} \cdots \binom{n - n_1 - \cdots - n_{k-1}}{n_k} = \frac{n!}{n_1! n_2! \cdots n_k!} \]

Prueba

El lado izquierdo se desprende de la regla de multiplicación. Hay\(\binom{n}{n_1}\) formas de seleccionar el primer conjunto en la partición,\(\binom{n - n_1}{n_2}\) formas de seleccionar el segundo conjunto en la partición, y así sucesivamente. El lado derecho sigue escribiendo los coeficientes binomiales a la izquierda en términos de factoriales y simplificación.

El número en (18) se denomina coeficiente multinomial y se denota por\[ \binom{n}{n_1, n_2, \cdots, n_k} = \frac{n!}{n_1! n_2! \cdots n_k!} \]

Si\(n, \, k \in \N\) con\(k \le n\) entonces\[ \binom{n}{k, n - k} = \binom{n}{k}\]

Prueba combinatoria

Como se señaló anteriormente, si seleccionamos un subconjunto de tamaño\(k\) de un conjunto de\(n\) elementos, entonces particionamos el conjunto en dos subconjuntos de tamaños\(k\) y\(n - k\).

Secuencias

Considera ahora el conjunto\(T = \{1, 2, \ldots, k\}^n\). Los elementos de este conjunto son secuencias de longitud\(n\) en las que cada coordenada es uno de\(k\) los valores. Así, estas secuencias generalizan las cadenas de bits de longitud\(n\). Nuevamente, dejar\((n_1, n_2, \ldots, n_k)\) ser una secuencia de enteros no negativos con\(\sum_{i=1}^k n_i = n\).

Existe una correspondencia uno a uno entre las siguientes colecciones:

1. Particiones de\(S\) en subconjuntos disjuntos por pares\((A_1, A_2, \ldots, A_k)\) donde\(\#(A_j) = n_j\) para cada uno\(j \in \{1, 2, \ldots, k\}\).
2. Secuencias\(\{1, 2, \ldots, k\}^n\) en las que\(j\) ocurre\(n_j\) tiempos para cada uno\(j \in \{1, 2, \ldots, k\}\).

Prueba

Supongamos que\(S = \{s_1, s_2, \ldots, s_n\}\). Una correspondencia uno a uno entre una partición\((A_1, A_2, \ldots, A_k)\) del tipo en (a) y una secuencia\(\bs{x} = (x_1, x_2, \ldots, x_n)\) del tipo en (b) puede ser construida por la regla que\(s_i \in A_j\) si y solo si\(x_i = j\).

De ello se deduce que el número de elementos en ambas colecciones es\[ \binom{n}{n_1, n_2, \cdots, n_k} = \frac{n!}{n_1! n_2! \cdots n_k!} \]

Permutaciones con objetos indistinguibles

Supongamos ahora que tenemos\(n\) objeto de\(k\) diferentes tipos, con\(n_i\) elementos de tipo\(i\) para cada uno\(i \in \{1, 2, \ldots, k\}\). Además, los objetos de un tipo dado se consideran idénticos. Existe una correspondencia uno a uno entre las siguientes colecciones:

1. Secuencias\(\{1, 2, \ldots, k\}^n\) en las que\(j\) ocurre\(n_j\) tiempos para cada uno\(j \in \{1, 2, \ldots, k\}\).
2. Permutaciones distinguibles de los\(n\) objetos.

Prueba

Una correspondencia uno a uno entre una secuencia\(\bs{x} = (x_1, x_2, \ldots, x_n)\) del tipo en (a) y una permutación de los\(n\) objetos puede ser construida por la regla de que colocamos un objeto de tipo\(j\) en posición\(i\) si y solo si\(x_i = j\).

Una vez más, se deduce que el número de elementos en ambas colecciones es\[ \binom{n}{n_1, n_2, \cdots, n_k} = \frac{n!}{n_1! n_2! \cdots n_k!} \]

El Teorema Multinomial

El siguiente resultado es el teorema multinomial que es la razón del nombre de los coeficientes.

Si\(x_1, \, x_2, \ldots, x_k \in \R\) y\(n \in \N\) luego\[ (x_1 + x_2 + \cdots + x_k)^n = \sum \binom{n}{n_1, n_2, \cdots, n_k} x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k} \] La suma está sobre secuencias de enteros no negativos\((n_1, n_2, \ldots, n_k)\) con\( n_1 + n_2 + \cdots + n_k = n\). Hay\(\binom{n + k - 1}{n}\) términos en esta suma.

Prueba combinatoria

Tenga en cuenta que para entrar\(x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k}\) en la expansión de\((x_1 + x_2 + \cdots x_k)^n\), debemos elegir\(x_i\) en\(n_i\) de los factores, para cada uno\(i\). El número de formas de hacerlo es el coeficiente multinomial\(\binom{n}{n_1, n_2, \ldots, n_k}\). El número de términos en la suma se desprende de la fórmula anterior.

Ejercicios Computacionales

Arreglos

En una carrera con 10 caballos se anotan los finalistas del primer, segundo y tercer lugar. ¿Cuántos resultados hay?

Responder

\(720\)

Ocho personas, que constan de cuatro parejas macho-mujer, se sentarán en fila de ocho sillas. Cuántas disposiciones de asientos hay en cada uno de los siguientes casos:

1. No hay otras restricciones.
2. Los hombres deben sentarse juntos y las mujeres deben sentarse juntas.
3. Los hombres deben sentarse juntos.
4. Cada pareja debe sentarse junta.

Responder

1. \(40 \, 320\)
2. \(1152\)
3. \(2880\)
4. \(384\)

Supongamos que la\(n\) gente va a estar sentada en una mesa redonda. ¿Cuántos asientos hay? El significado matemático de una mesa redonda es que no hay una primera silla dedicada.

Responder

\((n - 1)!\). Asiento uno, persona distinguida arbitrariamente. Cada disposición de los asientos se puede especificar dando la posición de una persona (digamos en el sentido de las agujas del reloj) en relación con la persona distinguida.

Doce libros, que consisten en 5 libros de matemáticas, 4 libros de ciencias y 3 libros de historia, están dispuestos en una estantería. Encuentra el número de arreglos en cada uno de los siguientes casos:

1. No hay restricciones.
2. Los libros de cada tipo deben estar juntos.
3. Los libros de matemáticas deben estar juntos.

Responder

1. \(479 \, 001 \, 600\)
2. \(103 \, 680\)
3. \(4 \, 838 \, 400\)

Encuentra el número de arreglos distintos de las letras en cada una de las siguientes palabras:

1. estadísticas
2. probabilidad
3. mississippi
4. tennessee
5. Alabama

Responder

1. \(50 \, 400\)
2. \(9\,979\,200\)
3. \(34\,650\)
4. \(3780\)
5. \(210\)

Un niño tiene 12 cuadras; 5 son rojas, 4 son verdes y 3 son azules. ¿De cuántas maneras se pueden organizar los bloques en una línea si los bloques de un color dado se consideran idénticos?

Responder

\(27\,720\)

Palabras de código

Una etiqueta de licencia consta de 2 letras mayúsculas y 5 dígitos. Encuentra el número de etiquetas en cada uno de los siguientes casos:

1. No hay otras restricciones
2. Las letras y los dígitos son todos diferentes.

Responder

1. \(67\,600\,000\)
2. \(19\,656\,000\)

Comités

Un club cuenta con 20 miembros; 12 son mujeres y 8 son hombres. Se elegirá un comité de 6 integrantes. Encuentra el número de comisiones diferentes en cada uno de los siguientes casos:

1. No hay otras restricciones.
2. El comité deberá tener 4 mujeres y 2 hombres.
3. El comité deberá tener al menos 2 mujeres y al menos 2 hombres.

Responder

1. \(38\,760\)
2. \(13\,860\)
3. \(30\,800\)

Supongamos que un club con 20 miembros planea formar 3 comités distintos con 6, 5 y 4 miembros, respectivamente. De cuántas maneras se puede hacer esto.

Responder

\(9\,777\,287\,520\). Obsérvese que los integrantes que no forman un comité también forman uno de los conjuntos en la partición.

Tarjetas

Una baraja de cartas estándar puede ser modelada por el conjunto de productos cartesianos\[ D = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, j, q, k\} \times \{\clubsuit, \diamondsuit, \heartsuit, \spadesuit\} \] donde la primera coordenada codifica la denominación o tipo (as, 2-10, jack, reina, rey) y donde la segunda coordenada codifica el palo (palos, diamantes, corazones, espadas). A veces representamos una carta como una cadena en lugar de un par ordenado (por ejemplo\(q \heartsuit\)).

Una mano de póquer (en el póquer al azar) consiste en 5 cartas repartidas sin reemplazo y sin tener en cuenta el orden de una baraja de 52 cartas. Encuentra el número de manos de poker en cada uno de los siguientes casos:

1. No hay restricciones.
2. La mano es una casa llena (3 tarjetas de un tipo y 2 de otro tipo).
3. La mano tiene 4 de un tipo.
4. Las cartas están todas en el mismo palo (por lo que la mano está a ras o a ras recta).

Responder

1. \(2\,598\,960\)
2. \(3744\)
3. \(624\)
4. \(5148\)

El juego de póquer se estudia en detalle en el capítulo de Juegos de azar.

Una mano de puente consta de 13 cartas repartidas sin reemplazo y sin importar el orden de una baraja de 52 cartas. Encuentra el número de manecillas de puente en cada uno de los siguientes casos:

1. No hay restricciones.
2. La mano tiene exactamente 4 picas.
3. La mano tiene exactamente 4 espadas y 3 corazones.
4. La mano tiene exactamente 4 espadas, 3 corazones y 2 diamantes.

Responder

1. \(635\,013\,559\,600\)
2. \(151\,519\,319\,380\)
3. \(47\,079\,732\,700\)
4. \(11\,404\,407\,300\)

Se dice que una mano de cartas que no tiene cartas en un palo en particular es nula en ese palo. Utilice la fórmula de inclusión-exclusión para encontrar cada uno de los siguientes:

1. El número de manos de póquer que son nulas en al menos un palo.
2. El número de manecillas de puente que son nulas en al menos un palo.

Responder

1. \(1\,913\,496\)
2. \(32\,427\,298\,180\)

Se dice que una mano de puente que no tiene tarjetas de honor (tarjetas de denominación 10, jota, reina, rey o as) es un Yarborough, en honor al Segundo Conde de Yarborough. Encuentra el número de Yarboroughs.

Responder

\(347\,373\,600\)

Un reparto de puente consiste en repartir 13 cartas (una mano de puente) a cada uno de 4 jugadores distintos (genéricamente denominados norte, sur, este y oeste) desde una baraja estándar de 52 cartas. Encuentra el número de ofertas de puentes.

Responder

\( 53\,644\,737\,765\,488\,792\,839\,237\,440\,000 \approx 5.36 \times 10^{28} \)

Este asombroso número es aproximadamente del mismo orden de magnitud que el número de átomos en tu cuerpo, y es una de las razones por las que bridge es un juego rico e interesante.

Encuentra el número de permutaciones de las cartas en una baraja estándar.

Responder

\(52! \approx 8.0658 \times 10^{67}\)

Este número es aún más asombroso. De hecho, si realizas el experimento de repartir las 52 cartas de un mazo bien barajado, bien podrías generar un patrón de cartas que nunca antes se había generado, asegurando así tu inmortalidad. En realidad, este experimento demuestra que, en cierto sentido, los eventos raros pueden ser muy comunes. Por cierto, Persi Diaconis ha demostrado que se necesitan alrededor de siete barajadas de riffle estándar para aleatorizar a fondo una baraja de cartas.

Dados y Monedas

Supongamos que se lanzan 5 dados distintos y estándar y se registra la secuencia de puntuaciones.

1. Encuentra el número de secuencias.
2. Encuentra el número de secuencias con las puntuaciones todas diferentes.

Responder

1. \(7776\)
2. \(720\)

Supongamos que se rodan 5 dados idénticos, estándar. ¿Cuántos resultados hay?

Responder

\(252\)

Una moneda se lanza 10 veces y el resultado se registra como una cadena de bits (donde 1 denota cabezas y 0 colas).

1. Encuentra el número de resultados.
2. Encuentra el número de resultados con exactamente 4 cabezas.
3. Encuentra el número de resultados con al menos 8 cabezas.

Responder

1. \( 1024 \)
2. \(210\)
3. \(56\)

Coeficientes polinomiales

Encuentra el coeficiente de\(x^3 \, y^4\) in\((2 \, x - 4 \, y)^7\).

Responder

\(71\,680\)

Encuentra el coeficiente de\(x^5\) in\((2 + 3 \, x)^8\).

Responder

\(108\,864\)

Encuentra el coeficiente de\(x^3 \, y^7 \, z^5\) in\((x + y + z)^{15}\).

Responder

\(360\,360\)

La Junta de Galton

En el juego de mesa Galton,

1. Mueve la pelota de\((0, 0)\) a\((10, 6)\) por un camino de tu elección. Tenga en cuenta la cadena de bits y el subconjunto correspondientes.
2. Genera la cadena de bits\(0011101001\). Anote el subconjunto y la ruta correspondientes.
3. Generar el subconjunto\(\{1, 4, 5, 7, 8, 10\}\). Tenga en cuenta la cadena de bits y la ruta correspondientes.
4. Generar todos los caminos desde\((0, 0)\) hasta\((5, 3)\). ¿Cuántos caminos hay?

Responder

4. 10

Genera el triángulo de Pascal hasta\(n = 10\).

Muestras

Un envío contiene 12 artículos buenos y 8 defectuosos. Se selecciona una muestra de 5 ítems. Encuentra el número de muestras que contienen exactamente 3 buenos artículos.

Responder

\(6160\)

En la \((n, k)\)lotería,\(k\) los números se eligen sin reemplazo del conjunto de enteros desde el 1 hasta\(n\) (donde\( n, \, k \in \N_+ \) y\(k \lt n\)). El orden no importa.

1. Encuentra el número de resultados en la\((n, k)\) lotería general.
2. Calcular explícitamente el número de resultados en la\((44, 6)\) lotería (un formato común).

Responder

1. \(\binom{n}{k}\)
2. \(7\,059\,052\)

Para más información sobre este tema, consulte la sección de Loterías en el capítulo sobre Juegos de azar.

Calcular explícitamente cada fórmula en la tabla de muestreo anterior cuándo\(n = 10\) y\(k = 4\).

Responder

1. Muestras ordenadas con reemplazo:\(10\,000\)
2. Muestras pedidas sin reemplazo:\(5040\)
3. Muestras desordenadas con reemplazo:\(715\)
4. Muestras desordenadas sin reemplazo:\(210\)

Saludos

Supongamos que hay\(n\) personas que se dan la mano entre sí. ¿Cuántos apretones de manos hay?

Responder

\(\binom{n}{2}\). Tenga en cuenta que un apretón de manos puede considerarse como un subconjunto de tamaño 2 del conjunto de\( n \) personas.

Hay\( m \) hombres y\( n \) mujeres. Los hombres se dan la mano entre sí; las mujeres se abrazan; y cada hombre se inclina ante cada mujer.

1. ¿Cuántos apretones de manos hay?
2. ¿Cuántos abrazos hay?
3. ¿Cuántos arcos hay?
4. ¿Cuántos saludos hay?

Responder

1. \( \binom{m}{2} \)
2. \( \binom{n}{2} \)
3. \( m n \)
4. \( \binom{m}{2} + \binom{n}{2} + m n = \binom{m + n}{2} \)

Soluciones Integer

Encuentra el número de soluciones enteras de\(x_1 + x_2 + x_3 = 10\) en cada uno de los siguientes casos:

1. \(x_i \ge 0\)para cada uno\(i\).
2. \(x_i \gt 0\)para cada uno\(i\).

Responder

1. \(66\)
2. \(36\)

Coeficientes Generalizados

Calcular cada uno de los siguientes:

1. \((-5)^{(3)}\)
2. \(\left(\frac{1}{2}\right)^{(4)}\)
3. \(\left(-\frac{1}{3}\right)^{(5)}\)

Responder

1. \(-210\)
2. \(-\frac{15}{16}\)
3. \(-\frac{3640}{243}\)

Calcular cada uno de los siguientes:

1. \(\binom{1/2}{3}\)
2. \(\binom{-5}{4}\)
3. \(\binom{-1/3}{5}\)

Responder

1. \(\frac{1}{16}\)
2. \(70\)
3. \(-\frac{91}{729}\)

Cumpleaños

Supongamos que se seleccionan\(n\) personas y se anotan sus cumpleaños. (Ignorar los años bisiestos, para que un año tenga 365 días.)

1. Encuentra el número de resultados.
2. Encuentra el número de resultados con cumpleaños distintos.

Responder

1. \(365^n\).
2. \(365^{(n)}\).

Ajedrez

Tenga en cuenta que los cuadrados de un tablero de ajedrez son distintos y, de hecho, a menudo se identifican con el conjunto de productos cartesianos\[ \{a, b, c, d, e, f, g, h\} \times \{1, 2, 3, 4, 5, 6, 7, 8\} \]

Encuentra la cantidad de formas de colocar 8 gradas en un tablero de ajedrez para que ninguna torre pueda capturar otra en cada uno de los siguientes casos.

1. Las gradas son distinguibles.
2. Las gradas son indistinguibles.

Responder

1. \(1\,625\,702\,400\)
2. \(40\,320\)

Regalos

Supongamos que 20 caramelos idénticos se distribuyen a 4 niños. Encuentra el número de distribuciones en cada uno de los siguientes casos:

1. No hay restricciones.
2. Cada niño debe recibir al menos un caramelo.

Responder

1. \(1771\)
2. \(969\)

En la canción Los doce días de Navidad, encuentra la cantidad de regalos que le dio a la cantante su verdadero amor. (Tenga en cuenta que el cantante comienza de nuevo con regalos cada día, de manera que por ejemplo, el verdadero amor consigue una nueva perdiz en un peral cada uno de los 12 días.)

Responder

\(364\)

Equipos

Supongamos que 10 niños se dividen en dos equipos de 5 cada uno para un juego de básquetbol. De cuántas maneras se puede hacer esto en cada uno de los siguientes casos:

1. Los equipos son distinguibles (por ejemplo, un equipo está etiquetado como Alabama y el otro equipo está etiquetado como Auburn).
2. Los equipos no son distinguibles.

Responder

1. \(252\)
2. \(126\)