1.2: Principios Básicos de Conteo

\(\circ\) Exercise \(1\)

Cinco escuelas van a enviar a sus equipos de béisbol a un torneo, en el que cada equipo debe jugar entre sí exactamente una vez. ¿Cuántos juegos se requieren? (Pista).

\(\bullet\) Exercise \(2\)

Ahora algún número\(n\) de escuelas van a enviar a sus equipos de béisbol a un torneo, y cada equipo debe jugar uno al otro equipo exactamente una vez. Pensemos en los equipos como\(1\) numerados\(n\).

1. ¿En cuántos juegos\(1\) tiene que jugar el equipo?
2. ¿Cuántos juegos, aparte del de equipo\(1\), tiene que jugar el equipo dos?
3. ¿En cuántos juegos, aparte de los de\(i − 1\) los primeros equipos,\(i\) tiene que jugar el equipo?
4. En cuanto a sus respuestas a las partes anteriores de este problema, ¿cuál es el número total de juegos que se deben jugar?

\(\bullet\) Exercise \(3\)

Una de las escuelas que envía a su equipo al torneo tiene que mandar a sus jugadores desde cierta distancia, y así está haciendo sándwiches para que los integrantes del equipo coman en el camino. Hay tres opciones para el tipo de pan y cinco opciones para el tipo de relleno. ¿Cuántos tipos diferentes de sándwiches hay disponibles? (Pista).

\(+\) Exercise \(4\)

Un par ordenado\((a, b)\) consta de dos cosas que llamamos\(a\) y\(b\). Decimos que\(a\) es el primer miembro de la pareja y\(b\) es el segundo miembro de la pareja. Si\(M\) es un conjunto\(m\) -elemento y\(N\) es un conjunto\(n\) -elemento, ¿cuántos pares ordenados hay cuyo primer miembro está en\(M\) y cuyo segundo miembro está en\(N\)? ¿Este problema tiene algo que ver con alguno de los problemas anteriores?

\(\circ\) Exercise \(5\)

Dado que un sándwich por sí mismo es bastante aburrido, a los estudiantes de la escuela del Problema 3 se les ofrece la opción de una bebida (de entre cinco tipos diferentes), un sándwich y una fruta (de entre cuatro tipos diferentes). ¿De cuántas maneras puede un estudiante elegir los tres elementos ahora?

\(\bullet\) Exercise \(6\)

El entrenador del equipo en Problema 3 sabe de una heladería en el camino donde planea detenerse para comprar a cada miembro del equipo un cono de tres pisos. Hay\(12\) diferentes sabores de helado, y los conos de triple piso se hacen en conos de gofres caseros. Tener helado de chocolate como primicia inferior es diferente a tener helado de chocolate como la cucharada superior. ¿Cuántos conos de helado posibles van a estar disponibles para los miembros del equipo? ¿Cuántos conos con tres tipos diferentes de helado estarán disponibles? (Pista).

\(\bullet\) Exercise \(7\)

La idea de una función es omnipresente en las matemáticas. Una función\(f\) de un conjunto\(S\) a un conjunto\(T\) es una relación entre los dos conjuntos que asocia exactamente un miembro\(f(x)\) de\(T\) con cada elemento\(x\) en\(S\). Volveremos a las ideas de funciones y relaciones con más detalle y desde diferentes puntos de vista de vez en cuando. Sin embargo, la revisión rápida anterior probablemente debería dejarte responder estas preguntas. Si tiene dificultades con ellos, sería una buena idea ir ahora al Apéndice A y trabajar en la Sección A.1.1 que abarca esta definición con más detalle. También es posible que desee estudiar la Sección A.1.3 para aprender a visualizar las propiedades de las funciones. También retomaremos el tema de esta sección más adelante en este capítulo, pero con menos detalle que en el apéndice.

1. Utilizando\(f, g, \dotsb,\) para representar las diversas funciones, anota todas las diferentes funciones que puedas desde el conjunto\(\{1, 2\}\) hasta el conjunto\(\{a, b\}\). Por ejemplo, podrías comenzar con la función f dada por\(f(1) = a\),\(f(2) = b\). ¿Cuántas funciones hay del conjunto\({1, 2}\) al conjunto\(\{a, b\}\)? (Pista).
2. ¿Cuántas funciones hay desde el conjunto de tres elementos\(\{1, 2, 3\}\) hasta el conjunto de dos elementos\({a, b}\)? (Pista).
3. ¿Cuántas funciones hay desde el conjunto de dos elementos\(\{a, b\}\) hasta el conjunto de tres elementos\(\{1, 2, 3\}\)? (Pista).
4. ¿Cuántas funciones hay de un conjunto de tres elementos a un conjunto de\(12\) elementos?
5. Una función\(f\) se llama uno a uno o una inyección si siempre\(x\) es diferente de\(y\),\(f(x)\) es diferente de\(f(y)\). ¿Cuántas funciones uno a uno hay de un conjunto de tres elementos a un conjunto de\(12\) elementos?
6. Explicar la relación entre este problema y el Problema 6.

\(\bullet\) Exercise \(8\)

Un grupo de miembros del equipo hambrientos en Problema 6 nota que sería más económico comprar tres pintas de helado para que se partieran que comprar un cono de tres pisos para cada uno de ellos, y de esa manera obtendrían más helado. Le preguntan a su entrenador si pueden comprar tres pintas de helado.

1. ¿De cuántas maneras pueden elegir entre los sabores tres pintas de diferentes\(12\) sabores? (Pista).
2. ¿De cuántas maneras pueden elegir tres pintas si los sabores no tienen que ser diferentes? (Pista).

\(\bullet\) Exercise \(9\)

Se dice que dos conjuntos son disjuntos si no tienen elementos en común. Por ejemplo,\(\{1, 3, 12\}\) y\(\{6, 4, 8, 2\}\) son disjuntas, pero\(\{1, 3, 12\}\) y no lo\(\{3, 5, 7\}\) son. Se dice que tres o más conjuntos son mutuamente disjuntos si no hay dos de ellos que tengan elementos en común. ¿Qué se puede decir sobre el tamaño de la unión de un número finito de conjuntos finitos (mutuamente) disjuntos? ¿Esto tiene algo que ver con alguno de los problemas anteriores?

\(\bullet\) Exercise \(10\)

Los subconjuntos disgregados se definen en el Problema 9. ¿Qué se puede decir sobre el tamaño de la unión de conjuntos\(m\) (mutuamente) disjuntos, cada uno de tamaño\(n\)? ¿Esto tiene algo que ver con alguno de los problemas anteriores?

1.2.1: La suma y los principios del producto

Estos problemas contienen entre ellos los granos de muchas de las ideas fundamentales de la combinatoria. Por ejemplo, con suerte, acaba de afirmar el principio de suma (ilustrado en la Figura 1.2.1), y el principio de producto (ilustrado en la Figura 1.2.2) en los Problemas 9 y 10. Estos son dos de los principios más básicos de la combinatoria. Estos dos principios de conteo son la base sobre la cual desarrollaremos muchos otros principios de conteo.

Figura\(\PageIndex{1}\): La unión de estos dos conjuntos disjuntos tiene el tamaño 17. (Copyright; autor vía fuente)

Figura\(\PageIndex{2}\): La unión de cuatro conjuntos disjuntos de talla cinco. (Copyright; autor vía fuente)

Es posible que hayas notado algunas palabras y frases matemáticas estándar como set, par ordenado, función y así sucesivamente arrastrándose en los problemas. Uno de nuestros objetivos en estas notas es mostrar cómo la mayoría de los problemas de conteo pueden reconocerse como contar todos o algunos de los elementos de un conjunto de objetos matemáticos estándar. Por ejemplo, el Problema 4 pretende sugerir que la pregunta que hicimos en el Problema 3 era realmente un problema de contar todos los pares ordenados que consistían en una elección de pan y una elección de relleno. Usamos\(A \times B\) para representar el conjunto de todos los pares ordenados cuyo primer elemento está en\(A\) y cuyo segundo elemento está en\(B\) y llamamos\(A \times B\) el producto cartesiano de\(A\) y\(B\). Así puedes pensar en el Problema 4 como pedirte el tamaño del producto cartesiano de\(M\) y\(N\), es decir, pedirte contar el número de elementos de este producto cartesiano.

Cuando un conjunto\(S\) es una unión de conjuntos\(B_{1}, B_{2}, \dotsc , B_{m}\) disjuntos decimos que los conjuntos\(B_{1}, B_{2}, \dotsc , B_{m}\) son una partición del conjunto\(S\). Por lo tanto, una partición de\(S\) es un (tipo especial de) conjunto de conjuntos. Para que no nos encontremos confundiendo entre el conjunto\(S\) y los conjuntos\(B_{i}\) en los que lo hemos dividido, a menudo llamamos a los conjuntos\(B_{1}, B_{2}, \dotsc , B_{m}\) los bloques de la partición. En este lenguaje, el principio de suma dice que

si tenemos una partición de un conjunto finito\(S\), entonces el tamaño de\(S\) es la suma de los tamaños de los bloques de la partición.

El principio del producto dice que si tenemos una partición de un conjunto finito\(S\) en\(m\) bloques, cada uno de tamaño\(n\), entonces S tiene tamaño\(mn\).

Notarás que en nuestra declaración formal del principio de suma y producto hablamos de una partición de un conjunto finito. Podríamos modificar un poco nuestro lenguaje para cubrir tamaños infinitos, pero siempre que hablemos de tamaños de conjuntos en lo que sigue, estaremos trabajando con conjuntos finitos. Para evitar posibles complicaciones en el futuro, coincidamos en que cuando nos referimos al tamaño de un conjunto, estamos asumiendo implícitamente que el conjunto es finito. Hay otra versión del principio del producto que se aplica directamente en problemas como el Problema 5 y el Problema 6, donde no solo estábamos tomando una unión de\(m\) conjuntos disjuntos de tamaño\(n\), sino más bien m conjuntos disjuntos de tamaño\(n\), cada uno de los cuales era una unión de\(m'\) conjuntos disjuntos de tamaño \(n'\). Esta es una forma inconveniente de tener que pensar en un problema de conteo, por lo que podemos reformular el principio del producto en términos de una secuencia de decisiones:

\(\bullet\) Exercise \(11\)

Si hacemos una secuencia de\(m\) elecciones para las cuales

• hay\(k_{1}\) posibles primeras opciones, y
• para cada forma de tomar las primeras\(i - 1\) decisiones, hay\(k_{i}\) formas

para hacer la\(i^{\text{th}}\) elección, entonces ¿de cuántas maneras podemos hacer nuestra secuencia de elecciones? (No necesita probar su respuesta correcta en este momento.)

El principio de conteo que diste en el Problema 11 se llama principio general del producto. Describiremos una prueba del principio general del producto a partir del principio del producto original en Problema 80. Hasta entonces, aceptémoslo simplemente como otro principio de conteo. Por ahora, fíjate lo más fácil que nos facilita explicar por qué multiplicamos las cosas que hicimos en el Problema 5 y el Problema 6.

\(\rightarrow\) Exercise \(12\)

Un club de tenis tiene\(2n\) miembros. Queremos emparejar a los miembros por dos para partidos de singles.

1. ¿De cuántas maneras podemos emparejar a todos los miembros del club? (Pista: considerar los casos de\(2\),\(4\), y\(6\) miembros.) (Pista).
2. Supongamos que además de especificar quién juega a quién, por cada pareja decimos quién sirve primero. Ahora bien, ¿de cuántas formas podemos especificar nuestros pares?

\(+\) Exercise \(13\)

Volvamos ahora al Problema 7 y justificemos —o tal vez acabemos— nuestra respuesta a la pregunta sobre el número de funciones de un conjunto de tres elementos a un conjunto\(12\) de elementos.

1. ¿Cómo puedes justificar tu respuesta en el Problema 7 a la pregunta “¿Cuántas funciones hay de un conjunto de tres elementos (digamos\([3] = \{1, 2, 3\})\) a un conjunto de doce elementos (digamos\([12]\))? ”
2. A partir de los ejemplos que has visto hasta ahora, haz una conjetura sobre cuántas funciones hay desde el set\([m] = \{1, 2, 3,\dotsc ,m\}\) hasta el momento\([n] = \{1, 2, 3,\dotsc, n\}\) y demuéstralo.
3. Una notación común para el conjunto de todas las funciones de un conjunto\(M\) a un conjunto\(N\) es\(N^{M}\). ¿Por qué es esta una buena notación?

\(+\) Exercise \(14\)

Ahora supongamos que estamos pensando en un conjunto\(S\) de funciones\(f\) de [\(m\)] a algún conjunto\(X\). (Por ejemplo, en el Problema 6 estábamos pensando en el conjunto de funciones desde los tres posibles lugares para las primicias en un cono de helado hasta\(12\) sabores de helado.) Supongamos que hay\(k_{1}\) opciones para\(f(1)\). (En el Problema 6,\(k_{1}\) fue\(12\), porque había\(12\) formas de elegir la primera primicia.) Supongamos que para cada elección de\(f(1)\) hay\(k_{2}\) opciones para f (2). (Por ejemplo, en el Problema 6\(k_{2}\) era\(12\) si el segundo sabor podía ser el mismo que el primero, pero\(k_{2}\) era\(11\) si los sabores tenían que ser diferentes). En general, supongamos que para cada elección de\(f(1), f(2), \dotsc, f(i − 1)\), hay\(k_{i}\) opciones para\(f(i)\). (Por ejemplo, en el Problema 6, si los sabores tienen que ser diferentes, entonces para cada elección de\(f(1)\) y\(f(2)\), hay\(10\) opciones para\(f(3)\).)

Lo que hemos asumido hasta ahora sobre las funciones en\(S\) puede resumirse como
• Hay\(k_{1}\) opciones para\(f(1)\).
• Para cada elección de\(f(1), f(2), \dotsc , f(i − 1)\), hay\(k_{i}\) opciones para\(f(i)\).

¿Cuántas funciones hay en el set\(S\)? ¿Hay alguna diferencia práctica entre el resultado de este problema y el principio general del producto?

El punto del Problema 14 es que el principio general del producto se puede afirmar informalmente, como lo hicimos originalmente, o como una declaración sobre el conteo de conjuntos de objetos matemáticos concretos estándar, es decir, funciones.

\(\rightarrow\) Exercise \(15\)

Un carro de montaña rusa tiene\(n\) filas de asientos, cada uno de los cuales tiene espacio para dos personas. Si\(n\) hombres y\(n\) mujeres se suben al auto con un hombre y una mujer en cada fila, ¿de cuántas maneras pueden elegir sus asientos? (Pista).

\(+\) Exercise \(16\)

¿Cómo se aplica el principio general del producto al Problema 6?

\(\bullet\) Exercise \(17\)

¿De cuántas maneras podemos repartir piezas\(k\) distintas de fruta a\(n\) los niños (sin restricción de cuántas piezas de fruta puede obtener un niño)?

\(\bullet\) Exercise \(18\)

¿Cuántos subconjuntos tiene un conjunto\(S\) con\(n\) elementos? (Pista).

\(\circ\) Exercise \(19\)

Asumiendo\(k \leq n\), ¿de cuántas maneras podemos repartir\(k\) distintos trozos de fruta a\(n\) los niños si cada niño puede obtener como máximo uno? ¿Cuál es el número si\(k > n\)? Asumir para ambas preguntas que repartimos toda la fruta. (Pista).

\(\bullet\) Exercise \(20\)

Otro nombre para una lista, en un orden específico, de cosas\(k\) distintas elegidas de un conjunto\(S\) es una permutación\(k\) -elemento de\(S\). También podemos pensar en una permutación\(k\) -elemento de\(S\) como una función uno a uno (o, en otras palabras, inyección) de\(k = \{1, 2,\dotsc, k\}\) a\(S\). ¿Cuántas permutaciones\(k\) -elemento tiene un conjunto\(n\) -element? (Para este problema es natural asumir\(k \leq n\). Sin embargo, la pregunta tiene sentido aunque sea\(k > n\).) ¿Cuál es el número de permutaciones\(k\) -elemento de un conjunto de\(n\) elementos si\(k > n\)? (Pista).

Hay una variedad de notaciones diferentes para el número de permutaciones\(k\) -elemento de un conjunto de\(n\) elementos. El que usaremos fue introducido por Don Knuth; es decir\(n^{\underline{k}}\), leer “\(n\)a la\(k\) caída” o “\(n\)a la\(k\) baja”. ” En Problema 20 es posible que hayas demostrado que

\[n^{\underline{k}} = n(n - 1) \dotsm (n - k + 1) = \prod^{k}_{i = 1}(n - i + 1) \label{1.2.1}\].

Es estándar llamar\(n^{\underline{k}}\) al\(k\) -ésimo poder factorial descendente de\(n\), lo que explica por qué usamos la notación exponencial. Lo llamamos un poder factorial ya que\(n^{\underline{n}} = n(n - 1) \dotsm 1\), al que llamamos\(n\) -factorial y denotamos por\(n!\). Si no está familiarizado con la\(\pi\) notación, o notación de producto que introdujimos para los productos en la ecuación\ ref {1.2.1}, funciona igual que la notación Sigma funciona para sumaciones.

\(\bullet\) Exercise \(21\)

Expresar\(n^{\underline{k}}\) como cociente de factoriales.

\(\rightarrow\) Exercise \(22\)

¿Cómo debemos definir\(n^{\underline{k}}\)?

1.2.2: Funciones y Gráficas Dirigidas

Como otro ejemplo de cómo el lenguaje matemático estándar se relaciona con los problemas de conteo, el Problema 7 le pidió explícitamente que relacionara la idea de contar funciones con la cuestión del Problema 6. Probablemente hayas aprendido en álgebra o cálculo a dibujar gráficas en el plano cartesiano de funciones desde un conjunto de números hasta un conjunto de números. Tal vez recuerde cómo podemos determinar si una gráfica es una gráfica de una función examinando si cada línea recta vertical cruza la gráfica como mucho una vez. También puede recordar cómo podemos determinar si tal función es uno a uno examinando si cada línea recta horizontal cruza la gráfica como máximo una vez. Las funciones que tratamos a menudo involucran objetos que no son números, y a menudo serán funciones de un conjunto finito a otro. Por lo tanto, las gráficas en el plano cartesiano a menudo no estarán disponibles para nosotros para visualizar funciones. Sin embargo, existe otro tipo de gráfico llamado grafo dirigido o dígrafo que es especialmente útil cuando se trata de funciones entre conjuntos finitos. Abordamos este tema con más detalle en el Apéndice A, particularmente en la Sección A.1.2 y la Sección A.1.3. En la Figura 1.2.3 mostramos varios ejemplos de dígrafos de funciones.

Figura\(\PageIndex{3}\): ¿Qué es un dígrafo de una función? (Copyright; autor vía fuente)

Si tenemos una función\(f\) de un conjunto\(S\) a un conjunto\(T\), dibujamos una línea de puntos o círculos, llamados vértices para representar los elementos de\(S\) y otra (generalmente paralela) línea de vértices para representar los elementos de\(T\). Luego dibujamos una flecha desde el vértice para\(x\) hasta el vértice para\(y\) si\(f(x) = y\). En ocasiones, como en la parte (e) de la figura, si tenemos una función de un conjunto\(S\) a sí mismo, dibujamos solo un conjunto de vértices que representan los elementos de\(S\), en cuyo caso podemos tener flechas tanto entrando como saliendo de un vértice dado. Como ves, el dígrafo puede ser más esclarecedor en este caso si experimentamos con la función para encontrar una buena ubicación de los vértices en lugar de ponerlos en fila. Observe que existe una prueba simple para saber si un dígrafo cuyos vértices representan los elementos de los conjuntos\(S\) y\(T\) es el dígrafo de una función de\(S\) a\(T\). Debe haber una y sólo una flecha dejando cada vértice del dígrafo representando un elemento de\(S\). El hecho de que haya una flecha significa que\(f(x)\) se define para cada una\(x\) en\(S\). El hecho de que solo haya una flecha significa que cada una\(x\) de ellas\(S\) está relacionada exactamente con un elemento de\(T\). (Tenga en cuenta que estos comentarios también se mantienen si tenemos una función de\(S\) a\(S\) y dibujamos solo un conjunto de vértices que representan los elementos de\(S\).) Para mayor discusión de funciones y dígrafos véanse las Secciones A.1.1 y A.1.2 del Apéndice A.

\(\circ\) Exercise \(23\)

Dibuja el dígrafo de la función del conjunto\(\{\text{Alice, Bob, Dawn, Bill}\}\) al conjunto\(\{A, B, C, D, E\}\) dado por

\(f(X) = \text{the first letter of the name X}\).

\(\bullet\) Exercise \(24\)

Una función\(f : S \longrightarrow T\) se llama una función onto o sobrejección si cada elemento de\(T\) es\(f(x)\) para algunos\(x \in S\). Elija un conjunto\(S\) y un conjunto\(T\) para que pueda dibujar el dígrafo de una función desde\(S\) hasta\(T\) que sea uno a uno pero no sobre, y dibuje el dígrafo de dicha función.

\(\circ\) Exercise \(25\)

Elija un conjunto\(S\) y un conjunto\(T\) para que pueda dibujar el dígrafo de una función desde\(S\) hasta\(T\) que está en pero no uno a uno, y dibujar el dígrafo de dicha función.

\(\bullet\) Exercise \(26\)

26. Los dígrafos de funciones nos ayudan a visualizar las ideas de funciones uno a uno y sobre funciones. (Pista).

1. ¿Qué\(Y\) aspecto tiene el dígrafo de una función uno a uno (inyección) de un conjunto finito\(X\) a un conjunto finito? (Busque una prueba algo similar a la que describimos para cuando un dígrafo es el dígrafo de una función).
2. ¿Qué aspecto tiene el dígrafo de una función onto?
3. ¿Qué\(T\) aspecto tiene el dígrafo de una función uno a uno y a partir de un conjunto finito\(S\) a un conjunto?

\(\bullet\) Exercise \(27\)

La palabra permutación en realidad se usa de dos maneras diferentes en matemáticas. Una permutación de un conjunto\(S\) es una función uno a uno de\(S\) hacia\(S\). ¿Cuántas permutaciones tiene un conjunto\(n\) -element?

Observe que existe una gran consistencia entre el uso de la palabra permutación en el Problema 27 y el uso en el Problema 20. Si tenemos alguna manera\(a_{1}, a_{2},\dotsc, a_{n}\) de enumerar nuestro conjunto\(S\), entonces cualquier otra lista nos\(b_{1}, b_{2},\dotsc, b_{n}\) da la permutación de\(S\) cuya regla es\(f(a_{i}) = b_{i}\), y cualquier permutación de\(S\), digamos la que nos\(g(a_{i}) = c_{i}\) da da una lista\(c_{1}, c_{2},\dotsc, c_{n}\) de\(S\). Por lo tanto, realmente hay muy poca diferencia entre la idea de una permutación de\(S\) y una permutación\(n\) -elemento de\(S\) cuándo\(n\) es el tamaño de\(S\).

1.2.3: El Principio de Biyección

Otro nombre para una función uno a uno y onto es bijección. Los dígrafos marcados (a), (b) y (e) en la Figura 1.2.3 son dígrafos de biyecciones. La descripción en Problema 26c del dígrafo de una biyección de\(X\) a\(Y\) ilustra uno de los principios fundamentales de la matemática combinatoria, el principio de bijección:

Definición: Principio de Biyección

Dos conjuntos tienen el mismo tamaño si y sólo si hay una bijección entre ellos.

Es sorprendente cómo este principio de sonido inocente nos guía a encontrar información sobre algunas pruebas que por lo demás serían muy complicadas.

1.2.4: Recuento de subconjuntos de un conjunto

Ejercicio\(28\)

La representación binaria de un número\(m\) es una lista, o cadena,\(a_{1} a_{2} \dotsb a_{k}\) de ceros y unos tales que\(m = a_{1}2^{k−1} + a_{2}2^{k−2} + \dotsb + a_{k}2^{0}\). Describir una biyección entre las representaciones binarias de los números enteros entre\(0\) y\(2^{n} − 1\) y los subconjuntos de un conjunto\(n\) de elementos. ¿Qué le dice esto sobre el número de subconjuntos del conjunto\(n\) -element [\(n\)]? (Pista).

Observe que la primera pregunta del Problema 8 le pidió el número de formas de elegir un subconjunto de tres elementos de un subconjunto de\(12\) elementos. Es posible que haya visto una notación como\(\binom{n}{k}, C(n, k)\), o\(_nC_k\) que representa el número de formas de elegir un subconjunto\(k\) -element de un conjunto\(n\) -element. El número\(\binom{n}{k}\) se lee como “n elige k” y se llama coeficiente binomial por razones que veremos más adelante. Otra forma frecuente de leer la notación del coeficiente binomial es “el número de combinaciones de\(n\) cosas tomadas\(k\) a la vez”. No vamos a utilizar esta forma de leer la notación. Se le va a pedir que construya dos bijecciones que se relacionen con estos números y que averiguaran qué fórmula famosa prueban. Vamos a pensar en subconjuntos del conjunto\(n\) -element\([n] = \{1, 2, 3, . . . , n\}\). Como ejemplo, el conjunto de subconjuntos de dos elementos de\([4]\) es

\[\{\{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\}\}\].

Este ejemplo nos dice eso\(\binom{4}{2} = 6\).

\(\bullet\) Exercise \(29\)

29. Dejar\(C\) ser el conjunto de subconjuntos\(k\) -elemento de\([n]\) que contienen el número\(n\), y dejar\(D\) ser el conjunto de\(k\) -elementos subconjuntos de\([n]\) que no contienen\(n\).

1. Let\(C'\) Ser el conjunto de\((k − 1)\) -elementos subconjuntos de\([n − 1]\). Describir una biyección de C a C0. (Una descripción verbal está bien.)
2. Let\(D'\) Ser el conjunto de\(k\) -elementos subconjuntos de\([n − 1] = \{1, 2, \dotsc, n − 1\}\). Describir una biyección de\(D\) a\(D'\). (Una descripción verbal está bien.)
3. Con base en las dos partes anteriores, expresar los tamaños de\(C\) y\(D\) en términos de coeficientes binomiales que involucran\(n − 1\) en lugar de\(n\).
4. Aplicar el principio de suma a\(C\)\(D\) y obtener una fórmula que exprese\(\binom{n}{k}\) en términos de dos coeficientes binomiales que implican\(n − 1\). Acabas de derivar la Ecuación Pascal que es la base del famoso Triángulo de Pascal.

1.2.5: Triángulo de Pascal

La Ecuación Pascal que derivaste en el Problema 29 nos da el triángulo en la Figura 1.2.4. Esta cifra tiene el número de subconjuntos\(k\) -elemento de un conjunto\(n\) -elemento como el número\(k\)\(n\) th sobre en la fila th (llamamos a la fila superior la fila cero y la entrada inicial de una fila el número cero sobre). Verás que tu fórmula no dice nada sobre\(\binom{n}{k}\) si\(k = 0\) o\(k = n\), pero de lo contrario dice que cada entrada es la suma de las dos que están por encima y justo a la izquierda o a la derecha.

Figura\(\PageIndex{4}\): Triángulo de Pascal. (Copyright; autor vía fuente)

Ejercicio\(30\)

Sólo para la práctica, ¿cuál es la siguiente fila del triángulo de Pascal?

\(\rightarrow\) Exercise \(31\)

Sin escribir completamente las filas, escriba lo suficiente del triángulo de Pascal para obtener una respuesta numérica para la primera pregunta del Problema 8. (Pista).

Es menos común ver el triángulo de Pascal como un triángulo rectángulo, pero en realidad hace que tu fórmula sea más fácil de interpretar. En el Triángulo Recto de Pascal, el elemento en fila\(n\) y columna\(k\) (con la convención de que la primera fila es la fila cero y la primera columna es la columna cero) es\(\binom{n}{k}\). En este caso, tu fórmula dice que cada entrada en una fila es la suma de la anterior y la de arriba y a la izquierda, excepto las entradas más a la izquierda y a la derecha de una fila, para lo cual eso no tiene sentido. Dado que la entrada más a la izquierda es\(\binom{n}{0}\) y la entrada más a la derecha es\(\binom{n}{n}\), estas entradas son ambas una (para ver por qué, pregúntese cuántos subconjuntos\(0\) -elementos y cuántos subconjuntos de n-elementos tiene un conjunto de n elementos), y su fórmula le dice entonces cómo rellenar el resto de la tabla.

Cuadro 1.2.1: Triángulo Recto de Pascal
	\(k=0\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)
\(n=0\)	\(1\)
\(1\)	\(1\)	\(1\)
\(2\)	\(1\)	\(2\)	\(1\)
\(3\)	\(1\)	\(3\)	\(3\)	\(1\)
\(4\)	\(1\)	\(4\)	\(6\)	\(4\)	\(1\)
\(5\)	\(1\)	\(5\)	\(10\)	\(10\)	\(5\)	\(1\)
\(6\)	\(1\)	\(6\)	\(15\)	\(20\)	\(15\)	\(6\)	\(1\)
\(7\)	\(1\)	\(7\)	\(21\)	\(35\)	\(35\)	\(21\)	\(7\)	\(1\)

Al ver este triángulo rectángulo nos lleva a preguntarnos si existe alguna manera natural de extender el triángulo rectángulo a un rectángulo. Si tuviéramos una tabla rectangular de coeficientes binomiales, contando la primera fila como fila cero (i.e.,\(n = 0\)) y la primera columna como columna cero (i.e.,\(k = 0\)), las entradas que aún no tenemos son valores de\(\binom{n}{k}\) for\(k > n\). Pero, ¿cuántos subconjuntos de\(k\) elementos -elemento tiene un conjunto de n elementos if\(k > n\)? La respuesta, por supuesto, es cero, así que todas las demás entradas que rellenaríamos serían cero, dándonos la matriz rectangular en la Tabla 1.2.2. Es sencillo comprobar que la Ecuación de Pascal ahora funciona para todas las entradas en el rectángulo que tienen una entrada por encima de ellas y una entrada arriba y a la izquierda.

Cuadro 1.2.2: Rectángulo de Pascal
	\(k=0\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)
\(n=0\)	\(1\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)
\(1\)	\(1\)	\(1\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)
\(2\)	\(1\)	\(2\)	\(1\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)
\(3\)	\(1\)	\(3\)	\(3\)	\(1\)	\(0\)	\(0\)	\(0\)	\(0\)
\(4\)	\(1\)	\(4\)	\(6\)	\(4\)	\(1\)	\(0\)	\(0\)	\(0\)
\(5\)	\(1\)	\(5\)	\(10\)	\(10\)	\(5\)	\(1\)	\(0\)	\(0\)
\(6\)	\(1\)	\(6\)	\(15\)	\(20\)	\(15\)	\(6\)	\(1\)	\(0\)
\(7\)	\(1\)	\(7\)	\(21\)	\(35\)	\(35\)	\(21\)	\(7\)	\(1\)

\(\rightarrow\) Exercise \(32\)

Porque nuestra definición nos dijo que\(\binom{n}{k}\) es\(0\) cuando\(k > n\), obtuvimos una tabla rectangular de números que satisface la Ecuación Pascal.

1. ¿Hay alguna otra forma de definir\(\binom{n}{k}\) cuándo\(k > n\) para obtener una mesa rectangular que concuerde con el Triángulo Recto de Pascal\(k \leq n\) y satisfaga la Ecuación Pascal? (Pista).
2. Supongamos que queremos extender el Rectángulo de Pascal hacia la izquierda y definir\(\binom{n}{k}\) para\(n \geq k\) y para\(k > 0\) eso\(−k < 0\). ¿Qué debemos poner en la fila n y columna\(−k\) del Rectángulo de Pascal para que la Ecuación Pascal se mantenga verdadera? (Pista).
3. * ¿Qué debemos poner en fila\(−n\) (supongamos que n es positivo) y columna\(k\) o columna\(−k\) para que la Ecuación Pascal continúe manteniéndose? ¿Tenemos alguna libertad de elección? (Pista).

Ejercicio\(33\)

Hay otra bijección que nos permite probar que un conjunto de tamaños\(n\) tiene\(2^{n}\) subconjuntos. Es decir, para cada subconjunto S de\([n] = \{1, 2, . . . , n\}\), definir una función (tradicionalmente denotada por\(\chi_{S}\)) de la siguiente manera. ^a

\(\chi_{S}(i)= \begin{cases} 1, & \text{if}\ i \in S \\ 0, & \text{if}\ i \notin S \end{cases}\)

La función\(\chi_{S}\) se llama la función característica de\(S\). Observe que la función característica es una función de\([n]\) a\(\{0, 1\}\).

1. Para la práctica, considere la función\(\chi_{\{1,3\}}\) para el subconjunto\(\{1, 3\}\) del conjunto\(\{1, 2, 3, 4\}\). ¿Qué son
   1. \(\chi_{\{1,3\}}(1)\)?
   2. \(\chi_{\{1,3\}}(2)\)?
   3. \(\chi_{\{1,3\}}(3)\)?
   4. \(\chi_{\{1,3\}}(4)\)?
2. Definimos una función\(f\) desde el conjunto de subconjuntos de\([n] = \{1, 2, . . . , n\}\) hasta el conjunto de funciones de [n] a {0, 1} por f (S) = S. Explicar por qué f es una biyección.
3. ¿Por qué el hecho de que\(f\) sea una bijección prueba que\([n]\) tiene\(2^{n}\) subconjuntos?

En Problemas 18, 28 y 33 diste tres pruebas del siguiente teorema.

Teorema\(\PageIndex{1}\)

El número de subconjuntos de un conjunto\(n\) -element es\(2^{n}\).

Prueba

Las pruebas del Problema 28 y 33 utilizan esencialmente la misma biyección, pero interpretan secuencias de ceros y unos de manera diferente, y así terminan siendo pruebas diferentes. Daremos otra prueba más, utilizando bijecciones similares a las que usamos para probar la Ecuación de Pascal, al inicio del Capítulo 2.

1.2.6: El principio del cociente

\(\bullet\) Exercise \(34\)

Como señalamos en el Problema 29, la primera pregunta del Problema 8 nos pidió el número de subconjuntos de tres elementos de un conjunto de doce elementos. Pudimos usar la Ecuación Pascal para obtener una respuesta numérica a esa pregunta. Si hubiéramos tenido veinte o treinta sabores de helado para elegir, usar la Ecuación Pascal para obtener nuestra respuesta habría supuesto un poco más de trabajo. Hemos visto como el principio general del producto nos da una respuesta al Problema 6. Así podríamos pensar que el número de formas de elegir un conjunto de tres elementos a partir de\(12\) elementos es el número de formas de elegir el primer elemento multiplicado por el número de formas de elegir el segundo elemento por el número de formas de elegir el tercer elemento, que es\(12 \cdot 11 \cdot 10 = 1320\). No obstante, nuestro resultado en el Problema 29 demuestra que esto está mal.

1. ¿Qué es lo que es diferente entre la cantidad de formas de apilar el helado en un cono de tres pisos con tres sabores diferentes de helado y la cantidad de formas de simplemente elegir tres sabores diferentes de helado?
2. En particular, ¿cuántos conos de tres pisos diferentes usan vainilla, chocolate y fresa? (Por supuesto, cualquiera de los tres sabores distintos podrían sustituir a la vainilla, el chocolate y la fresa sin cambiar la respuesta).
3. Usando su respuesta de la parte 34b, calcule el número de formas de elegir tres sabores diferentes de helado (de doce sabores) a partir de la cantidad de formas de elegir un cono de tres pisos con tres sabores diferentes (de doce sabores).

\(\bullet\) Exercise \(35\)

En base a lo que observaste en el Problema 34c, ¿cuántos\(k\) subconjuntos de elementos tiene un conjunto\(n\) -element?

\(\rightarrow\) Exercise \(36\)

La fórmula que probaste en el Problema 35 es simétrica en\(k\) y\(n−k\); es decir, da el mismo número para\(n \choose k\) que da para\(n \choose n-k\). Siempre que dos cantidades son contadas por la misma fórmula, es bueno para nuestra visión encontrar una bijección que demuestre que los dos conjuntos que se están contando tienen el mismo tamaño. De hecho, este es un principio rector de la investigación en matemáticas combinatorias. Encuentra una bijección que demuestre que\(n \choose k\) es igual\(n \choose n-k\). (Pista).

\(\bullet\) Exercise \(37\)

¿De cuántas maneras podemos repartir\(k\) (idénticas) pelotas de ping-pong a n niños si cada niño puede obtener como máximo una? (Pista).

\(\bullet\) Exercise \(38\)

¿De cuántas maneras n personas pueden sentarse alrededor de una mesa redonda? (Supongamos que cuando la gente está sentada alrededor de una mesa redonda, lo único que realmente importa es quién está a la derecha de cada persona. Por ejemplo, si podemos conseguir un arreglo de personas alrededor de la mesa de otro haciendo que todos se levanten y se muevan al lugar correcto y se sienten de nuevo, entonces obtenemos un arreglo equivalente de personas. Observe que puede obtener una lista de una disposición de asientos marcando un lugar en la mesa y luego enumerando a las personas en la mesa, comenzando en ese lugar y moviéndose hacia la derecha). Hay al menos dos formas diferentes de hacer este problema. Intenta encontrarlos a ambos. (Pista).

Ahora vamos a analizar el resultado del Problema 35 con más detalle para desentrañar otro principio de conteo que podamos utilizar en una amplia variedad de situaciones.

Cuadro 1.2.3: Las permutaciones\(3\) -elemento de\(\{a, b, c, d, e\}\) organizado por el cual\(3\) -conjunto de elementos permutan.
\ (3\) -elemento permutaciones de\(\{a, b, c, d, e\}\) organizado por qué\(3\) -elemento conjunto permutan.” >\(abc\)	\(acb\)	\(bac\)	\(bca\)	\(cab\)	\(cba\)
\ (3\) -elemento permutaciones de\(\{a, b, c, d, e\}\) organizado por qué\(3\) -elemento conjunto permutan.” >\(abd\)	\(adb\)	\(bad\)	\(bda\)	\(dab\)	\(dba\)
\ (3\) -elemento permutaciones de\(\{a, b, c, d, e\}\) organizado por qué\(3\) -elemento conjunto permutan.” >\(abe\)	\(aeb\)	\(bae\)	\(bea\)	\(eab\)	\(eba\)
\ (3\) -elemento permutaciones de\(\{a, b, c, d, e\}\) organizado por qué\(3\) -elemento conjunto permutan.” >\(acd\)	\(adc\)	\(cad\)	\(cda\)	\(dac\)	\(dca\)
\ (3\) -elemento permutaciones de\(\{a, b, c, d, e\}\) organizado por qué\(3\) -elemento conjunto permutan.” >\(ace\)	\(aec\)	\(cae\)	\(cea\)	\(eac\)	\(eca\)
\ (3\) -elemento permutaciones de\(\{a, b, c, d, e\}\) organizado por qué\(3\) -elemento conjunto permutan.” >\(ade\)	\(aed\)	\(dae\)	\(dea\)	\(ead\)	\(eda\)
\ (3\) -elemento permutaciones de\(\{a, b, c, d, e\}\) organizado por qué\(3\) -elemento conjunto permutan.” >\(bcd\)	\(bdc\)	\(cbd\)	\(cdb\)	\(dbc\)	\(dcb\)
\ (3\) -elemento permutaciones de\(\{a, b, c, d, e\}\) organizado por qué\(3\) -elemento conjunto permutan.” >\(bce\)	\(bec\)	\(cbe\)	\(ceb\)	\(ebc\)	\(ecb\)
\ (3\) -elemento permutaciones de\(\{a, b, c, d, e\}\) organizado por qué\(3\) -elemento conjunto permutan.” >\(bde\)	\(bed\)	\(dbe\)	\(deb\)	\(ebd\)	\(edb\)
\ (3\) -elemento permutaciones de\(\{a, b, c, d, e\}\) organizado por qué\(3\) -elemento conjunto permutan.” >\(cde\)	\(ced\)	\(dce\)	\(dec\)	\(ecd\)	\(edc\)

En la Tabla 1.2.3, enumeramos todas las permutaciones de tres elementos del conjunto\(5\) de elementos\(\{a, b, c, d, e\}\). Cada fila consiste en todas las permutaciones\(3\) -elementos de algún subconjunto de\(\{a, b, c, d, e\}\). Debido a que un subconjunto\(k\) -elemento dado se puede enumerar como una permutación\(k\) -elemento de\(k!\) maneras, hay\(3! = 6\) permutaciones en cada fila. Debido a que cada permutación\(3\) -elemento aparece exactamente una vez en la tabla, cada fila es un bloque de una partición del conjunto de permutaciones\(3\) -elemento de\(\{a, b, c, d, e\}\). Cada bloque tiene tamaño seis. Cada bloque consiste en todas las permutaciones\(3\) -elemento de algunos tres elementos subconjunto de\(\{a, b, c, d, e\}\). Como hay diez filas, vemos que hay diez subconjuntos\(3\) -elementos de\({a, b, c, d, e}\). Una forma alternativa de ver esto es observar que particionamos el conjunto de todas las permutaciones de\(60\) tres elementos de\(\{a, b, c, d, e\}\) en algún número\(q\) de bloques, cada uno de tamaño seis. Así por el principio del producto,\(q \cdot 6 = 60\), así\(q = 10\).

\(\bullet\) Exercise \(39\)

En lugar de restringirnos a\(n = 5\) y\(k = 3\), podemos dividir el conjunto de todas las permutaciones\(k\) -elemento de un\(n\) -elemento\(S\) configurado en bloques. Lo hacemos dejando\(B_{K}\) ser el conjunto (bloque) de todas las permutaciones\(k\) -elemento de\(K\) para cada subconjunto\(k\) -elemento\(K\) de\(S\). Así como en nuestro ejemplo anterior, cada bloque consiste en todas las permutaciones de algún subconjunto\(K\) de nuestro conjunto\(n\) -element. Por ejemplo, las permutaciones de {a, b, c} se listan en la primera fila de la Tabla 1.2.3 De hecho, cada fila de esa tabla es un bloque. Las preguntas que siguen son sobre la partición correspondiente del conjunto de permutaciones\(k\) -elemento de\(S\), dónde\(S\) y\(k\) son arbitrarias.

1. ¿Cuántas permutaciones hay en un bloque? (Pista).
2. Ya que\(S\) tiene\(n\) elementos, ¿qué te dice el Problema 20 sobre el número total de permutaciones\(k\) -elementos de\(S\)?
3. Describir una biyección entre el conjunto de bloques de la partición y el conjunto de subconjuntos\(k\) -elemento de\(S\). (Pista).
4. ¿Qué fórmula le da esto para el número\(n \choose k\) de subconjuntos\(k\) -element de un conjunto\(n\) -element? (Pista).

\(\rightarrow\) Exercise \(40\)

Un equipo de basquetbol tiene\(12\) jugadores. Sin embargo, sólo cinco jugadores juegan en un momento dado durante un juego.

1. ¿De cuántas maneras puede elegir el entrenador a los cinco jugadores?
2. Para ser más realistas, los cinco jugadores que juegan un juego normalmente constan de dos guardias, dos delanteros y un centro. Si hay cinco guardias, cuatro delanteros y tres centros en el equipo, ¿de cuántas maneras el entrenador puede elegir dos guardias, dos delanteros y un centro? (Pista).
3. ¿Y si uno de los centros es igualmente hábil para jugar al frente? (Pista).

\(\bullet\) Exercise \(41\)

En el Problema 38, describa una manera de dividir las permutaciones\(n\) -elemento de las\(n\) personas en bloques para que haya una biyección entre el conjunto de bloques de la partición y el conjunto de arreglos de las\(n\) personas alrededor de una mesa redonda. ¿A qué método de solución para el Problema 38 corresponde esto?

\(\bullet\) Exercise \(42\)

En Problemas 39d y 41, has estado usando el principio del producto de una manera nueva. Una de las formas en que anteriormente afirmamos el principio del producto fue “Si particionamos un conjunto en\(m\) bloques cada uno de tamaño\(n\), entonces el conjunto tiene tamaño”\(m \cdot n\). En los problemas 39d y 41 sabíamos el tamaño\(p\) de un conjunto\(P\) de permutaciones de un conjunto, y sabíamos que habíamos\(P\) dividido en algún número desconocido de bloques, cada uno de cierto tamaño conocido\(r\). Si dejamos\(q\) reposar el número de bloques, ¿qué nos dice el principio del producto\(p\),\(q\), y\(r\)? ¿Qué obtenemos cuando resolvemos\(q\)?

La fórmula que encontraste en el Problema 42 es tan útil que la vamos a destacar como otro principio. El principio del cociente dice:

Si particionamos un conjunto\(P\) de tamaño\(p\) en\(q\) bloques, cada uno de tamaño\(r\), entonces\(q = p/r\).

El principio del cociente es realmente solo una reformulación del principio del producto, pero pensarlo como un principio por derecho propio a menudo nos lleva a encontrar soluciones a los problemas. Observe que no siempre nos da una fórmula para el número de bloques de una partición; sólo funciona cuando todos los bloques tienen el mismo tamaño. En el Capítulo 6, desarrollamos una manera de resolver problemas con diferentes tamaños de bloque en los casos en que hay mucha simetría en el problema. (La redondez de la mesa era una simetría en el problema de
las personas en una mesa; el hecho de que podamos ordenar los conjuntos en cualquier orden es la simetría en el problema de contar\(k\) -elementos subconjuntos.)

En la Sección A.2 del Apéndice A introducimos la idea de una relación de equivalencia, vemos qué tienen que ver las relaciones de equivalencia con las particiones, y discutimos el principio del cociente desde ese punto de vista. Si bien ese apéndice no se requiere para lo que estamos haciendo aquí, si quiere una discusión más profunda del principio del cociente, este sería un buen momento para trabajar a través de ese apéndice.

Ejercicio\(43\)

¿De cuántas maneras podemos ensartar n cuentas distintas en un collar sin broche? (Quizás hagamos el collar ensartando las cuentas
en una cuerda, y luego pegando cuidadosamente los dos extremos de la cuerda para que no se pueda ver la articulación. Supongamos que alguien puede recoger el collar, moverlo en el espacio y ponerlo de nuevo hacia abajo, dando una forma aparentemente diferente de ensartar las cuentas que es equivalente a la primera.) (Pista).

\(\rightarrow\) Exercise \(44\)

Primero dimos este problema como Problema 12a. Ahora tenemos varias formas de abordar el problema. Un club de tenis tiene\(2n\) miembros. Queremos emparejar a los miembros por dos para partidos de singles.

1. ¿De cuántas maneras podemos emparejar a todos los miembros del club? Da al menos dos soluciones distintas a la que diste en Problema 12a. (Puede que no hayas hecho Problema 12a. En ese caso, vea si puede encontrar tres soluciones.) (Pista).
2. Supongamos que además de especificar quién juega a quién, por cada pareja decimos quién sirve primero. Ahora bien, ¿de cuántas formas podemos especificar nuestros pares? Intenta encontrar tantas soluciones como puedas. (Pista).

\(\bullet\) Exercise \(45\)

(Esto se vuelve especialmente relevante en el Capítulo 6, aunque aquí hace un punto importante). ¿De cuántas maneras podemos unir dos cuentas rojas idénticas y dos cuentas azules idénticas a las esquinas de un cuadrado (con una cuenta por esquina) libres para moverse en el espacio (tridimensional)? (Pista).

\(\rightarrow\) Exercise \(46\)

Si bien la fórmula que probaste en Problema 35 y Problema 39d es muy útil, no nos da una idea de cuán grandes son los coeficientes binomiales. Podemos hacernos una idea muy aproximada,\(2n \choose n\) por ejemplo, del tamaño de al reconocer que podemos escribir\((2n)^{\underline{n}}/n!\) como\(\dfrac{2n}{n} \cdot \dfrac{2n-1}{n-1} \dotsb \dfrac{n+1}{1}\), y cada cociente es al menos\(2\), así que el producto es al menos\(2^{n}\). Si esto fuera una estimación precisa, significaría que la fracción de los subconjuntos de n-elementos de un conjunto de\(2n\) elementos sería aproximadamente\(2^{n}/2^{2n} = 1/2n\), lo que se vuelve muy pequeño a medida que\(n\) se vuelve grande. No obstante, es bastante claro que la aproximación no va a ser muy buena, porque algunos de los términos en ese producto son mucho mayores que\(2\). De hecho, si\(n \choose k\) fueran los mismos para cada\(k\), entonces cada uno sería la fracción\(\frac{1}{2n+1}\) de\(2^{2n}\). Esto es mucho mayor que la fracción\(\dfrac{1}{2n}\). Pero nuestra intuición sugiere que\(2n \choose n\) es mucho más grande que\(2n \choose 1\) y probablemente sea más grande que\(2n \choose n-1\) así podemos estar seguros de que nuestra aproximación es mala. Para estimaciones como esta, James Stirling desarrolló una fórmula para aproximarse\(n!\) cuando\(n\) es grande,\(n!\) es decir, se trata\(\left(\sqrt{2 \pi n}\right) n^{n}/e^{n}\). De hecho la relación de\(n!\) a esta expresión se aproxima\(1\) como\(n\) se vuelve infinita ^b. Escribimos esto como

\(n! \sim \sqrt{2 \pi n} \frac{n^{n}}{e^{n}}\).

Leemos esta notación como\(n!\) es asintótica a\(\sqrt{2 \pi n} \frac{n^{n}}{e^{n}}\). Utilice la fórmula de Stirling para mostrar que la fracción de subconjuntos de tamaño\(n\) en un conjunto\(2n\) de elementos es aproximadamente\(\frac{1}{\sqrt{\pi n}}\). ¡Esta es una fracción mucho mayor que\(\frac{1}{2n}\)!

Notas

a. el símbolo\(χ\) es la letra griega chi que se pronuncia Ki, con el i sonando como “ojo”.

b. probar esto requiere más de un desvío de lo que es recomendable aquí; sin embargo hay una prueba elemental que se puede trabajar en los problemas del final de la Sección 1 del Capítulo 1 de Combinatoria Introductoria de Kenneth P. Bogart, Harcourt Academic Press, (2000).