Como otros han señalado, [math] \ binom {n} {n / 4} [/ math] tiende al infinito con bastante rapidez a medida que [math] n [/ math] crece. Pero hay cosas muy interesantes que decir sobre cuán rápido crece.
Este coeficiente binomial cuenta subconjuntos de tamaño [matemática] n / 4 [/ matemática] dentro de un conjunto de tamaño [matemática] n [/ matemática]. ¿Qué pasa si contamos todos los subconjuntos, independientemente del tamaño? Claramente, existen [matemáticas] 2 ^ n [/ matemáticas] tales subconjuntos. Este número también tiende al infinito, pero está muy claro cómo lo hace: crece exponencialmente, siendo simplemente un poder de crecimiento lineal de [matemáticas] 2 [/ matemáticas].
¿Es posible que nuestro coeficiente binomial sea también un poder de crecimiento lineal de [math] 2 [/ math]? La respuesta es sí, de hecho lo es. En lugar de ser [matemáticas] 2 ^ n [/ matemáticas], es aproximadamente [matemáticas] 2 ^ {0.81n} [/ matemáticas]. Claro, es más pequeño, pero ahora entendemos cuán pequeño es: tiene el mismo comportamiento exponencial pero con un coeficiente constante diferente de [matemáticas] n [/ matemáticas].
- ¿Los dados generan números aleatorios?
- ¿Cuáles son algunos datos / patrones matemáticos menos conocidos?
- ¿El grupo módulo tiene una operación que es homomórfica a la suma?
- ¿Es posible hacer cálculo mental?
- ¿Por qué mil millones equivalen a mil millones?
¿Qué es esto [matemáticas] 0.81 [/ matemáticas], se preguntarán? Ah, esa es una buena pregunta. Es una de las manifestaciones más importantes de la maravillosa función de entropía , definida como
[matemática] H (p) = – p \ log_2 (p) – (1-p) \ log_2 (1-p) [/ math].
Esta función mide la cantidad de información asociada con bits aleatorios sesgados hacia [matemática] 0 [/ matemática] (o [matemática] 1 [/ matemática], no importa) con probabilidad [matemática] p [/ matemática]. Y de hecho,
[matemáticas] H (1/4) = 0.811278 \ ldots [/ matemáticas]
es exactamente el coeficiente de [matemática] n [/ matemática] en la fórmula asintótica de [matemática] \ binom {n} {n / 4} [/ matemática]. Además, esto es cierto en general: para cualquier [matemática] p [/ matemática] fija entre [matemática] 0 [/ matemática] y [matemática] 1 [/ matemática] (¡inclusive!),
[matemáticas] \ displaystyle \ lim_ {n \ to \ infty} \ frac {1} {n} \ log_2 \ binom {n} {pn} = H (p) [/ math].
La función de entropía le dice exactamente qué “fracción logarítmica” ocupan los subconjuntos de tamaño [math] pn [/ math] entre todos los subconjuntos.
Cuando un combinatorio experimentado escucha “la tasa de crecimiento asintótico de [matemáticas] \ binom {n} {pn} [/ matemáticas]”, esto es inmediatamente lo que piensan: no es el hecho de que tiende al infinito, ¡seguro que sí! – pero el hecho de que crece como [matemáticas] 2 ^ {H (p) n} [/ matemáticas].
Desde una perspectiva teórica de la información, este resultado es muy natural. De hecho es casi trivial. El número de bits que necesito darle para describir un subconjunto de tamaño [math] pn [/ math] entre los elementos [math] n [/ math] es solo el número de bits yes / no que determinan qué elementos están en el subconjunto y cuáles no, que es solo una secuencia aleatoria de [math] p [/ math]-bits imparciales. Entonces, por supuesto, requiere [math] nH (p) [/ math] bits para comunicarse.
Probar esta fórmula asintótica no es difícil con la aproximación de Stirling, y es un buen ejercicio para hacerlo.
La función de entropía [matemática] H (p) [/ matemática] se ve así:
Describe exactamente cómo crece la proporción de subconjuntos de tamaño [matemática] pn [/ matemática] y luego se reduce a medida que [matemática] p [/ matemática] pasa de [matemática] 0 [/ matemática] a [matemática] 1 [/ matemática] . La derivada en [matemáticas] p = 0 [/ matemáticas] y [matemáticas] p = 1 [/ matemáticas] es infinita, lo que en un momento de mi vida resultó ser algo muy útil.
En caso de que se pregunte: [matemáticas] H (1/2) = 1 [/ matemáticas], mientras que el coeficiente binomial medio [matemáticas] \ binom {n} {n / 2} [/ matemáticas] es claramente menor que [matemáticas] 2 ^ n [/ matemáticas]. De hecho, la fórmula que presentamos es indiferente a esta sutileza: [matemáticas] \ binom {n} {pn} [/ matemáticas] en realidad está más cerca de [matemáticas] 2 ^ {H (p) n} / \ sqrt {n} [ /matemáticas]. Tomar el registro y dividirlo entre [matemáticas] n [/ matemáticas] hace que el término de corrección [matemáticas] \ sqrt {n} [/ matemáticas] desaparezca, pero para estimaciones asintóticas más refinadas es importante tenerlo en cuenta.
Por lo tanto, esta es posiblemente una descripción más útil y precisa del comportamiento asintótico de [math] \ binom {n} {n / 4} [/ math].
