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

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?

• See this, specifically $A$-restricted compositions. – MathematicsStudent1122 Dec 28 '18 at 21:48
• Well, for $k=2$ you get the Fibonacci sequence, so if there is a general formula, it will be complicated for sure. – SmileyCraft Dec 28 '18 at 21:48
• @MathematicsStudent1122 I saw this, but it does not give me the answer to my question. Maybe I am missing something. Perhaps you could elaborate? – model_checker Dec 28 '18 at 21:50
• You can convert them into eqs. and find no. of integral solutions here is a link of finding no. of possible integral solutions math.stackexchange.com/a/2990467/584828 – Mustang Dec 28 '18 at 21:52
• @SmileyCraft: not so much complicated actually (see my answer). – G Cab Dec 30 '18 at 19:07

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.

• For computing the $k$'th order Fibonacci numbers, you can use the formula $f(n,k)=2f(n-1,k)-f(n-k-1,k)$. – SmileyCraft Dec 28 '18 at 22:00
• For a given $k,$ the initial conditions for the recurrence are $f(1,k) = 1, f(2,k) = 2, f(3,k) = 2^{3-1}=4, \cdots f(k,k)=2^{k-1},$ right? – model_checker Dec 29 '18 at 19:04
• @Hello_World No, I defined the initial conditions as $f(n,k)=0$ for $n < 0$ and $f(0,k)=1$ for $n=0$. Then, you can figure out $f(1,k), f(2,k), ...$ from the initial conditions using the recurrence. – Noble Mushtak Dec 29 '18 at 19:52

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.

• you might be interested to know that the coefficients of $F(x)$ might be expressed through a finite sum (see my answer). – G Cab Dec 30 '18 at 19:01

- 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.