Cfrgtkky

Let $n$ be an integer $geq 1.$ Then a partition of $n$ is a sequence of positive integers (greater than equal to $1$) such that their sum equals $n.$ So for instance if $n=4$ then
$$[[4], [1, 3], [1, 1, 2], [1, 1, 1, 1], [1, 2, 1], [2, 2], [2, 1, 1], [3, 1]]$$
is a collection of all partitions of $n$ with order. Clearly for any $n$ the number of such ordered partitions is $2^{n-1}.$ However I want to count the number of paritions of $n$ where each integer in the parition is less than equal to some integer $k.$ So for instance if $n=4$ and $k=2$ then
$$[[1, 1, 2], [1, 1, 1, 1], [1, 2, 1], [2, 2], [2, 1, 1]]$$
is a collection of all the $2$-partitions of $4.$ Is there a general formula for finding this or maybe an asymptotic expression?

I think it may be easier to deal with the simpler case of $k=2$ first. Let's find some easy, small values first:

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

As you have shown, $f(4)=5$.

$$n=5rightarrow [[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$$

Hopefully you notice the pattern: This is the Fibonacci sequence. The reason this is the Fibonacci sequence is because for any $n$, a partition with $k=2$ will end in either $1$ or $2$. If it ends in $1$, then we simply add $1$ onto a partition from $n-1$. If it ends in $2$, then we simply add $2$ onto a partition from $n-2$. This gives us the following recurrence:

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

And, of course, this is the Fibonacci recurrence.

Now, let's extend this reasoning to general $k$. First, let's define $f(n, k)$ to be the number of partitions of $N$ where the positive integers involved are at most $k$. Then, let's define $f(n,k)=0$ for any $n < 0$ because we only want to allow for positive integers and $f(0,k)=1$ for any $k$ since the only way to partition $0$ is with the empty set.

Since the integers must be at most $k$, this means in every partition, we are adding some new integer $l leq k$ every time. Thus, if we take $l$ away, we get a partition of $n-l$. Therefore, the number of partitions of $n$ must be the partitions of $n-1$ plus that of $n-2$ plus that of $n-3$ ... and so on, until $n-k$. In other words:

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

This is a generalization of the Fibonacci numbers. For $k=3$, it gets you the tribonacci numbers, for $k=4$, if gets you the tetranacci numbers, then $k=5$ is pentanacci, $k=6$ is heptanacci, etc.

Thus, the pattern you are studying is simply a higher-order form of the Fibonacci numbers.

Generating functions look like the way to go. Finding $m$ pieces, each of size at most $k$, that sum to $n$, has generating function $(x+x^2+cdots+x^k)^m$; the coefficient of $x^n$ is the number of ways. Then, we want the total number of ways, over all possible numbers of pieces, so we get
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*}
If you're looking for specific coefficients, it's easiest to use the Fibonacci-like recursion noted in Noble Mushtak's answer, or the telescoped version $a_{n+1}=2a_n-a_{n-k}$. The initial conditions are $a_0=a_1=1,a_{-1}=cdots=a_{-k+1}=0$. For the asymptotics? That'll come from the pole of $F$ nearest to zero - namely, the unique positive root $r$ of $x^k+cdots+x^2+x-1=0$. For $k>1$, $rin [0,1]$. The $n$th term will be approximately proportional to $r^{-n}$. An exact formula? You'd have to find all the roots of that polynomial and run partial fractions. The generating function then splits up as several terms of the form $frac{b_j}{x-c_j}$, each of which gives us a geometric series. It's all fine in theory, but that first step of solving the polynomial is a doozy.

First a note about terminology:

- a Partition of a positive integer $n$ is a non-decreasing sequence of positive integers summing to $n$;

- a Composition of a positive integer $n$ is an unordered sequence of positive integers summing to $n$.

That premised, you are speaking of the number of Compositions of $n$, whose terms (parts) are not-greater than $k$.

Consider the case in which you seek for the number of compositions of the positive number $s+m$
into $m$ parts not exceeding $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.
$$
that's the same as
$$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$ is given by the following sum
$$
N_b (s,r,m)quad left| {;0 leqslant text{integers }s,m,r} right.quad =
sumlimits_{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 - jleft( {r + 1} right) }
{ s - jleft( {r + 1} right)} }
$$
as widely explained in this related post.

Going back to your case, the
number of compositions of $n$ into $m$ parts not greater than $k$

will then be
$$
eqalign{
& N_c (n,k,m)quad left| {;1 le n,m,k} right.quad = cr
& = sumlimits_{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}
$$
while the
overall number of compositions of $n$ into parts not greater than $k$

will be the sum
of the above for $0 le m$ : if the sum extends over $n$ it will maintain the value $2^{n-1}$.
$$ bbox[lightyellow] {
eqalign{
& N_{c,t} (n,k)quad left| {;0 le n,k in mathbb Z} right.quad = cr
& = sumlimits_{0, le ,,m} {;sumlimits_{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}
}$$

In the example with $n=4$, the above gives for $k=1,2,3,4$
$$
1,5,7,8
$$
which in fact correspond to
$$
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}
$$

Finally note that:

- $N_{c,t}(n,k)$ correctly checks with OEIS seq. A126198, which provides further properties of these numbers;

- the o.g.f. of $N_{c,t}$ in $n$ is in fact the $F(x)$ given by @jmerry's answer (re. to the o.g.f. for $N_b$ given in related post);
$$
sumlimits_{0, le ,,n} {N_{c,t} (n,k),x^{,n} } = {{1 - x} over {1 - 2x + x^{,k + 1} }}
$$
- $N_{c,t}(n,k)$ satisfies the recursion given by @NobleMushtak
$$
N_{c,t} (n,k) = sumlimits_{j = 1}^k {N_{c,t} (n - j,k)} + left[ {n = 0} right]
$$
where $[P]$ denotes the Iverson bracket.