Compositions of $n$ with largest part at most $m$

Solution 1:

I tried my own way and got something slightly different - more on that in a second. Let $c(m,n,k)$ be the number of integer compositions with largers part $\le m$ and exactly $k$ parts. Then

$$\sum_n c(m,n,k)x^n=\left.\sum_{p_1=1}^m\cdots\sum_{p_k=1}^m x_1^{p_1}\cdots x_k^{p_k}\right|_{x_1=x_2=\cdots=x_k=x}=\left(x\frac{1-x^m}{1-x~~~}\right)^k$$

and therefore

$$\sum_n c(m,n)x^n=\sum_n\left[\sum_{k\ge1}c(m,n,k)\right]x^n=\sum_{k\ge1}\sum_nc(m,n,k)x^n$$

$$=\sum_{k\ge1}\left(x\frac{1-x^m}{1-x~~~}\right)^k=\frac{\displaystyle x\frac{1-x^m}{1-x~~~}}{\displaystyle 1-x\frac{1-x^m}{1-x~~~}}=\frac{x(1-x^m)}{1-2x+x^{m+1}}.$$

Note that

$$\frac{x(1-x^m)}{1-2x+x^{m+1}}=\frac{1-x}{1-2x+x^{m+1}}-1,$$

so the given answer and mine differ merely by $1$. What's the deal? The reason we need to add $1$ I presume is that $n=0$ has one integer composition, namely the empty set (it is the empty sum). At least that's what OEIS says, I haven't actually seen the textbook's definition/convention for $0$.

Solution 2:

This can be solved in two ways, both quite easy.

For the first, note that the given fraction simplifies due to the decomposition $1-2x+x^{m+1}=(1-x)(1-x-x^2-\cdots-x^m)$ to the rational function $$ \frac1{1-x-x^2-\cdots-x^m}. $$ The coefficients $a_i$ of the corresponding power series satisfy $a_0=1$ and the recurrence $$ a_i=a_{i-1}+a_{i-2}+\cdots+a_m \qquad\text{for $i>0$,} $$ where terms with negative index are taken to be$~0$. But taking $a_i=\bar c(n,i)$ this recurrence can be easily seen to be satisfied: a composition of $i>0$ has a final part$~k$ with $1\leq k\leq m$, and removing that part leaves a composition of $i-k$ into parts at most$~m$, each obtained exactly once, so $\bar c(n,i)=\sum_{k=1}^m\bar c(n,i-k)$.

The other way is to use the form of the fraction given in the question directly. Its denominator indicates that the recurrence $ a_i=2a_{i-1}-a_{i-(m+1)} $ should be satisfied for sufficiently large$~i$. Here each composition of $i$ can be obtained in one of two ways from a composition of $i-1$: either adding a part $1$, or by increasing the last part by$~1$. However the latter method cannot be applied to all compositions of $i-1$ into parts at most $m$, since it may make the final part $m+1$. The number of such forbidden extensions equals $\bar c(n,i-(m+1))$ (each composition counted by that number produces one when a $m+1$ added at its end), so that number must be subtracted in the recurrence. With again the convention that recurrence terms with negative indices are taken to be $0$, the recurrence relation gives the correcct number for $i>1$, but the value$~2$ it would give for $i=1$ is one too much (since the composition of $0$ has no part to increase). This is reflected by the term "$-x$" in the numerator of the fraction $\frac{1-x}{1-2x+x^{m+1}}$.