I want to find the generating function for the number of compositions (ordered partitions) of n such that no part is unique ( equivalently, every part appears at least twice). For example: there are 9 such compositions of the integer 6: 3+3, 2+2+2, 2+2+1+1, 2+1+2+1, 2+1+1+2, 1+2+2+1, 1+2+1+2, 1+1+2+2, 1+1+1+1+1+1.

This question is exercise 3.4 page 84 in the text: Combinatorics of Compositions and Words, Sylvia Heubach and Toufik Mansour.

The question actually asks for a bivariate generating function in which the number of parts in such compositions is indicated.


We can find a bivariate generating function that is exponential in $m$ (the number of parts), and ordinary in $n$. Other variants are harder questions, so I suspect this is what the exercise intended. We use $z$ to mark size ($n$), and $u$ to mark the number of parts ($m$).

Fix $m$, the number of parts. For any positive integer $k$, if we denote by $c_k(n,m)$ the number of compositions of $n$ into $m$ non-unique parts all equal to $k$ (thus $c_k(n,m) = 1$ when $n = mk$ and $m \neq 1$, and $0$ otherwise), then the generating function $$C_k(z, u) = \sum_{m,n \ge 0} c_k(n,m) z^n \frac{u^m}{m!} = \sum_{m \ge 0, m \neq 1} z^{mk} \frac{u^m}{m!} = e^{uz^k} - uz^k$$

When we allow compositions using two integers $k$ and $l$, the corresponding number of compositions $c_{k, l}(n, m)$ forms a binomial convolution, corresponding to which of the $m$ parts are chosen to be equal to $k$, and which equal to $l$: $$c_{k, l}(n, m) = \sum_{a \ge 0} \binom{m}{a} c_k(ak, a) c_l(n - ak, m - a)$$ which corresponds to a product of generating functions: $$C_{k,l}(z, u) = \sum_{m,n \ge 0} c_{k,l}(n,m) z^n \frac{u^m}{m!} = (\exp(uz^k) - uz^k)\cdot (\exp(uz^l) - uz^l)$$

Thus the class of all restricted compositions has generating function $$C(z, u) = \prod_{k=1}^{\infty}\left(\exp(uz^k) - uz^k\right)$$

Further simplification doesn't seem to be possible.


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.