Deje $n_1 < n_2 < n_3 < n_4 < n_5$ ser enteros positivos tales que a $n_1 + n_2 + n_3 + n_4 + n_5 = 20$. A continuación, el número de distintos arreglos $(n_1, n_2, n_3, n_4, n_5)$ es...... No tengo idea de cómo proceder. Manualmente, yo lo he hecho $$1+2+3+4+10$$ $$1+2+3+5+9$$ $$1+2+3+6+8$$ $$1+2+4+5+8$$ $$1+2+4+6+7$$ $$1+3+4+5+7$$ $$2+3+4+5+6$$ Pero, ¿hay alguna manera de que pueda hacerlo por Permutación y Combinación de método?
Respuestas
¿Demasiados anuncios?
Una variación basa en la generación de funciones. Presentamos enteros positivos $a,b,c,d$ y poner \begin{align*} n_2&=n_1+a\\ n_3&=n_2+b=n_1+a+b\\ n_4&=n_3+c=n_1+a+b+c\\ n_5&=n_4+d=n_1+a+b+c+d \end{align*}
La ecuación de $n_1+n_2+n_3+n_4+n_5=20$ se transforma en \begin{align*} 5n_1+4a+3b+2c+d=20\tag{1} \end{align*} con $n_1,a,b,c,d>0$.
Con el fin de encontrar el número de soluciones de (1) consideramos que la generación de la función $A(x)$ \begin{align*} A(x)&=\frac{x^5}{1-x^5}\cdot\frac{x^4}{1-x^4}\cdot\frac{x^3}{1-x^3}\cdot\frac{x^2}{1-x^2}\cdot\frac{x}{1-x}\\ &=x^{15}+x^{16}+2x^{17}+3x^{18}+5x^{19}+\color{blue}{7}x^{20}+10x^{21}+\cdots \end{align*} y obtener con la ayuda de Wolfram Alpha la solución \begin{align*} [x^{20}]A(x)\color{blue}{=7} \end{align*}
Add-on: Algunos detalles
Primero vamos a transformar la ecuación con restricciones mediante la introducción de números enteros positivos $a,b,c,d$ en una ecuación equivalente con más conveniente restricciones \begin{align*} &n_1 + n_2 + n_3 + n_4 + n_5 = 20\qquad&\qquad&5n_1+4a+3b+2c+d=20\\ &0<n_1<n_2<n_3<n_4<n_5\qquad&\qquad&0<n_1,0<a,0<b,0<c,0<d \end{align*}
Ahora consideramos admisible $5$-tuplas $(n_1,a,b,c,d)$. El aumento de $n_1$ $1$ agrega $5$ a de la ecuación. Del mismo modo, el aumento de $a$ $1$ agrega $4$ a de la ecuación. Valoramos estos incrementos a través de los exponentes de la generación de funciones:
- $n_1$: Incremento por $5$ da \begin{align*} x^5+x^{10}+x^{15}+\cdots=x^5(1+x^5+x^{10}+\cdots)=\frac{x^5}{1-x^5} \end{align*}
- $a$: Incremento por $4$ da \begin{align*} x^4+x^8+x^3+\cdots=x^4(1+x^4+x^8+\cdots)=\frac{x^4}{1-x^4} \end{align*}
y lo mismo para $b,c$$d$. Observar que cada uno de $n_1,a,b,c,d$ es positivo, es decir, tiene al menos el valor de $1$. Este es respetado por los más pequeños los valores de $x^5,x^4,x^3,x^2$$x^1$.
El número admisible de soluciones es, por tanto, \begin{align*} [x^{20}]&\frac{x^5}{1-x^5}\cdot\frac{x^4}{1-x^4}\cdot\frac{x^3}{1-x^3}\cdot\frac{x^2}{1-x^2}\cdot\frac{x}{1-x}\\ &=[x^{20}]\frac{x^{15}}{(1-x^5)(1-x^4)(1-x^3)(1-x^2)(1-x)}\\ &=[x^{5}]\frac{1}{(1-x^5)(1-x^4)(1-x^3)(1-x^2)(1-x)}\tag{2}\\ &=[x^{5}](1+x^5)(1+x^4)(1+x^3)(1+x^2+x^4)(1+x+x^2+x^3+x^4+x^5)\tag{3}\\ &=\cdots\tag{4}\\ &\color{blue}{=7} \end{align*}
Comentario:
En (2) utilizamos el coeficiente de operador de la regla: $[x^{p}]x^qA(x)=[x^{p-q}]A(x)$.
En (3) expandir la serie geométrica restringido a los poderes menor o igual a $x^5$ desde otros términos no contribuyen a $[x^5]$.
En (4) se expanda más allá y puede omitir términos con potencias mayores de $5$.
Sugerencia: ejemplo ilustrativo puede encontrarse en H. S. Wilf del libro generatingfunctionology.
CodingBytes
Puntos
102
Escribir $$n_1=1+y_1,\qquad n_k=n_{k-1}+1+y_k \quad(2\leq k\leq5)$$ con $y_k\geq0$ $(1\leq k\leq 5)$. Recopilación de términos que, a continuación, obtener $$20=\sum_{k=1}^5 n_k=15 + 5y_1+4y_2+3y_3+2y_4+y_5\ .$$ Por lo tanto, debemos contar las soluciones de $$\sum_{k=1}^5 z_k\,k=5$$ en números enteros $z_k=y_{6-k}\geq0$. Cada solución codifica una partición de $5$ a $z_k$ partes de tamaño $k$. Desde allí se $7$ particiones de $5$, la respuesta a la pregunta original es $7$.
freethinker
Puntos
656
Deje $m_1 = n_1, m_2 = n_2 -1, m_3 = n_3 -2, m_4 = n_4 -3, m_5 = n_5-4$; a continuación,$m_1 \leq m_2 \leq \cdots \leq m_5$$m_1+m_2+m_3+m_4+m_5 = 10$. Por lo tanto necesitamos el número de 5 particiones de 10, $P(10,5)$. Claramente, $P(10, 5) = 7$, mediante la recurrencia $P(n,p) = P(n-1, p-1) + P(n-p,p)$.
Pieter21
Puntos
1072
Usted podría comenzar con $1+2+3+4+5 = 15$ y ver que todavía hay que agregar $5$.
Añadiendo, por ejemplo, $n_3$ implica que tienes que añadir a $n_4$$n_5$, por lo que necesita $3$ hacer que la adición.
Así que, finalmente, acabará con $5n_1 + 4n_2 + 3n_3 + 2n_4 + n_5 = 5$.
Que se podría tratar de resolver con la recursividad, ya sea con un programa o con una fórmula. No estoy seguro de si la fórmula va a ser fácil y la forma cerrada.
Archis Welankar
Puntos
1730
El uso de la combinatoria nos encontramos con que la respuesta es el coeficiente de $x^{20} $ $(x+x^2+x^3+x^4+x^5)(x^2+x^3+..x^6)(x^3..+x^7)(x^4+..+x^8)(x^5+..+x^9)=x^{15}(1+x+x^2+x^3+x^4)^5$ $7$ es decir las formas se $(1,1,1,x,x^4), (1,1,x,x,x^3), (1,1,1,x^2,x^3), (x,x,x,x,x), (1,1,x,x^2,x^2),(1,x,x,x,x^2), (1,1,x,x,x^3) $
