3
$\begingroup$

I was wondering if any of you guys could help me with this combinatorial problem. I need to determine the exact number of compositions $(a_1, \ldots,a_k)$ of $n$ which have $k$ parts and satisfy $a_i\ge i$ for $i = 1, \ldots,k$.

Thanks in advance!

2 Answers 2

2

The generating function for such compositions is

$g(x)=\prod_{i=1}^k\sum_{j\ge i}x^j=\prod_{i=1}^k\frac{x^i}{1-x}=\frac1{(1-x)^k}\prod_{i=1}^kx^i=\frac{x^{k(k+1)/2}}{(1-x)^k}\;,$

so the coefficient of $x^n$ in this function is the number that you want. A standard and very useful generating function is

$\frac1{(1-x)^k}=\sum_{n\ge 0}\binom{k+n-1}nx^n\;;$

using this, you should be able to find the coefficient of $x^n$ in $g(x)$.

1

You can add up the excess of the conditions beyond the $1$ required by a general composition to find that $1+\dotso+k-1=k(k-1)/2$ of the sum has to go into fulfilling the conditions. On top of that you can add any of the

$\binom{n-k(k-1)/2-1}{k-1}$

compositions of the remaining sum with $k$ parts, so this is the number you're looking for.