Number of compositions of $n$ such that each term is less than equal to $k.$

Question

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?

Answer 1

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

As you have shown, $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$$

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.

Answer 2

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$, $r\in [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.

Answer 3

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 = \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)}\ } $$ 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 & = \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} $$ 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 & = \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} }$$

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); $$ \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)$ satisfies the recursion given by @NobleMushtak $$ N_{c\,t} (n,k) = \sum\limits_{j = 1}^k {N_{c\,t} (n - j,k)} + \left[ {n = 0} \right] $$ where $[P]$ denotes the Iverson bracket.