Intereting Posts

lim sup inequality $\limsup ( a_n b_n ) \leq \limsup a_n \limsup b_n $
Find the area enclosed by the curve $r=2+3\cos \theta$.
Meaning/Justification for Describing Functions as 'Orthogonal'
Explanation for summation complex analysis method
A Regular Tetrahedron is a cool Polyhedron.
How to prove $\sum_{n=0}^\infty \left(\frac{(2n)!}{(n!)^2}\right)^3\cdot \frac{42n+5}{2^{12n+4}}=\frac1\pi$?
Parallel lines divide a circle's area into thirds
$5^n+n$ is never prime?
Prove that if $A\triangle B = C\triangle B$, then $A = C$
Confused about the $\pm$ sign?
Suggested textbook for Multivariable Calculus
Family of normal derivatives does not imply family is normal
Why are maximal ideals prime?
Can all real polynomials be factored into quadratic and linear factors?
How to express $z^8 − 1$ as the product of two linear factors and three quadratic factors

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

- Equal sized partitions without overlap
- What is the rank of COCHIN
- Intuitively understanding $\sum_{i=1}^ni={n+1\choose2}$
- Permutations of a string with duplicate characters
- Compute the following sum $ \sum_{i=0}^{n} \binom{n}{i}(i+1)^{i-1}(n - i + 1) ^ {n - i - 1}$?
- How many total order relations on a set $A$?

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.

- Questions about Combinatorial Proof of $\sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$
- Number of connected graphs on labeled vertices, counted according to parity
- count the number of words with length $n$ using $a,b,c$ that contain odd number of $a$'s.
- maximum size of a $k$-intersecting antichain of $$
- Who conjectured that there are only finitely many biplanes, and why?
- Combinatorial proof of a Stirling number identity.
- If a number can be expressed as a product of n unique primes…
- Can we solve this using stars and bars?
- Number of ways to connect sets of $k$ dots in a perfect $n$-gon
- A committee of four people, containing at least one man and one woman, must be chosen from four men and three women.

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

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

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.

- Rigorous proof that surjectivity implies injectivity for finite sets
- If $A$ is an invertible skew-symmetric matrix, then prove $A^{-1}$ is also skew symmetric
- How many ways are there to divide $100$ different balls into $5$ different boxes so the last $2$ boxes contains even number of balls?
- Is $\mathrm{ZFC}^E$ outright inconsistent?
- Prove the converse of Wilson's Theorem
- How many number of functions are there?
- How to efficiently generate five numbers that add to one?
- Prime Number Theorem and the Riemann Zeta Function
- Help understanding the complexity of my algorithm (summation)
- Difference of random variables
- When do we get extraneous roots?
- Finding the summation of the floor of the series identity
- Of any 52 integers, two can be found whose difference of squares is divisible by 100
- Josephus' Puzzle Basic Java with some basic math.
- How do I show that the sum $(a+\frac12)^n+(b+\frac12)^n$ is an integer for only finitely many $n$?