¿De cuántas maneras para elegir $a<b<c<d<e$ el conjunto de $\{1,2,3,\cdots,100\}$ tal que $100<a+b+c+d+e<145$?

Question

Le agradeceria si alguien me pudiera ayudar con el siguiente problema

De cuántas maneras puedo elegir un número 5 $a,b,c,d,e(a<b<c<d<e)$ el conjunto de $\{1,2,3,\cdots,100\}$ tal que % $100<a+b+c+d+e<145$

Answer 1

(2. Actualización: Ahora la condición de $e\leq100$ es también tomado cuidado de.)

Escribir $$\eqalign{a&=1+x_1\cr b&=2+x_1+x_2\cr c&=3+x_1+x_2+x_3\cr d&=4+x_1+x_2+x_3+x_4\cr e&=5+x_1+x_2+x_3+x_4+x_5\cr}$$ con $x_i\geq0$ $\>(1\leq i\leq5)$. Entonces tenemos que encontrar el número de enteros soluciones de ${\bf x}=(x_1,\ldots,x_5)$ satisfactorio $x_i\geq0$ $(1\leq i\leq5)$ y $$x_1+x_2+x_3+x_4+x_5\leq95,\qquad 86\leq 5x_1+4x_2+3x_3+2x_4+x_5\leq 129\ .$$ Para este fin de ampliar las funciones de $$f_i(t,y):={1\over 1-t y^i}\qquad (1\leq i\leq 5)$$ hasta el $y^{129}$ y de forma recursiva calcular (a a $y^{129}$) de las funciones de $$g_0(t,y):=1,\qquad g_{k}(t,y):=g_{k-1}(t,y)\cdot f_k(t,y)\qquad(1\leq k\leq 5)\ .$$ La función de $g_5(t,y)$ es un polinomio en a$t$$y$. Cada solución de ${\bf x}$ de la original del problema contribuye a un plazo$t^my^n$$g_5$, el cual $x_1+\ldots+x_5=m$, $5x_1+\ldots+x_5=n$. Ahora podemos eliminar todos los términos en $g_5$ con $t$grado $m>95$, y posteriormente,$t:=1$. Deje $\hat g_5(y)$ será la resultante polinomio en $y$ solo. El número de $N$ que estamos buscando es el dado por $$N=\sum_{k=86}^{129}{\rm coeff}_k(\hat g_5)=2\,831\,886\ ,$$ como Mathematica calculada para nosotros.

Answer 2

El número de particiones de $n$ en cinco partes con la mayor parte de las $k$ es el coeficiente de $t^kq^n$ en $$\frac{t^5q^{15}}{(1-ca)(1-tq^2)(1-tq^3)(1-tq^4)(1-tq^5)}.$$ (Para una explicación de esto, ver a continuación). Con la suficiente fuerza bruta, uno podría extraer los coeficientes de todos los términos con $k\le100$ $100<n<145$—esto es lo que Christian Blatter termina haciendo (2. Actualización) para corregir la omisión en su respuesta original—pero sin duda hay más eficientes métodos de cálculo.

El método más directo que se me ocurre, que evita la necesidad de ampliar de dos variables de generación de función, es la siguiente: elimina la restricción de que la mayor parte de estar en la mayoría de $100$, y calcular el número de particiones de $n$ en cinco partes bien diferenciadas para $n\in\{101,102,\ldots,144\}$ mediante la extracción adecuada de los coeficientes de la función de la generación de $$\frac{q^{15}}{(1-q)(1-p^2)(1-q^3)(1-q^4)(1-q^5)}.$$ El resultado es $$26,455+27,604+28,796+\ldots+116,875+120,362=2,862,666.$$ Para $n$ en este rango, en la mayoría de los que una parte puede ser mayor que $100$. (Esto significa que no tiene que preocuparse acerca de $d$ superior a $e$.) Así, del total de número ilimitado de particiones restar $$\begin{aligned} &\sum_{e=101}^{134}\sum_{n=10}^{144-e}\text{(# partitions of %#%#% into four distinct parts)}\\ &\quad=\sum_{n=10}^{43}(44-n)\text{(# partitions of %#%#% into four distinct parts).} \end{aligned}$$ El número de particiones de $n$ en cuatro partes distintas, y es el coeficiente de $n$ en $$\frac{q^{10}}{(1-q)(1-p^2)(1-q^3)(1-q^4)}.$$ Poniendo todo esto junto, la cantidad que se resta es $$34\cdot1+33\cdot1+32\cdot2+31\cdot3+30\cdot5+29\cdot6+28\cdot9+\ldots+2\cdot351+1\cdot378=30,780.$$ El resultado neto es $$2,862,666-30,780=2,831,886.$$

Explicación de la generación de la función: A primera vista, la generación de la función en el párrafo de apertura parece ser el de generación de función cuyo $n$ coeficiente es el número de particiones de $q^n$ a $t^kq^n$ partes de tamaño en la mayoría de las $n$, después de haber al menos una parte de cada uno de los tamaños $k$, $5$, $1$, $2$, $3$—¡y lo es! Pero la conjugación de cualquier partición de este tipo da una partición de $4$ en cinco partes con la mayor parte de las $5$. He aquí un ejemplo. Una partición de $n$ en nueve partes de tamaño en la mayoría de las $k$, con el tamaño de cada representados al menos una vez es $27$. Se tiene el siguiente diagrama de Ferrers. $$\begin{array}{cccccccc}*&*&*&*&*\\ *&*&*&*\\ *&*&*&*\\ *&*&*&*\\ *&*&*\\ *&*&*\\ *&*\\ *\\ * \end{array}$$ Conjugación da la partición de $5$ en cinco partes con la mayor parte de las $5+4+4+4+3+3+2+1+1$ se muestra a continuación. $$\begin{array}{ccccccccc}*&*&*&*&*&*&*&*&*\\ *&*&*&*&*&*&*\\ *&*&*&*&*&*\\ *&*&*&*\\ * \end{array}$$ Esta es la partición $27$. Debido a la conjugación de una correspondencia uno a uno entre los dos tipos de particiones, la generación de la función de arriba también representa lo que se reivindica.