2
$\begingroup$

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?

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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