4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ See this, specifically $A$-restricted compositions. $\endgroup$ – MathematicsStudent1122 Dec 28 '18 at 21:48
  • $\begingroup$ Well, for $k=2$ you get the Fibonacci sequence, so if there is a general formula, it will be complicated for sure. $\endgroup$ – SmileyCraft Dec 28 '18 at 21:48
  • $\begingroup$ @MathematicsStudent1122 I saw this, but it does not give me the answer to my question. Maybe I am missing something. Perhaps you could elaborate? $\endgroup$ – model_checker Dec 28 '18 at 21:50
  • $\begingroup$ 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 $\endgroup$ – Mustang Dec 28 '18 at 21:52
  • $\begingroup$ @SmileyCraft: not so much complicated actually (see my answer). $\endgroup$ – G Cab Dec 30 '18 at 19:07
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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)$. $\endgroup$ – SmileyCraft Dec 28 '18 at 22:00
  • $\begingroup$ 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? $\endgroup$ – model_checker Dec 29 '18 at 19:04
  • $\begingroup$ @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. $\endgroup$ – Noble Mushtak Dec 29 '18 at 19:52
2
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.