3.1: Permutaciones

Muchos problemas en la teoría de la probabilidad requieren que se cuente el número de formas en que puede ocurrir un evento en particular. Para ello, estudiamos los temas de permutaciones y combinaciones. Consideramos permutaciones en esta sección y combinaciones en la siguiente sección. Antes de discutir las permutaciones, es útil introducir una técnica general de conteo que nos permita resolver una variedad de problemas de conteo, incluido el problema de contar el número de posibles permutaciones de\(n\) objetos.

Problemas de conteo

Considera un experimento que se lleva a cabo en varias etapas y es tal que el número de resultados\(m\) en la etapa\(n\) th es independiente de los resultados de las etapas anteriores. El número\(m\) puede ser diferente para diferentes etapas. Queremos contar el número de formas en que se puede llevar a cabo todo el experimento.

Ejemplo\(\PageIndex{1}\)

Estás comiendo en el restaurante de Émile y el mesero te informa que tienes (a) dos opciones para aperitivos: sopa o jugo; (b) tres para el plato principal: un plato de carne, pescado o verdura; y (c) dos para postre: helado o pastel. ¿Cuántas opciones posibles tienes para tu comida completa? Ilustramos las posibles comidas mediante un diagrama de árbol que se muestra en la Figura\(\PageIndex{1}\) Su menú se decide en tres etapas; en cada etapa el número de opciones posibles no depende de lo que se elija en las etapas anteriores: dos opciones en la primera etapa, tres en la segunda y dos en la tercera. Del diagrama de árbol vemos que el número total de elecciones es producto del número de elecciones en cada etapa. En estos ejemplos tenemos\(2 \cdot 3 \cdot 2 = 12\) posibles menús. Nuestro ejemplo de menú es un ejemplo de la siguiente técnica general de conteo.

Una técnica de conteo

Una tarea se va a llevar a cabo en una secuencia de\(r\) etapas. Hay\(n_1\) formas de llevar a cabo la primera etapa; para cada una de estas\(n_1\) vías, hay\(n_2\) formas de llevar a cabo la segunda etapa; para cada una de estas\(n_2\) vías, hay\(n_3\) formas de llevar a cabo la tercera etapa, y así sucesivamente. Entonces el número total de formas en que se puede realizar toda la tarea viene dada por el producto\(N = n_1 \cdot n_2 \cdot \dots \cdot n_r\).

Diagramas de árbol

A menudo será útil utilizar un diagrama de árbol cuando se estudien probabilidades de eventos relacionados con experimentos que se llevan a cabo por etapas y para los que se nos dan las probabilidades de los resultados en cada etapa. Por ejemplo, supongamos que el dueño del restaurante de Émile ha observado que el 80 por ciento de sus clientes elige la sopa para un aperitivo y el 20 por ciento elige el jugo. De los que eligen la sopa, el 50 por ciento elige la carne, el 30 por ciento elige el pescado y el 20 por ciento elige el plato de verduras. De los que eligen jugo para un aperitivo, 30 por ciento elige carne, 40 por ciento elige pescado y 30 por ciento elige el plato de verduras. Podemos usar esto para estimar las probabilidades en las dos primeras etapas como se indica en el diagrama de árbol de la Figura 3.2.

Elegimos para nuestro espacio de muestra el conjunto\(\Omega\) de todos los caminos posibles\(\omega = \omega_1\),\(\omega_2\),...,\(\omega_6\) a través del árbol. ¿Cómo debemos asignar nuestra distribución de probabilidad? Por ejemplo, ¿qué probabilidad debemos asignar al cliente eligiendo sopa y luego la carne? Si 8/10 de los clientes eligen sopa y luego 1/2 de estos eligen carne, una proporción\(8/10 \cdot 1/2 = 4/10\) de los clientes elige sopa y luego carne. Esto sugiere elegir nuestra distribución de probabilidad para cada camino a través del árbol para que sea el producto de las probabilidades en cada una de las etapas a lo largo del camino. Esto da como resultado la distribución de probabilidad para los puntos de muestreo\(\omega\) indicados en la Figura 3.2. (Tenga en cuenta que\(m(\omega_1) + \cdots + m(\omega_6) = 1\).) De esto vemos, por ejemplo, que la probabilidad de que un cliente elija carne es\(m(\omega_1) + m(\omega_4) = .46\).

Diremos más sobre estas medidas de árbol cuando discutamos el concepto de probabilidad condicional en el Capítulo 4. Volvemos ahora a más problemas de conteo.

Ejemplo\(\PageIndex{2}\)

Podemos demostrar que hay al menos dos personas en Columbus, Ohio, que tienen las mismas tres iniciales. Suponiendo que cada persona tiene tres iniciales, hay 26 posibilidades para la primera inicial de una persona, 26 para la segunda y 26 para la tercera. Por lo tanto, existen\(26^3 = 17,576\) posibles conjuntos de iniciales. Este número es menor que el número de personas que viven en Columbus, Ohio; por lo tanto, debe haber al menos dos personas con las mismas tres iniciales.

Consideramos a continuación el problema del cumpleaños celebrado, que a menudo se usa para mostrar que la intuición ingenua no siempre se puede confiar en la probabilidad.

Ejemplo\(\PageIndex{3}\): Birthday Problem

¿Cuántas personas necesitamos tener en una habitación para que sea una apuesta favorable (probabilidad de éxito mayor a 1/2) que dos personas en la sala tengan el mismo cumpleaños?

Solución

Dado que hay 365 cumpleaños posibles, es tentador adivinar que necesitaríamos alrededor de 1/2 este número, o 183. Seguramente ganarías esta apuesta. De hecho, el número requerido para una apuesta favorable es de sólo 23. Para mostrar esto, encontramos la probabilidad de\(p_r\) que, en una habitación con\(r\) personas, no haya duplicación de cumpleaños; tendremos una apuesta favorable si esta probabilidad es menor a la mitad.

Problema de cumpleaños.

Número de personas	Probabilidad de que todos los cumpleaños sean diferentes
20	.5885616
21	.5563117
22	.5243047
23	.4927028
24	.4616557
25	.4313003

Supongamos que hay 365 cumpleaños posibles para cada persona (ignoramos los años bisiestos). Ordene a la gente de 1 a\(r\). Para un punto de muestra\(\omega\), elegimos una posible secuencia de duración\(r\) de cumpleaños cada uno elegido como una de las 365 fechas posibles. Hay 365 posibilidades para el primer elemento de la secuencia, y para cada una de estas elecciones hay 365 para el segundo, y así sucesivamente, haciendo\(365^r\) posibles secuencias de cumpleaños. Debemos encontrar el número de estas secuencias que no tienen duplicación de cumpleaños. Para tal secuencia, podemos elegir cualquiera de los 365 días para el primer elemento, luego cualquiera de los 364 restantes para el segundo, 363 para el tercero, y así sucesivamente, hasta\(r\) tomar decisiones. Para la elección\(r\) th, habrá\(365 - r + 1\) posibilidades. Por lo tanto, el número total de secuencias sin duplicaciones es

\[365 \cdot 364 \cdot 363 \cdot \dots \cdot (365 - r + 1)\ .\]

Así pues, suponiendo que cada secuencia es igualmente probable,

\[p_r = \frac{365 \cdot 364 \cdot \dots \cdot (365 - r + 1)}{365^r}\ .\]

Denotamos el producto\[(n)(n-1)\cdots (n - r +1)\] por\((n)_r\) (leer “\(n\)abajo\(r\)” o\(r\) “\(n\)inferior”). Por lo tanto,

\[p_r = \frac{(365)_r}{(365)^r}\ .\]

El programa Cumpleaños realiza este cálculo e imprime las probabilidades de\(r = 20\) hasta 25. Al ejecutar este programa, obtenemos los resultados que se muestran en la Tabla 3.1.

Como afirmamos anteriormente, la probabilidad de que no haya duplicación cambia de más de la mitad a menos de la mitad a medida que pasamos de 22 a 23 personas. Para ver lo poco probable que es que perdamos nuestra apuesta por un mayor número de personas, hemos vuelto a ejecutar el programa, imprimiendo valores de\(r = 10\) a\(r = 100\) en pasos de 10. Vemos que en una sala de 40 personas las probabilidades ya favorecen fuertemente una duplicación, y en una sala de 100 las probabilidades están abrumadoramente a favor de una duplicación.

Problema de cumpleaños

Número de personas	Probabilidad de que todos los cumpleaños sean diferentes
10	.8830518
20	.5885616
30	.2936838
40	.1087682
50	.0296264
60	.0058773
70	.0008404
80	.0000857
90	.0000062
100	.0000003

Hemos asumido que es igualmente probable que los cumpleaños caigan en cualquier día en particular. La evidencia estadística sugiere que esto no es cierto. No obstante, es intuitivamente claro (pero no fácil de probar) que esto hace que sea aún más probable que tenga una duplicación con un grupo de 23 personas. (Consulte Ejercicio\(\PageIndex{19}\) para saber qué sucede en planetas con más o menos de 365 días al año).

Permutaciones

Pasamos ahora al tema de las permutaciones.

Definición\(PageIndex{1}\): Permutation

Dejar\(A\) ser cualquier conjunto finito. Una permutación de\(A\) es un mapeo uno a uno de\(A\) sobre sí mismo.

Para especificar una permutación particular enumeramos los elementos de\(A\) y, debajo de ellos, mostramos dónde se envía cada elemento por el mapeo uno a uno. Por ejemplo, si\(A = \{a,b,c\}\) una posible permutación\(\sigma\) sería

\[\sigma = \pmatrix{ a & b & c \cr b & c & a \cr}.\]

Por la permutación\(\sigma\),\(a\) se envía a\(b\),\(b\) se envía a\(c\), y\(c\) se envía a\(a\). La condición de que el mapeo sea uno a uno significa que no\(A\) se envían dos elementos de, por el mapeo, al mismo elemento de\(A\).

Podemos poner los elementos de nuestro conjunto en algún orden y cambiarles el nombre 1, 2,...,\(n\). Entonces, una permutación típica del conjunto se\(A = \{a_1,a_2,a_3,a_4\}\) puede escribir en la forma

\[\sigma = \pmatrix{ 1 & 2 & 3 & 4 \cr 2 & 1 & 4 & 3 \cr},\]

indicando que\(a_1\) fue a\(a_2\),\(a_2\) a\(a_1\),\(a_3\) a\(a_4\), y\(a_4\) a\(a_3\).

Si siempre elegimos la fila superior para que sea 1 2 3 4 entonces, para prescribir la permutación, solo necesitamos dar la fila inferior, con el entendimiento de que esto nos dice a dónde va 1, va 2, y así sucesivamente, bajo el mapeo. Cuando esto se hace, a la permutación se le suele llamar un reordenamiento de los\(n\) objetos 1, 2, 3,...,\(n\). Por ejemplo, todas las posibles permutaciones, o reordenamientos, de los números\(A = \{1,2,3\}\) son:\[123,\ 132,\ 213,\ 231,\ 312,\ 321\ .\]

Es una cuestión fácil contar el número de posibles permutaciones de\(n\) objetos. Por nuestro principio general de conteo, hay\(n\) formas de asignar el primer elemento, para cada uno de estos tenemos\(n - 1\) formas de asignar el segundo objeto,\(n - 2\) para el tercero, y así sucesivamente. Esto prueba el siguiente teorema.

Teorema\(PageIndex{1}\)

El número total de permutaciones de un conjunto\(A\) de\(n\) elementos viene dado por\(n \cdot (n-1) \cdot (n - 2) \cdot \ldots \cdot 1\).

A veces es útil considerar ordenamientos de subconjuntos de un conjunto dado. Esto solicita la siguiente definición.

Let\(A\) be an\(n\) -element set, y let\(k\) ser un entero entre 0 y\(n\). Entonces una\(k\) -permutación de\(A\) es un listado ordenado de un subconjunto\(A\) de tamaño\(k\).

Utilizando las mismas técnicas que en el último teorema, se demuestra fácilmente el siguiente resultado.

Teorema\(PageIndex{2}\)

El número total de\(k\) -permutaciones de un conjunto\(A\) de\(n\) elementos viene dado por\(n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n - k + 1)\).

Factoriales

El número dado en Teorema\(\PageIndex{1}\) se llama\(n\) factorial, y se denota por\(n!\). La expresión 0! se define como 1 para que ciertas fórmulas salgan más simples. Los primeros valores de esta función se muestran en la Tabla 3.3. El lector notará que esta función crece muy rápidamente.

Valores de la función factorial.

\(n\)	\(n!\)
\ (n\) ">0	\ (n! \) ">1
\ (n\) ">1	\ (n! \) ">1
\ (n\) ">2	\ (n! \) ">2
\ (n\) ">3	\ (n! \) ">6
\ (n\) ">4	\ (n! \) ">24
\ (n\) ">5	\ (n! \) ">120
\ (n\) ">6	\ (n! \) ">720
\ (n\) ">7	\ (n! \) ">5040
\ (n\) ">8	\ (n! \) ">40320
\ (n\) ">9	\ (n! \) ">362880
\ (n\) ">10	\ (n! \) ">3628800

La expresión\(n!\) entrará en muchos de nuestros cálculos, y necesitaremos tener alguna estimación de su magnitud cuando\(n\) sea grande. Claramente no es práctico hacer cálculos exactos en este caso. En cambio, usaremos un resultado llamado fórmula de Stirling. Antes de afirmar esta fórmula necesitamos una definición.

Definición\(PageIndex{3}\)

Let\(a_n\) y\(b_n\) ser dos secuencias de números. Decimos que\(a_n\) es asintóticamente igual a\(b_n\), y escribimos\(a_n \sim b_n\), si

\[\lim_{n \to \infty} \frac{a_n}{b_n} = 1\ .\]

[examen 3.4] Si\(a_n = n + \sqrt n\) y\(b_n = n\) entonces, ya\(a_n/b_n = 1 + 1/\sqrt n\) y esta proporción tiende a 1 como\(n\) tiende al infinito, tenemos\(a_n \sim b_n\).

Teorema\(\PageIndex{3}\)(Stirling's Formula)

La secuencia\(n!\) es asintóticamente igual a

\[n^ne^{-n}\sqrt{2\pi n}\ .\].

La prueba de la fórmula de Stirling se puede encontrar en la mayoría de los textos de análisis. Verifiquemos esta aproximación mediante el uso de la computadora. El programa StirlingApproximations imprime\(n!\), la aproximación de Stirling y, finalmente, la proporción de estos dos números. La salida de muestra de este programa se muestra en la Tabla 3.4. Obsérvese que, mientras la relación de los números se está acercando a 1, la diferencia entre el valor exacto y la aproximación va en aumento, y de hecho, esta diferencia tenderá al infinito como\(n\) tiende al infinito, aunque la relación tiende a 1. (Esto también fue cierto en nuestro Ejemplo\(\PageIndex{4}\) donde\(n + \sqrt n \sim n\), pero la diferencia es\(\sqrt n\).)

Cuadro 3.4: Aproximaciones de Stirling a la función factorial.

\(n\)	\(n!\)	Aproximación	Ratio
\ (n\) ">1	\ (n! \) ">1	0.922	1.084
\ (n\) ">2	\ (n! \) ">2	1.919	1.042
\ (n\) ">3	\ (n! \) ">6	5.836	1.028
\ (n\) ">4	\ (n! \) ">24	23.506	1.021
\ (n\) ">5	\ (n! \) ">120	118.019	1.016
\ (n\) ">6	\ (n! \) ">720	710.078	1.013
\ (n\) ">7	\ (n! \) ">5040	4980.396	1.011
\ (n\) ">8	\ (n! \) ">40320	39902.395	1.010
\ (n\) ">9	\ (n! \) ">362880	359536.873	1.009
\ (n\) ">10	\ (n! \) ">3628800	3598696.619	1.008

Generación de permutaciones aleatorias

Consideramos ahora la cuestión de generar una permutación aleatoria de los enteros entre 1 y\(n\). Considera el siguiente experimento. Comenzamos con una baraja de\(n\) cartas, etiquetada del 1 a través\(n\). Elegimos una carta aleatoria de la baraja, tomamos nota de su etiqueta y la dejamos a un lado. Repetimos este proceso hasta que se hayan elegido todas\(n\) las tarjetas. Es claro que cada permutación de los números enteros de 1 a\(n\) puede ocurrir como una secuencia de etiquetas en este experimento, y que cada secuencia de etiquetas es igualmente probable que ocurra. En nuestras implementaciones de los algoritmos informáticos, el procedimiento anterior se llama Permutación Aleatoria.

Puntos Fijos

Hay muchos problemas interesantes que se relacionan con las propiedades de una permutación elegida al azar del conjunto de todas las permutaciones de un conjunto finito dado. Por ejemplo, dado que una permutación es un mapeo uno a uno del conjunto sobre sí mismo, es interesante preguntar cuántos puntos se mapean sobre sí mismos. Llamamos a tales puntos puntos fijos del mapeo.

\(p_k(n)\)Sea la probabilidad de que una permutación aleatoria del conjunto\(\{1, 2, \ldots, n\}\) tenga puntos exactamente\(k\) fijos. Intentaremos aprender algo sobre estas probabilidades mediante simulación. El programa FixedPoints utiliza el procedimiento RandomPermutation para generar permutaciones aleatorias y contar puntos fijos. El programa imprime la proporción de veces que hay puntos\(k\) fijos así como el número promedio de puntos fijos. Los resultados de este programa para 500 simulaciones para los casos\(n = 10\), 20 y 30 se muestran en la Tabla 3.5.

Distribuciones de punto fijo.

Número de puntos fijos	Fracción de permutaciones
	n = 10	n = 20	n = 30
0	0.362	0.370	0.358
1	0.368	0.396	0.358
2	0.202	0.164	0.192
3	0.052	0.060	0.070
4	0.012	0.008	0.020
5	0.004	0.002	0.002
Promedio de puntos fijos	0.996	0.948	1.042

Observe el hecho bastante sorprendente de que nuestras estimaciones para las probabilidades no parecen depender mucho del número de elementos en la permutación. Por ejemplo, la probabilidad de que no haya puntos fijos, cuando\(n = 10,\ 20,\) o 30 se estima que esté entre .35 y .37. Veremos más adelante (ver Ejemplo\(\PageIndex{12}\) que para\(n \geq 10\) las probabilidades exactas\(p_n(0)\) son, a seis decimales de precisión, iguales a\(1/e \approx .367879\). Así, para todos los fines prácticos, después de\(n = 10\) la probabilidad de que una permutación aleatoria del conjunto no\(\{1, 2, \ldots, n\}\) tenga puntos fijos no depende de ello\(n\). Estas simulaciones también sugieren que el número promedio de puntos fijos es cercano a 1. Se puede mostrar (ver Ejemplo\(\PageIndex{1}\)) que el promedio es exactamente igual a 1 para todos\(n\).

Las versiones más pintorescas del problema de punto fijo son: Has arreglado los libros en tu estantería en orden alfabético por autor y son devueltos a tu estantería al azar; ¿cuál es la probabilidad de que exactamente\(k\) de los libros terminen en su posición correcta? (El problema de la biblioteca.) En un restaurante se revisan los\(n\) sombreros y están desesperadamente revueltos; ¿cuál es la probabilidad de que nadie recupere su propio sombrero? (El problema de la comprobación del sombrero.) En las Observaciones Históricas al final de esta sección, damos un método para resolver exactamente el problema del hat check. Otro método se da en Ejemplo\(\PageIndex{13}\)

Registros

Aquí hay otro problema de probabilidad interesante que involucra permutaciones. Las estimaciones para la cantidad de nieve medida en pulgadas en Hanover, New Hampshire, en los diez años de 1974 a 1983 se muestran en el Cuadro 3.4.

Nevadas en Hannover.

Fecha	Nevadas en pulgadas
1974	75
1975	88
1976	72
1977	110
1978	85
1979	30
1980	55
1981	86
1982	51
1983	64

Supongamos que hemos empezado a llevar registros en 1974. Entonces las nevadas de nuestro primer año podrían considerarse una nevada récord a partir de este año. En 1975 se estableció un nuevo registro; el siguiente registro se estableció en 1977, y no se establecieron nuevos registros después de este año. Así, en este periodo de diez años se establecieron tres registros: 1974, 1975 y 1977. La pregunta que nos planteamos es: ¿Cuántos registros debemos esperar que se establezcan en un periodo de diez años así? Podemos contar el número de registros en términos de una permutación de la siguiente manera: Numeramos los años del 1 al 10. Las cantidades reales de nevadas no son importantes pero sus tamaños relativos sí. Podemos, por lo tanto, cambiar los números que miden nevadas a números 1 a 10 reemplazando el número más pequeño por 1, el siguiente más pequeño por 2, y así sucesivamente. (Asumimos que no hay vínculos.) Para nuestro ejemplo, obtenemos los datos que se muestran en la Tabla 3.7.

.5in Año .5in 1.3in2.3in 3.3in 4.3in 5.3in6.3in 7.3in 8.3in 9.3in 9.3in 10
.5in Ranking 6 9 5 10 7 1 3 8 2 4

Esto nos da una permutación de los números del 1 al 10 y, a partir de esta permutación, podemos leer fuera de los registros; están en los años 1, 2 y 4. Así podemos definir registros para una permutación de la siguiente manera:

Que\(\sigma\) sea una permutación del conjunto\(\{1, 2, \ldots, n\}\). Entonces\(i\) es un registro de\(\sigma\) si cualquiera\(i = 1\) o\(\sigma(j) < \sigma(i)\) para cada uno\(j = 1,\ldots,\,i - 1\).

Ahora bien, si consideramos que todos los rankings de nevadas durante un periodo de un\(n\) año son igualmente probables (y no permitimos empates), podemos estimar la probabilidad de que haya\(k\) registros en\(n\) años así como el número promedio de registros por simulación.

Hemos escrito un programa Registros que cuenta el número de registros en permutaciones elegidas aleatoriamente. Hemos ejecutado este programa para los casos\(n = 10\), 20, 30. Para\(n = 10\) el número promedio de registros es 2.968, para 20 es 3.656, y para 30 es 3.960. Vemos ahora que los promedios aumentan, pero muy lentamente. Veremos más adelante (ver Ejemplo\(\PageIndex{11}\)) que el número promedio es aproximadamente\(\log n\). Ya que\(\log 10 = 2.3\)\(\log 20 = 3\),, y\(\log 30 = 3.4\), esto es consistente con los resultados de nuestras simulaciones.

Como se señaló anteriormente, podremos obtener fórmulas para obtener resultados exactos de ciertos problemas del tipo anterior. No obstante, sólo cambios menores en el problema hacen que esto sea imposible. El poder de la simulación es que cambios menores en un problema no hacen que la simulación sea mucho más difícil. (Consulte Ejercicio\(\PageIndex{20}\) para ver una variación interesante del problema de verificación de sombrero.)

Lista de Permutaciones

Otro método para resolver problemas que no es sensible a pequeños cambios en el problema es hacer que la computadora simplemente enumere todas las permutaciones posibles y cuente la fracción que tenga la propiedad deseada. El programa AllPermutations produce una lista de todas las permutaciones de\(n\). Cuando intentamos ejecutar este programa, nos encontramos con una limitación en el uso de la computadora. El número de permutaciones de\(n\) aumenta tan rápidamente que incluso enumerar todas las permutaciones de 20 objetos es poco práctico.

Observaciones Históricas

Nuestro principio básico de conteo establecía que si puedes hacer una cosa de\(r\) maneras y para cada una de estas otra cosa de\(s\) maneras, entonces puedes hacer el par de\(rs\) maneras. Este es un resultado tan evidente que podría esperarse que ocurrió muy temprano en las matemáticas. N. L. Biggs sugiere que podríamos trazar un ejemplo de este principio de la siguiente manera: Primero, relata una popular canción infantil que data de al menos 1730:

Como iba a St. Ives,

Conocí a un hombre con siete esposas,

Cada esposa tenía siete sacos,

Cada saco tenía siete gatos,

Cada gato tenía siete kits.

Kits, gatos, sacos y esposas,

¿Cuántos iban a San Ives?

(Necesitas nuestro principio solo si no eres lo suficientemente inteligente como para darte cuenta de que se supone que debes responder a uno, ya que solo el narrador va a St. Ives; ¡los demás van en la otra dirección!)

También da un problema al aparecer en uno de los manuscritos matemáticos más antiguos sobrevivientes de alrededor de 1650 a.C., traducido aproximadamente como:

Casas	7
Gatos	49
Ratones	343
Trigo	2401
Hekat	16807
	19607

Se ha sugerido la siguiente interpretación: hay siete casas, cada una con siete gatos; cada gato mata a siete ratones; cada ratón habría comido siete cabezas de trigo, cada una de las cuales habría producido siete medidas hekat de grano. Con esta interpretación, la tabla responde a la pregunta de cuántas medidas hekat fueron salvadas por las acciones de los gatos. No está claro por qué el escritor de la mesa quiso sumar los números juntos. ¹

Uno de los primeros usos de las factoriales ocurrió en la prueba de Euclides de que hay infinitamente muchos números primos. Euclides argumentó que debe haber un número primo entre\(n\) y de la\(n! + 1\) siguiente manera:\(n!\) y\(n! + 1\) no puede tener factores comunes. O\(n! + 1\) es primo o tiene un factor propio. En este último caso, este factor no puede dividirse\(n!\) y por lo tanto debe estar entre\(n\) y\(n! + 1\). Si este factor no es primo, entonces tiene un factor que, por el mismo argumento, debe ser mayor que\(n\). De esta manera, eventualmente alcanzamos un prime más grande que\(n\), y esto es válido para todos\(n\).

La “\(n!\)" regla para el número de permutaciones parece haber ocurrido primero en la India. Se han encontrado ejemplos ya en el 300 a.C., y para el siglo XI la fórmula general parece haber sido bien conocida en la India y luego en los países árabes.

El problema del chequeo de sombrero se encuentra en un libro de probabilidad temprana escrito por de Montmort e impreso por primera vez en 1708. ² Aparece en forma de juego llamado Treize. En una versión simplificada de este juego considerado por de Montmort se vuelca cartas numeradas del 1 al 13, llamando 1, 2,..., 13 a medida que se examinan las cartas. De Montmort pidió la probabilidad de que ninguna tarjeta que se aparta esté de acuerdo con el número llamado.

Esta probabilidad es la misma que la probabilidad de que una permutación aleatoria de 13 elementos no tenga punto fijo. De Montmort resolvió este problema mediante el uso de una relación de recursión de la siguiente manera: deja\(w_n\) ser el número de permutaciones de\(n\) elementos sin punto fijo (tales permutaciones se denominan desórdenes). Entonces\(w_1 = 0\) y\(w_2 = 1\).

Ahora asuma eso\(n \ge 3\) y elige un desajuste de los enteros entre 1 y\(n\). Dejar\(k\) ser el entero en la primera posición en este desajuste. Por la definición de trastornamiento, tenemos\(k \ne 1\). Hay dos posibilidades de interés respecto a la posición de 1 en el desajuste: o 1 está en la posición\(k\) th o está en otra parte. En el primer caso, los enteros\(n-2\) restantes se pueden posicionar de\(w_{n-2}\) maneras sin dar como resultado ningún punto fijo. En el segundo caso, consideramos el conjunto de enteros\(\{1, 2, \ldots, k-1, k+1, \ldots, n\}\). Los números en este conjunto deben ocupar las posiciones\(\{2, 3, \ldots, n\}\) para que ninguno de los números que no sea 1 en este conjunto sea fijo, y también para que 1 no esté en posición\(k\). El número de formas de lograr este tipo de arreglos es justo\(w_{n-1}\). Ya que hay valores\(n-1\) posibles de\(k\), vemos que\[w_n = (n - 1)w_{n - 1} + (n - 1)w_{n -2}\] para\(n \ge 3\). Se podría conjeturar a partir de esta última ecuación que la secuencia\(\{w_n\}\) crece como la secuencia\(\{n!\}\).

De hecho, es fácil demostrar por inducción que\[w_n = nw_{n - 1} + (-1)^n\ .\] Entonces\(p_i = w_i/i!\) satisface\[p_i - p_{i - 1} = \frac{(-1)^i}{i!}\ .\] Si sumamos de\(i = 2\) a\(n\), y usamos el hecho de que\(p_1 = 0\), obtenemos\[p_n = \frac1{2!} - \frac1{3!} + \cdots + \frac{(-1)^n}{n!}\ .\] Esto concuerda con los primeros\(n + 1\) términos de la expansión para\(e^x\) para\(x = -1\) y por lo tanto para grandes \(n\)es aproximadamente\(e^{-1} \approx .368\). David señala que este fue posiblemente el primer uso de la función exponencial en probabilidad. ³ Veremos otra forma de derivar el resultado de Montmort en la siguiente sección, utilizando un método conocido como el método Inclusión-Exclusión.

Recientemente, un problema relacionado apareció en una columna de Marilyn vos Savant. ⁴ Charles Price escribió para preguntar sobre su experiencia jugando cierta forma de solitario, a veces llamado “solitario de frustración”. En este juego en particular, se baraja una baraja de cartas, y luego se reparte, una carta a la vez. A medida que se reparten las cartas, el jugador cuenta del 1 al 13, y luego comienza de nuevo en 1. (Así, cada número se cuenta cuatro veces.) Si un número que se está contando coincide con el rango de la carta que se está entregando, entonces el jugador pierde el juego. Price encontró que rara vez ganaba y se preguntaba con qué frecuencia debía ganar. Vos Savant remarcó que el número esperado de partidos es de 4 por lo que debería ser difícil ganar el juego.

Encontrar la posibilidad de ganar es un problema más difícil que el que resolvió de Montmort porque, cuando uno recorre toda la baraja, hay diferentes patrones para los partidos que podrían ocurrir. Por ejemplo, los partidos pueden ocurrir para dos cartas del mismo rango, digamos dos ases, o para dos rangos diferentes, digamos un dos y un tres.

Una discusión de este problema se puede encontrar en Riordan. ⁵ En este libro, se muestra que como\(n \rightarrow \infty\), la probabilidad de que no haya coincidencias tiende a\(1/e^4\).

El juego original de Treize es más difícil de analizar que el solitario de frustración. El juego de Treize se juega de la siguiente manera. Una persona es elegida como crupier y las otras son jugadores. Cada jugador, que no sea el crupier, pone una apuesta. El crupier baraja las cartas y las vuelve una a la vez gritando, “As, dos, tres,..., rey”, al igual que en el solitario de frustración. Si el crupier pasa por las 13 cartas sin un partido paga a los jugadores una cantidad igual a su apuesta, y el trato pasa a otra persona. Si hay un partido el crupier recoge las apuestas de los jugadores; los jugadores ponen nuevas apuestas, y el crupier continúa a través de la baraja, gritando: “As, dos, tres,...” Si el crupier se queda sin cartas vuelve a organizar y continúa el conteo donde lo dejó. Continúa hasta que hay una racha de 13 sin partido y luego se elige un nuevo crupier.

La pregunta en este punto es cuánto dinero puede esperar ganar el crupier de cada jugador. De Montmort encontró que si cada jugador pone una apuesta de 1, digamos, entonces el crupier ganará aproximadamente .801 de cada jugador.

Peter Doyle calculó la cantidad exacta que el crupier puede esperar ganar. La respuesta es:

265160721560102185822276079127341827846421204821360914467153719620899315231134354172455433491287054144029923925160769411350008077591781851201382176876653563173852874555859367254632009477403737372739557280745938434274787664965076063990538261189388143513547366316017004945507201764278828306601171079536331427343824779227 098352817532990359885814136883676558331132447615331072062747416971930180664915269870408438391421790790695497603628528211590140316202120601549126920880824913325553882692055427830810368578818861208758248800680978640438118582834877542560955550662878927123048269976017001162335927933082975336421935050745402689256831938 87821301442705197918823303692913358259222011722071315607111497510114983106336407213896987800799647204708825303387525892236581323015628005621143427290625658974433971 657194541229080070862898413060875613028189911673578636237560671849864913535353553622197448890223267101158801016285931351979294387223277033396967797970699334758024236769498736616051840314775656156039338025707097071195969641268242455013319879747054693517809383750593488858698672364846950539888686285826099055862710013181 5062113440705698321474022185156770667208094586589378459432799868706334161812988630496327287254818458879353024498 0032242558644674104814772093410806135061350613503856973048971213063937040515 59533731591.

Esto es de .803 a 3 decimales. Una descripción del algoritmo utilizado para encontrar esta respuesta se puede encontrar en su página web. ⁶ Una discusión de este problema y otros problemas se puede encontrar en Doyle et al. ⁷

El problema del cumpleaños no parece tener una historia muy antigua. Problemas de este tipo fueron discutidos por primera vez por von Mises. ⁸ Se popularizó en la década de 1950 por el libro de Feller. ⁹

Stirling presentó su fórmula

\[n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n\]

en su obra Methodus Diferencialis publicada en 1730. ¹⁰ Esta aproximación fue utilizada por de Moivre para establecer su célebre teorema del límite central que estudiaremos en el Capítulo 9. El propio De Moivre había establecido independientemente esta aproximación, pero sin identificar la constante\(\pi\). Habiendo establecido la aproximación

\[\frac{2B}{\sqrt n}\]

para el término central de la distribución binomial, donde la constante\(B\) fue determinada por una serie infinita, de Moivre escribe:

... mi digno y erudito Amigo, el señor James Stirling, quien se había aplicado después de mí a esa indagación, encontró que la Cantidad\(B\) sí denotaba la Raíz Cuadrada de la Circunferencia de un Círculo cuyo Radio es Unidad, de manera que si esa Circunferencia se llamara\(c\) la Relación del Término medio a la Suma de todos los Términos serán expresados por\(2/\sqrt{nc}\,\)... ¹¹

Ejercicios

\(\PageIndex{1}\)Se van a organizar cuatro personas seguidas para que se les tome una foto. ¿De cuántas maneras se puede hacer esto?

\(\PageIndex{2}\)Un fabricante de automóviles tiene cuatro colores disponibles para exteriores de automóviles y tres para interiores. ¿Cuántas combinaciones de colores diferentes puede producir?

\(\PageIndex{3}\)En una computadora digital, un bit es uno de los enteros {0,1}, y una palabra es cualquier cadena de 32 bits. ¿Cuántas palabras diferentes son posibles?

\(\PageIndex{4}\)¿Cuál es la probabilidad de que al menos 2 de los presidentes de Estados Unidos hayan muerto el mismo día del año? Si apuestas a que esto ha sucedido, ¿ganarías tu apuesta?

\(\PageIndex{5}\)Hay tres rutas diferentes que conectan la ciudad A con la ciudad B. ¿De cuántas formas se puede hacer un viaje de ida y vuelta de A a B y de regreso? ¿De cuántas maneras se desea tomar una ruta diferente en el camino de regreso?

\(\PageIndex{6}\)Al organizar a las personas alrededor de una mesa circular, tomamos en cuenta sus asientos relativos entre sí, no la posición real de ninguna persona. Demuestre que\(n\) las personas se pueden organizar alrededor de una mesa circular\((n - 1)!\) de maneras.

\(\PageIndex{7}\)Cinco personas se suben a un elevador que se detiene en cinco pisos. Suponiendo que cada uno tiene la misma probabilidad de ir a cualquier piso, encuentre la probabilidad de que todos se bajen en diferentes pisos.

\(\PageIndex{8}\)Un conjunto finito\(\Omega\) tiene\(n\) elementos. Mostrar que si contamos el conjunto vacío y\(\Omega\) como subconjuntos, hay\(2^n\) subconjuntos de\(\Omega\).

\(\PageIndex{9}\)Una desigualdad más refinada para aproximar\(n!\) la da\[\sqrt{2\pi n}\left(\frac ne\right)^n e^{1/(12n + 1)} < n! < \sqrt{2\pi n}\left(\frac ne\right)^n e^{1/(12n)}\ .\] Escribe un programa de computadora para ilustrar esta desigualdad para\(n = 1\) a 9.

\(\PageIndex{10}\)Se baraja una baraja de cartas ordinarias y se reparten 13 cartas. ¿Cuál es la probabilidad de que la última carta repartida sea un as?

\(\PageIndex{11}\)Hay\(n\) aspirantes para el director de computación. Los aspirantes son entrevistados de manera independiente por cada miembro del comité de búsqueda de tres personas y clasificados de 1 a\(n\). Se contratará a un candidato si ocupa el primer lugar por al menos dos de los tres entrevistadores. Encuentra la probabilidad de que un candidato sea aceptado si los miembros del comité realmente no tienen capacidad para juzgar a los candidatos y simplemente clasificar a los candidatos al azar. En particular, compare esta probabilidad para el caso de tres candidatos y el caso de diez candidatos.

\(\PageIndex{12}\)Una orquesta sinfónica tiene en su repertorio 30 sinfonías de Haydn, 15 obras modernas y 9 sinfonías de Beethoven. Su programa siempre consiste en una sinfonía de Haydn seguida de una obra moderna, y luego una sinfonía de Beethoven.

1. ¿Cuántos programas diferentes puede jugar?
2. ¿Cuántos programas diferentes hay si las tres piezas se pueden tocar en cualquier orden?
3. ¿Cuántos programas diferentes de tres piezas hay si se puede jugar más de una pieza de la misma categoría y se pueden jugar en cualquier orden?

\(\PageIndex{13}\)Un estado determinado tiene placas que muestran tres números y tres letras. Cuántas placas diferentes son posibles

1. si los números deben venir antes de las letras?
2. si no hay restricción sobre dónde aparecen las letras y los números?

\(\PageIndex{14}\)La puerta del centro de cómputos tiene una cerradura la cual tiene cinco botones numerados del 1 al 5. La combinación de números que abre la cerradura es una secuencia de cinco números y se restablece cada semana.

1. ¿Cuántas combinaciones son posibles si cada botón debe usarse una vez?
2. Supongamos que la cerradura también puede tener combinaciones que requieran que presione dos botones simultáneamente y luego los otros tres uno a la vez. ¿Cuántas combinaciones más permite esto?

\(\PageIndex{15}\)Un centro de computación cuenta con 3 procesadores que reciben\(n\) trabajos, con los trabajos asignados a los procesadores puramente al azar para que todas las asignaciones\(3^n\) posibles sean igualmente probables. Encuentra la probabilidad de que exactamente un procesador no tenga trabajos.

\(\PageIndex{16}\)Demostrar que al menos dos personas en Atlanta, Georgia, tienen las mismas iniciales, asumiendo que nadie tiene más de cuatro iniciales.

\(\PageIndex{17}\)Encuentra una fórmula para la probabilidad de que entre un conjunto de\(n\) personas, al menos dos tengan sus cumpleaños en el mismo mes del año (asumiendo que los meses son igualmente probables para cumpleaños).

\(\PageIndex{18}\)Considerar el problema de encontrar la probabilidad de más de una coincidencia de cumpleaños en un grupo de\(n\) personas. Estos incluyen, por ejemplo, tres personas con el mismo cumpleaños, o dos parejas de personas con el mismo cumpleaños, o coincidencias mayores. Muestra cómo podrías calcular esta probabilidad, y escribir un programa de computadora para llevar a cabo este cálculo. Usa tu programa para encontrar el menor número de personas para lo cual sería una apuesta favorable que habría más de una coincidencia de cumpleaños.

\(\PageIndex{19}\)Supongamos que en el planeta Zorg un año tiene\(n\) días, y que las formas de vida allí son igualmente probables de haber eclosionado en cualquier día del año. Nos gustaría estimar\(d\), que es el número mínimo de formas de vida necesarias para que la probabilidad de que al menos dos compartan un cumpleaños supere 1/2.

1. En Ejemplo\(\PageIndex{3}\), se demostró que en un conjunto de\(d\) formas de vida, la probabilidad de que no dos formas de vida compartan un cumpleaños es\[ \frac{(n)_d}{n^d} ,\]
2. donde\((n)_d = (n)(n-1)\cdots (n-d+1)\). Por lo tanto, nos gustaría establecer esto igual a 1/2 y resolver para\(d\).
3. Usando la fórmula de Stirling, demuestre que\[
   ParseError: EOF expected (click for details)

   Callstack:
       at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/03:_Combinatoria/3.01:_Permutaciones), /content/body/div[11]/ol[4]/li[3]/span/span, line 1, column 4
   

   \sim \biggl(1 + {d\over{n-d}}\biggr)^{n-d + 1/2} e^{-d}\ .\]
4. Ahora toma el logaritmo de la expresión de la derecha, y usa el hecho de que para valores pequeños de\(x\), tenemos\[\log(1+x) \sim x - {{x^2}\over 2}\ .\] (Estamos utilizando implícitamente el hecho de que\(d\) es de menor orden de magnitud que\(n\). También utilizaremos este hecho en la parte (d).)
5. Establecer la expresión encontrada en la parte (c) igual a\(-\log(2)\), y resolver para\(d\) como una función de\(n\), mostrando así que\[d \sim \sqrt{2(\log 2)\,n}\ .\]: Si se utilizan las tres summands en la expresión encontrada en la parte (b), se obtiene una ecuación cúbica en\(d\). Si se tira el más pequeño de los tres términos, se obtiene una ecuación cuadrática en\(d\).
6. Utilice una computadora para calcular los valores exactos de\(d\) para diversos valores de\(n\). Comparar estos valores con los valores aproximados obtenidos mediante el uso de la respuesta a la parte d).

i (\ PageIndex {20}\) En una conferencia matemática, diez participantes se sientan aleatoriamente alrededor de una mesa circular para las comidas. Mediante simulación, estime la probabilidad de que no haya dos personas sentadas una al lado de la otra tanto en el almuerzo como en la cena. ¿Se puede hacer una conjetura inteligente para el caso de\(n\) los participantes cuando\(n\) es grande?

\(\PageIndex{21}\)Modificar el programa AllPermutations para contar el número de permutaciones de\(n\) objetos que tienen exactamente puntos\(j\) fijos para\(j = 0\), 1, 2,...,\(n\). Ejecuta tu programa para\(n = 2\) hasta 6. Hacer una conjetura para la relación entre el número que tiene 0 puntos fijos y el número que tiene exactamente 1 punto fijo. Una prueba de la conjetura correcta se puede encontrar en Wilf. ¹²

\(\PageIndex{22}\)El Sr. Wimplle Dimple, uno de los fabricantes de relojes más prestigiosos de Londres, ha llegado a Sherlock Holmes en pánico, al descubrir que alguien ha estado produciendo y vendiendo falsificaciones de crudo de su reloj más vendido. Las 16 falsificaciones descubiertas hasta ahora llevan números estampados, todos los cuales caen entre 1 y 56, y Dimple está ansioso por conocer la extensión de la obra del falsificador. Todos los presentes coinciden en que parece razonable suponer que las falsificaciones producidas hasta ahora llevan números consecutivos de 1 a cualquiera que sea el número total.

“Con la barbilla arriba, hoyuelo”, opina el Dr. Watson. “No debería preocuparme demasiado si yo fuera tú; el Principio de Máxima Probabilidad, que estima el número total como precisamente el que da la probabilidad más alta para la serie de números encontrados, sugiere que supongamos 56 en sí mismo como el total. Así, sus falsificadores no son una gran operación, y los tendremos seguros tras las rejas antes de que su negocio sufra significativamente”.

“Cosas, tonterías, y molesta tus principios elegantes, Watson”, contrata Holmes. “Cualquiera puede ver que, por supuesto, debe haber bastantes más de 56 relojes, por lo que las probabilidades de que hayamos descubierto precisamente el reloj de mayor número hecho son risiblemente insignificantes. Una suposición mucho mejor sería 56”.

1. Demostrar que Watson tiene razón que el Principio de Máxima Probabilidad da 56.
2. Escribe un programa de computadora para comparar las estrategias de adivinación de Holmes y Watson de la siguiente manera: fijar un total\(N\) y elegir 16 enteros aleatoriamente entre 1 y\(N\). Vamos a\(m\) denotar el más grande de estos. Entonces la suposición de Watson para\(N\) es\(m\), mientras que la de Holmes es\(2m\). Vea cuál de estos está más cerca\(N\). Repita este experimento (con\(N\) todavía fijo) cien o más veces, y determine la proporción de veces que cada uno se acerca. ¿De quién parece ser la mejor estrategia?

\(\PageIndex{23}\)Barbara Smith está entrevistando a candidatos para ser su secretaria. Al entrevistar a los candidatos, puede determinar el rango relativo de los candidatos pero no el rango verdadero. Así, si hay seis candidatos y su verdadero rango es 6, 1, 4, 2, 3, 5, (donde 1 es mejor) entonces después de haber entrevistado a los tres primeros candidatos los clasificaría 3, 1, 2. Al entrevistar a cada candidato, deberá aceptar o rechazar al candidato. Si no acepta al candidato después de la entrevista, el candidato se pierde para ella. Ella quiere decidir sobre una estrategia para decidir cuándo parar y aceptar a un candidato que maximice la probabilidad de conseguir el mejor candidato. Supongamos que hay\(n\) candidatos y llegan en orden de rango aleatorio.

1. ¿Cuál es la probabilidad de que Bárbara consiga la mejor candidata si entrevista a todos los candidatos? ¿Qué pasa si elige al primer candidato?
2. Supongamos que Bárbara decide entrevistar a la primera mitad de los candidatos y luego continuar entrevistando hasta conseguir un candidato mejor que cualquier candidato visto hasta ahora. Demuestre que tiene una probabilidad superior al 25 por ciento de terminar con la mejor candidata.

\(\PageIndex{24}\)Para la tarea descrita en el Ejercicio 23, se puede demostrar ¹³ que la mejor estrategia es pasar por encima de los primeros\(k - 1\) candidatos donde\(k\) está el entero más pequeño para el cual\[\frac 1k + \frac 1{k + 1} + \cdots + \frac 1{n - 1} \leq 1\ .\] Usando esta estrategia la probabilidad de obtener el mejor candidato es aproximadamente\(1/e = .368\). Escribe un programa para simular la entrevista de Barbara Smith si usa esta estrategia óptima, usando\(n = 10\), y mira si puedes verificar que la probabilidad de éxito es aproximadamente\(1/e\).