Número de composiciones de$n$, de modo que cada término sea menor que$k.$

Question

Deje $n$ ser un entero $\geq 1.$ , a Continuación, una partición de $n$ es una secuencia de enteros positivos (mayor que, igual a $1$) tales que su suma es igual a $n.$ Así por ejemplo, si $n=4$ luego $$[[4], [1, 3], [1, 1, 2], [1, 1, 1, 1], [1, 2, 1], [2, 2], [2, 1, 1], [3, 1]]$$ es una colección de todas las particiones de $n$ con el pedido. Claramente para cualquier $n$ el número de tales ordenado de las particiones es $2^{n-1}.$ sin Embargo quiero contar el número de particiones de $n$ donde cada entero en la partición es menor que igual a un número entero $k.$ Así por ejemplo, si $n=4$ e $k=2$ luego $$[[1, 1, 2], [1, 1, 1, 1], [1, 2, 1], [2, 2], [2, 1, 1]]$$ es una recopilación de todas las $2$-particiones de $4.$ hay una fórmula general para encontrar este o tal vez un asintótica de expresión?

Answer 1

Creo que puede ser más fácil tratar con el caso más sencillo de $k=2$ primera. Vamos a ver algunos sencillos, los pequeños valores de la primera:

$$n=1\rightarrow [[1]]\rightarrow f(1)=1$$ $$n=2\rightarrow [[1,1],[2]]\rightarrow f(2)=2$$ $$n=3\rightarrow [[1,1,1],[2,1],[1,2]]\rightarrow f(3)=3$$

Como se ha demostrado, $f(4)=5$.

$$n=5\rightarrow [[1,1,2,1],[1,1,1,1,1],[1,2,1,1],[2,2,1],[1,1,2,1],[1,1,1,2],[2,1,2],[1,2,2]]\rightarrow f(5)=8$$

Esperemos que se note el patrón: Esta es la secuencia de Fibonacci. La razón de esto es la secuencia de Fibonacci es porque para cualquier $n$, una partición con $k=2$ terminará en cualquiera de las $1$ o $2$. Si termina en $1$, entonces sólo tenemos que añadir $1$ en una partición de $n-1$. Si termina en $2$, entonces sólo tenemos que añadir $2$ en una partición de $n-2$. Esto nos da la siguiente recurrencia:

$$f(n)=f(n-1)+f(n-2)$$

Y, por supuesto, este es el Fibonacci de recurrencia.

Ahora, vamos a extender este razonamiento a general $k$. En primer lugar, vamos a definir $f(n, k)$ a ser el número de particiones de $N$ donde los enteros positivos son, a la mayoría de las $k$. A continuación, vamos a definir $f(n,k)=0$ cualquier $n < 0$ debido a que sólo se desea permitir para enteros positivos y $f(0,k)=1$ cualquier $k$ ya que la única manera de partición de la $0$ es con el conjunto vacío.

Puesto que los enteros se debe en la mayoría de las $k$, esto significa que en cada partición, vamos a añadir algunas nuevas entero $l \leq k$ cada vez. Por lo tanto, si tomamos $l$ lejos, tenemos una partición de $n-l$. Por lo tanto, el número de particiones de $n$ deben ser las particiones de $n-1$ más que de $n-2$ más que de $n-3$ ... y así sucesivamente, hasta que $n-k$. En otras palabras:

$$f(n,k)=\sum_{l=1}^k f(n-l,k)$$

Esta es una generalización de los números de Fibonacci. Para $k=3$, se obtiene de la tribonacci números, para $k=4$, si consigue la tetranacci números, a continuación, $k=5$ es pentanacci, $k=6$ es heptanacci, etc.

Por lo tanto, el modelo que estamos estudiando es simplemente un orden superior de la forma de los números de Fibonacci.

Answer 2

Funciones de generación se ven como el camino a seguir. Búsqueda de $m$ piezas, cada una de tamaño en la mayoría de las $k$, que se suma a $n$, ha de generación de función $(x+x^2+\cdots+x^k)^m$; el coeficiente de $x^n$ es el número de maneras. Entonces, queremos que el número total de formas, sobre todos los posibles números de piezas, por lo que tenemos \begin{align*}F(x) &= \sum_{m=0}^{\infty} (x+x^2+\cdots+x^k)^m\\ &= \frac{1}{1-(x+x^2+\cdots+x^k)}\\ F(x) &= \frac{1}{1-\frac{x-x^{k+1}}{1-x}} = \frac{1-x}{1-2x+x^{k+1}}\end{align*} Si usted está buscando para los coeficientes específicos, es más fácil usar la de Fibonacci-como la recursividad se señaló en el Noble Mushtak la respuesta, o la telescopado versión $a_{n+1}=2a_n-a_{n-k}$. Las condiciones iniciales son $a_0=a_1=1,a_{-1}=\cdots=a_{-k+1}=0$. Para el asymptotics? Que va a venir desde el polo de la $F$ más cercano a cero, es decir, el único positivo de la raíz de $r$ de $x^k+\cdots+x^2+x-1=0$. Para $k>1$, $r\in [0,1]$. El $n$el plazo será de aproximadamente proporcional a $r^{-n}$. Una fórmula exacta? Usted tendría que encontrar todas las raíces de dicho polinomio y ejecución parcial de las fracciones. La generación de la función, a continuación, se divide como varios términos de la forma $\frac{b_j}{x-c_j}$, cada uno de los cuales nos da una serie geométrica. Todo está bien en teoría, pero que el primer paso para resolver el polinomio es un doozy.

Answer 3

Primero una nota sobre la terminología:
- una Partición de un número entero positivo $n$ es no decreciente secuencia de enteros positivos sumar a $n$;
- una Composición de un entero positivo $n$ es una desordenada secuencia de enteros positivos sumar a $n$.

Esa premisa, de la que están hablando de la cantidad de Composiciones de $n$, cuyos términos de (partes de) son no-mayor que $k$.

Considere el caso en el que se solicite por el número de las composiciones de la número positivo $s+m$ en $m$ partes no exceda $r+1$ $$ {\rm No}{\rm .}\,{\rm de}\,{\rm soluciones}\,{\rm}\;\left\{ \matriz{ {\rm 1} \le {\rm integer}\;y_{\,j} \le r + 1 \hfill \cr y_{\,1} + y_{\,2} + \; \cdots \; + y_{\,m} = s + m \hfill \cr} \right. $$ que es la misma que $$N_{\,b} (s,r,m) = \text{No}\text{. de soluciones a}\;\left\{ \begin{gathered} 0 \leqslant \text{integer }x_{\,j} \leqslant r \hfill \\ x_{\,1} + x_{\,2} + \cdots + x_{\,m} = s \hfill \\ \end{reunieron} \right.$$

$N_b$ está dado por la siguiente suma $$ N_b (s,r,m)\quad \left| {\;0 \leqslant \text{números enteros }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,j\,\,\left( { \leqslant \,\frac{s}{i+1}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \binom{m}{j} \binom { s + m - 1 - j\left( {i + 1} \right) } { s - j\left( {i + 1} \right)}\ } $$ como ampliamente explicado en este post relacionados.

Volviendo a tu caso, la número de composiciones de $n$ a $m$ partes no mayor de $k$
será entonces $$ \eqalign{ Y N_c (n,k), m)\quad \left| {\;1 \le n,m,k} \right.\quad = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,j\,\,\left( {\, \le \,m} \right)} {\left( { - 1} \right)^{\,j} \binom{m}{j} \binom{n - 1 - j\,k}{ n - m a - j\,k}} \cr} $$ mientras que el
número total de composiciones de $n$ en partes no mayor de $k$
será la suma de de los de arriba para $0 \le m$ : si la suma se extiende sobre $n$ va a mantener el valor de $2^{n-1}$. $$ \bbox[lightyellow] { \eqalign{ & N_{c\,t} (n,k)\quad \left| {\;0 \le n,k \in \mathbb Z} \right.\quad = \cr & = \sum\limits_{0\, \le \,\,m} {\;\sum\limits_{\left( {0\, \le } \right)\,\,j\,\,\left( {\, \le \,m} \right)} {\left( { - 1} \right)^{\,j} \binom{m}{j} \binom{ n - 1 - j\,k}{n - m a - j\,k} } } \cr} }$$

En el ejemplo con $n=4$, el de arriba te da para $k=1,2,3,4$ $$ 1,5,7,8 $$ que en realidad corresponden a $$ \eqalign{ & \left[ {1,1,1,1} \right] \cr & \left[ {1,1,1,1} \right]\left[ {1,1,2} \right]\left[ {1,2,1} \right]\left[ {2,1,1} \right]\left[ {2,2} \right] \cr & \left[ {1,1,1,1} \right]\left[ {1,1,2} \right]\left[ {1,2,1} \right]\left[ {2,1,1} \right]\left[ {2,2} \right]\left[ {1,3} \right]\left[ {3,1} \right] \cr & \left[ {1,1,1,1} \right]\left[ {1,1,2} \right]\left[ {1,2,1} \right]\left[ {2,1,1} \right]\left[ {2,2} \right]\left[ {1,3} \right]\left[ {3,1} \right]\left[ 4 \right] \cr} $$

Finalmente tenga en cuenta que:
- $N_{c\,t}(n,k)$ correctamente comprueba con OEIS seq. A126198, que ofrece más propiedades de estos números;
- la junta.g.f. de $N_{c\,t}$ en $n$ es de hecho la $F(x)$ dada por @jmerry la respuesta de (re. a la junta.g.f. para $N_b$ dado en el post relacionados); $$ \sum\limits_{0\, \le \,\,n} {N_{c\,t} (n,k)\,x^{\n} } = {{1 - x} \over {1 - 2x + x^{\,k + 1} }} $$ - $N_{c\,t}(n,k)$ satisface la recursividad dada por @NobleMushtak $$ N_{c\,t} (n,k) = \sum\limits_{j = 1}^k {N_{c\,t} (n - j,k)} + \left[ {n = 0} \right] $$ donde $[P]$ denota la Iverson soporte.