Let $a_1,a_2,\ldots,a_k $ be non negative integers, and let $a(n)$ be the number of compositions of $n$ into $k$ parts so that $i$-th part is not larger than $a_i$. Find the ordinary generating function $A(x)=\sum_{n\ge0}^\ a(n){x^n}$
I set $B(x)=$ generating function of constructing $i$-th part is not larger than $a_i$. Then, $A(x)={1\over 1-B(x)}$ by the compositional formula. But I don's know how to get $B(x)$
Best Answer
HINT: The compositional formula doesn’t apply here: you’re not splitting $[n]$ into an arbitrary number of subintervals and performing the same task on each subinterval. In fact you’re counting the solutions in positive integers to the equation $\sum_{i=1}^kx_i=n$ subject to the condition that $x_i\le a_i$ for $i=1,\ldots,k$. In other words, you’re looking for the coefficient of $x^n$ in
$$(x+x^2+\ldots x^{a_1})(x+x^2+\ldots x^{a_2})\ldots(x+x^2+\ldots x^{a_k})\;,$$
or
$$[x^n]\prod_{i=1}^k\left(x+x^2+\ldots x^{a_i}\right)=[x^n]\left(x^k\prod_{i=1}^k(1+x+\ldots+x^{a_i-1})\right)\;.$$
The sum inside the product is a finite geometric series, so you can easily get a closed form for it, and at that point you’ll have your generating function. It will be a polynomial, since $a(n)$ is clearly $0$ for sufficiently large $n$.