This is a problem from Stanley's Enumerative Combinatorics that I'm failing at a bit (lot):

Let $\bar{c}(m,n)$ denote the number of compositions of $n$ with largest part at most $m$. Show that $$\sum_{n\geq 0}\bar{c}(m,n)x^n={{1-x}\over{1-2x+x^{m+1}}}$$

Some definitions: A composition of $n$ is an $ordered$ list of positive integers that equals $n$. If $\{a_1,...,a_k\}$ is one such composition, we say that the composition has $k$ $parts$.

I know it's pretty traditional to list a "what you've done so far" but I'm really about as blindly stuck as can be.

  • $\begingroup$ Neat question.${}$ $\endgroup$ – Alexander Gruber May 15 '13 at 20:14
  • $\begingroup$ @AlexanderGruber Stanley's book has many! $\endgroup$ – AsinglePANCAKE May 16 '13 at 1:27

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


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

| cite | improve this answer | |
  • $\begingroup$ ah, very cool. thank ya $\endgroup$ – AsinglePANCAKE May 16 '13 at 19:03

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

| cite | improve this answer | |

Hazy idea: I'd try to derive a relation $(\dagger)$ between for instance $\bar{c}(m, n)$ and $\bar{c}(m, n-1)$ (or even with multiple terms $\bar{c}(m, n-k)$), or something similar. The goal would then be to find an EDP for $f\colon x \to \sum_{n=0}^\infty \bar{c}(m, n)x^n$ by differentiating term by terms and using $(\dagger)$. Then, olving the EDP for $f$, one could get a closed-form expression of it — hopefully the one you're asked to prove.

Of course, the main step is to find (via combinatorics?) the said relation.

| cite | improve this answer | |
  • $\begingroup$ (Just to be clear: I don't actually know whether this would work; but that's what I'd try.) $\endgroup$ – Clement C. May 16 '13 at 1:55

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.