Número de composiciones de nnn tales que cada término es menor que igual a kkk

Creo que puede ser más fácil tratar con el caso más simple de$k=2$primero. Primero encontremos algunos valores pequeños y fáciles:

$$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 has 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$$

Con suerte notarás el patrón: esta es la secuencia de Fibonacci. La razón por la que esta es la secuencia de Fibonacci es porque para cualquier$n$, una partición con$k=2$terminará en cualquiera$1$o$2$. si termina en$1$, entonces simplemente sumamos$1$en una partición de$n-1$. si termina en$2$, entonces simplemente sumamos$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, esta es la recurrencia de Fibonacci.

Ahora, extendamos este razonamiento a general$k$. Primero, definamos$f(n, k)$ser el número de particiones de$N$donde los enteros positivos involucrados son como máximo$k$. Entonces, definamos$f(n,k)=0$para cualquier$n < 0$porque solo queremos permitir números enteros positivos y$f(0,k)=1$para cualquier$k$ya que la única manera de particionar$0$es con el conjunto vacío.

Como los números enteros deben ser como máximo$k$, esto significa que en cada partición estamos agregando algún entero nuevo$l \leq k$cada vez. Así, si tomamos$l$de distancia, obtenemos 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 el de$n-2$más el de$n-3$... y así sucesivamente, hasta$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$, obtiene los números de tribonacci , por$k=4$, si obtiene los números tetranacci , entonces$k=5$es pentanacci,$k=6$es heptanacci, etc.

Por lo tanto, el patrón que estás estudiando es simplemente una forma de orden superior de los números de Fibonacci.

La generación de funciones parece el camino a seguir. Hallazgo$m$piezas, cada una de tamaño como máximo$k$, esa suma a$n$, tiene función generadora$(x+x^2+\cdots+x^k)^m$; el coeficiente de$x^n$es el número de formas. Entonces, queremos el número total de formas, sobre todos los números posibles de piezas, por lo que obtenemos

$$\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 está buscando coeficientes específicos, es más fácil usar la recursividad similar a Fibonacci que se indica en la respuesta de Noble Mushtak, o la versión telescópica$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 los asintóticos? Eso vendrá del polo de$F$más cercano a cero, es decir, la única raíz positiva$r$de$x^k+\cdots+x^2+x-1=0$. Para$k>1$,$r\in [0,1]$. El$n$el término será aproximadamente proporcional a$r^{-n}$. ¿Una fórmula exacta? Tendrías que encontrar todas las raíces de ese polinomio y ejecutar fracciones parciales. La función generadora luego se divide en 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 ese primer paso de resolver el polinomio es un poco tonto.

Primero una nota sobre la terminología:
- una partición de un entero positivo$n$es una secuencia no decreciente de enteros positivos que se suman a$n$;
- una Composición de un entero positivo$n$es una secuencia desordenada de enteros positivos que se suman a$n$.

Con esa premisa, usted está hablando del número de Composiciones de$n$, cuyos términos (partes) no son mayores que$k$.

Considere el caso en el que busca el número de composiciones del número positivo$s+m$en$m$partes que no excedan$r+1$

$${\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ {\rm 1} \le {\rm integer}\;y_{\,j} \le r + 1 \hfill \cr y_{\,1} + y_{\,2} + \; \cdots \; + y_{\,m} = s + m \hfill \cr} \right.$$ eso es lo mismo que $$N_{\,b} (s,r,m) = \text{No}\text{. of solutions to}\;\left\{ \begin{gathered} 0 \leqslant \text{integer }x_{\,j} \leqslant r \hfill \\ x_{\,1} + x_{\,2} + \cdots + x_{\,m} = s \hfill \\ \end{gathered} \right.$$

$N_b$viene dada por la siguiente suma

$$N_b (s,r,m)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,j\,\,\left( { \leqslant \,\frac{s}{r+1}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \binom{m}{j} \binom { s + m - 1 - j\left( {r + 1} \right) } { s - j\left( {r + 1} \right)}\ }$$ como se explica ampliamente en este post relacionado .

Volviendo a tu caso, el número de composiciones de$n$en$m$partes no mayores que$k$
será entonces

$$\eqalign{ & 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 - j\,k}} \cr}$$ mientras que el
número total de composiciones de$n$en partes no mayores que$k$
será la suma de los anteriores para$0 \le m$: si la suma se extiende sobre$n$mantendrá el valor$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 - j\,k} } } \cr} }$$

En el ejemplo con$n=4$, lo anterior da por$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)$verifica correctamente con OEIS seq. A126198 , que proporciona más propiedades de estos números;
- el ogf de$N_{c\,t}$en$n$es de hecho el$F(x)$dada por la respuesta de @jmerry (re. to the ogf for$N_b$dado en una publicación relacionada );

$$\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 recursión dada por @NobleMushtak $$N_{c\,t} (n,k) = \sum\limits_{j = 1}^k {N_{c\,t} (n - j,k)} + \left[ {n = 0} \right]$$ dónde$[P]$denota el corchete de Iverson .