# Generating Functions with composition

For a nonnegative integer $n$, a composition of $n$ means a partition in which the order of the parts matters.

Consider the generating function $$C(x) = \sum_{n=0}^{\infty} c_nx^n,$$ where $c_n$ is the number of distinct compositions of $n$ (note that $c_0=1$ by convention).

What is the value of $C\left(\tfrac 15\right)$?

How can I start this?

• Work out a few examples with low values of $n$, then establish a recurrence on the values of $c_n$. – Yves Daoust Jun 13 '15 at 16:04
• @user228320 I am curious why would you want to know the value of C(1/5)? – Geoffrey Critzer Jun 14 '15 at 16:01

Hint: $c_n = 2^{n-1}$ for $n>0$.

Think about $$(x+x^2+x^3+\cdots)(x+x^2+x^3+\cdots)\cdots\underbrace{(x+x^2+x^3+\cdots)}_{m-\text{th term}}$$ Coefficient of $x$ in the above expression is the number of ways we can add up $m$ natural numbers to $n$ respecting the order. So the generating function is $$1+\sum_{m=1}^\infty(x+x^2+x^3+\cdots)^m=\sum_{m=0}^\infty\left({x\over1-x}\right)^m={1-x\over1-2x}\\=(1-x)\sum_{m=0}^\infty(2x)^m\\ \therefore c_n=2^n-2^{n-1}=2^{n-1}$$

You can construct the partitions in a systematic way: take the partitions of $n-1$, and form two new sets: in blue, by appending $1$, in green by adding $1$ to the last element.

$$1\to(1)$$ $$2\to(1,1),(2)$$ $$3\to(1,1,1),(2,1),(1,2),(3)$$ $$4\to(1,1,1,\color{blue}1),(2,1,\color{blue}1),(1,2,\color{blue}1),(3,\color{blue}1)(1,1,\color{green}2),(2,\color{green}2),(1,\color{green}3),(\color{green}4)$$

The partitions so obtained are all different and they exhaust the partitions of $n$ (you find all the partitions of $n$ ending in $1$ and all the partitions of $n$ not ending in $1$, which must be partitions of $n-1$ when you deduce $1$). This establishes the recurrence

$$c_n=2c_{n-1}$$

and, for $n>0$, $$c_n=2^{n-1}.$$

Then, $$1+\frac12\sum_{n=1}^\infty\left(\frac25\right)^n.$$