Realmente hay dos interpretaciones razonables de la pregunta:
- Desea contar el número de 6 selecciones ordenadas sin reemplazo del conjunto [math] \ {1,2,3, \ ldots, 45 \} [/ math] de modo que la suma de cada una sea 129.
- Desea contar el número de 6 selecciones ordenadas con reemplazo del conjunto [math] \ {1,2,3, \ ldots, 45 \} [/ math] de modo que la suma de cada una sea 129.
Explicación
Lo que sigue es un enfoque de función generadora [1].
Primero introduciré una notación llamada [matemática] q [/ matemática] -notación análoga, es una forma abreviada de generar funciones del tipo [matemática] 1 + q + q ^ 2 + q ^ 3 + \ cdots + q ^ {n -1} [/ math] para que:
- ¿Qué viene primero, un huevo o un pollito?
- ¿Cuáles son los siguientes 4 términos para 1, 1, 2, 3, 5, 8?
- ¿Qué es un desafío para la mente que es tan difícil como el problema de 1000 prisioneros?
- Cómo hacer 7 con solo usar 1, 3 y 11
- ¿Cuál golpeará primero el suelo, un elefante o un mono?
[matemáticas] [n] _q = 1 + q + q ^ 2 + q ^ 3 + \ cdots + q ^ {n-1} = \ dfrac {1-q ^ n} {1-q} \ tag {1} [/matemáticas]
Este es el [matemático] q [/ matemático] -análisis de [matemático] n [/ matemático]. Notamos que si evaluamos en [matemáticas] q = 1 [/ matemáticas], esto simplemente se convierte en [matemáticas] n [/ matemáticas]:
[matemáticas] [n] _1 = n \ etiqueta * {} [/ matemáticas]
También tenga en cuenta que, según esta definición, [matemáticas] [1] _q = 1 [/ matemáticas].
Esta definición conduce al análisis natural [matemático] q [/ matemático] del factorial
[matemáticas] [n] _q! = [n] _q [n-1] _q! = [n] _q [n-1] _q \ cdots [2] _q [1] _q \ tag {2} [/ matemáticas]
y podemos definir [math] [0] _q! = 1 [/ math] por consistencia, esto es en analogía con [math] 0! = 1 [/ math].
Los análogos se pueden extender aún más para definir los coeficientes binomiales [matemáticos] q [/ matemáticos]
[matemáticas] \ displaystyle {n \ brack r} _q = \ dfrac {[n] _q!} {[nr] _q! [r] _q!} \ tag {3} [/ matemáticas]
Hasta ahora [math] (1) [/ math], [math] (2) [/ math] y [math] (3) [/ math] no son más que formas sucintas de escribir funciones generadoras. Generando funciones para las cuales, hasta el momento, no tenemos interpretación.
Hay varias interpretaciones de las funciones generadoras [matemáticas] (1) [/ matemáticas] y [matemáticas] (2) [/ matemáticas] pero estamos interesados en [matemáticas] (3) [/ matemáticas] para nuestros propósitos aquí, así que Nos centraremos en eso.
Es posible establecer que es un [matemático] q [/ matemático] -análisis de la identidad de Pascal:
[matemáticas] \ displaystyle {n \ brack r} _q = {n-1 \ brack r} _q + q ^ {nr} {n-1 \ brack r-1} _q \ tag {4} [/ matemáticas]
esto debería ser obvio si escribimos el lado derecho explícitamente
[matemáticas] \ begin {align} \ dfrac {[n-1] _q!} {[n-r + 1] _q! [r] _q!} + q ^ {nr} \ dfrac {[n-1] _q !} {[nr] _q! [r-1] _q!} & = [nr] _q \ cdot \ dfrac {[nr] _q!} {[nr] _q! [r] _q!} + [r] _q \ cdot q ^ {nr} \ dfrac {[n-1] _q!} {[nr] _q! [r] _q!} \\ & = \ dfrac {[n-1] _q!} {[nr] _q ! [r] _q!} \ left ([nr] _q + q ^ {nr} [r] _q \ right) \\ & = \ dfrac {[n-1] _q!} {[nr] _q! [r] _q!} \ cdot [n] _q \\ & = \ dfrac {[n] _q!} {[nr] _q! [r] _q!} = {n \ brack r} _q \ tag * {} \ end { alinear} [/ math]
Ahora, es natural comparar el [matemático] q [/ matemático] -análisis del coeficiente binomial (el coeficiente binomial [matemático] q [/ matemático] o el coeficiente binomial gaussiano [2]) con el coeficiente binomial familiar [ matemáticas] \ smash {\ binom {n} {r}} [/ matemáticas] en un intento por encontrar una interpretación.
Hay una interpretación de los coeficientes binomiales que puede ayudar y es la interpretación del recuento de rutas reticulares NE [3]. El coeficiente binomial [math] \ smash {\ binom {n} {r}} [/ math] cuenta el número de dichos caminos reticulados entre el origen [math] (0,0) [/ math] y la coordenada [math] (r, nr) [/ matemáticas].
Por ejemplo:
Podríamos sospechar, por lo tanto, que los coeficientes de [math] q ^ k [/ math] la función generadora [math] \ smash {{n \ brack r} _q} [/ math] enumeran las rutas de la red con una determinada propiedad, después de todo si ponemos [matemáticas] q = 1 [/ matemáticas] entonces
[matemáticas] \ displaystyle {n \ brack r} _1 = \ binom {n} {r} \ tag * {} [/ matemáticas]
para que la suma de todos los coeficientes cuente todas las rutas de la red.
De hecho, resulta que la función generadora [math] \ smash {{n \ brack r} _q} [/ math] enumera las rutas de la red desde [math] (0,0) [/ math] a [math] (r, nr) [/ math] por área. Es decir, el coeficiente de [matemática] q ^ k [/ matemática] en [matemática] \ smash {{n \ brack r} _q} [/ matemática] es el número de rutas de la red desde [matemática] (0,0) [/ matemática] a [matemática] (r, nr) [/ matemática] con un área de [matemática] k [/ matemática] entre la ruta y el eje horizontal.
Es fácil ver que la función generadora de rutas reticulares por área tiene la misma recursividad que los coeficientes binomiales [math] q [/ math] del siguiente diagrama. Las rutas de celosía desde [matemáticas] (0,0) [/ matemáticas] a [matemáticas] (r, nr) [/ matemáticas] deben pasar por [matemáticas] (r-1, nr) [/ matemáticas] o [matemáticas] (r, nr-1) [/ math], nuevamente las rutas de ejemplo son rojas:
Y como [math] \ smash {{1 \ brack 0} _q = {1 \ brack 1} _q = 1 = 1q ^ 0} [/ math] esto concuerda en que el área del camino de la red desde [math] (0, 0) [/ matemática] a [matemática] (0,1) [/ matemática] o [matemática] (1,0) [/ matemática] es [matemática] 0 [/ matemática]. Por lo tanto, una interpretación de los coeficientes binomiales [matemáticos] q [/ matemáticos] son las funciones generadoras de rutas reticulares por área:
[matemáticas] \ displaystyle {n \ brack r} _q = \ sum_ {k = 0} ^ {r (nr)} lp_kq ^ k \ tag {4} [/ matemáticas]
[matemática] lp_k [/ matemática] es el número de rutas de red entre [matemática] (0,0) [/ matemática] y [matemática] (r, nr) [/ matemática] con área [matemática] k [/ matemática] .
¿Cómo ayuda esto con nuestro problema? Bueno, hay una biyección entre las rutas reticulares de [matemáticas] (0,0) [/ matemáticas] a [matemáticas] (r, nr) [/ matemáticas] con un área fija [matemáticas] k [/ matemáticas] y el número de particiones de [math] k [/ math] en como máximo [math] r [/ math] partes sin una parte mayor que [math] nr [/ math]. Esto se puede ver en el siguiente diagrama que usa nuestro ejemplo de rutas de [matemática] (0,0) [/ matemática] a [matemática] (10,10) [/ matemática] con área [matemática] k = 44 [/ matemáticas]
En este ejemplo, la partición de [math] 44 [/ math] en como máximo [math] 6 [/ math] partes sin una parte mayor que [math] 10 [/ math] es [math] \ lambda = (0,1 , 2,2,3,6,6,6,9,9) [/ matemáticas]. Por lo tanto, otra interpretación del coeficiente [math] q ^ k [/ math] en la función generadora [math] \ smash {{n \ brack r} _q} [/ math] es el número de particiones de [math] k [/ math] en como máximo [math] r [/ math] partes sin una parte mayor que [math] nr [/ math].
Ahora, a la pregunta!
Respuestas
Interpretación 1
De la discusión anterior podemos ver que las particiones de [math] 129 [/ math] en como máximo [math] 6 [/ math] partes sin una parte mayor que [math] 45 [/ math] viene dada por [math ] q ^ {129} [/ math] coeficiente de [math] \ smash {{6 + 45 \ brack 6} _q} [/ math], esto enumera las rutas de celosía entre [math] (0,0) [/ math] y [matemáticas] (6,45) [/ matemáticas] por área. Sin embargo, queremos las particiones de [math] 129 [/ math] en exactamente [math] 6 [/ math] partes sin una parte mayor que [math] 45 [/ math], por lo tanto, necesitamos que cada parte sea [math] \ ge 1 [/ matemáticas]. Por lo tanto, el primer paso en cada ruta reticular con área [matemática] 129 [/ matemática] debe ser [matemática] (0,0) \ rightarrow (0,1) [/ matemática] y contamos las rutas reticulares con área [matemática] ] 129–6 = 123 [/ matemática] de [matemática] (0,1) [/ matemática] a [matemática] (6,45) [/ matemática]. Esto es lo mismo que contar las rutas de celosía con área [matemática] 123 [/ matemática] entre [matemática] (0,0) [/ matemática] a [matemática] (6,44) [/ matemática], necesitamos tomar el [matemáticas] q ^ {123} [/ matemáticas] en [matemáticas] \ smash {{6 + 44 \ brack 6} _q} [/ matemáticas], la notación para esto es:
[matemáticas] \ displaystyle [q ^ {123}] {50 \ brack 6} _q = 178 \, 454 \ tag {Respuesta 1} [/ matemáticas]
Uno podría calcular esto manualmente, pero es mucho más eficiente usar un sistema de álgebra de computadora como sage [4], con la siguiente entrada
taylor ((1-x ^ 50) * (1-x ^ 49) * (1-x ^ 48) * (1-x ^ 47) * (1-x ^ 46) * (1-x ^ 45) / ((1-x) * (1-x ^ 2) * (1-x ^ 3) * (1-x ^ 4) * (1-x ^ 5) * (1-x ^ 6)), x, 0,124) .coeficiente (x ^ 123)
que salidas:
178454
Interpretación 2
Para particiones de [matemática] 129 [/ matemática] en exactamente [matemática] 6 [/ matemática] partes distintas sin una parte mayor que [matemática] 45 [/ matemática] notamos que estas particiones están en biyección con particiones de [matemática] 108 [/ math] en como máximo [math] 6 [/ math] partes distintas sin una parte mayor que [math] 45-6 = 39 [/ math] tomando las particiones de [math] 108 [/ math] y sumando [matemática] 1 [/ matemática] a la primera parte, [matemática] 2 [/ matemática] a la segunda parte, [matemática] 3 [/ matemática] a la tercera parte y así sucesivamente. Por lo tanto, para esta interpretación, queremos el coeficiente de [matemática] q ^ {129- (1 + 2 + 3 + 4 + 5 + 6)} = q ^ {108} [/ matemática] en la función generadora [matemática] \ smash {{39 + 6 \ brack 6} _q} [/ math], es decir
[matemáticas] \ displaystyle [q ^ {108}] {45 \ brack 6} _q = 101 \, 478 \ tag {Respuesta 2} [/ matemáticas]
Nuevamente usando salvia ingresamos:
taylor ((1-x ^ 45) * (1-x ^ 44) * (1-x ^ 43) * (1-x ^ 42) * (1-x ^ 41) * (1-x ^ 40) / ((1-x) * (1-x ^ 2) * (1-x ^ 3) * (1-x ^ 4) * (1-x ^ 5) * (1-x ^ 6)), x, 0,124) .coeficiente (x ^ 108)
que da salida:
101478
Notas al pie
[1] Función generadora – Wikipedia
[2] Coeficiente binomial gaussiano – Wikipedia
[3] Ruta del enrejado – Wikipedia
[4] Sage Cell Server
