Partial sum of coefficients of polynomials Let me define polynomials of form $1+x^2+x^3+\cdots+x^k$ as $P(k,x)$.
Let $$Q(x)=\prod_{k=1}^{n}P(k,x)$$
How can I find the sum of coefficients for which exponent of $x$ is $\le T$, where $0 \le T \le \frac{n(n+1)}{2}$ (which we define as $S(T,n)$)?
Example for the clarity of problem:
Let $k=4$, then $$Q(x)=\prod_{k=1}^{4}P(k,x)=(1+x)(1+x+x^2)(1+x+x^2+x^3)(1+x+x^2+x^3+x^4)$$
$$Q(x)=x^{10}+4x^9+9x^8+15x^7+20x^6+22x^5+20x^4+15x^3+9x^2+4x+1$$
If $T=10$ then $S(10,4)=1+4+9+15+20+22+20+15+9+4+1=120$
If $T=5$ then $S(10,4)=22+20+15+9+4+1=71$
Is it possible to find $S(T,n)$ efficiently without calculating the product of all polynomials?
 A: I can't help you with a closed formula for $S(T,n)$, but we can construct a fairly simple algorithm for computing this recursively. Defining $a_k^{(n)}$ via $$Q_n(x) = \sum_{k=0}^{\frac{n(n+1)}{2}}a_k^{(n)} x^k$$ then $$Q_{n+1}(x) = Q_n(x)(1+x+\ldots+x^{n+1}) = \sum_{k=0}^{\frac{(n+1)(n+2)}{2}}a_k^{(n+1)} x^k$$
gives the recurence
$$a_k^{(n+1)} = \sum\limits_{\matrix{0\leq i\leq n+1,~~i+j=k\\0\leq j \leq \frac{n(n+1)}{2}}} a_j^{(n)}$$
Having computed $a_k^{(n)}$ the sum you are after is just $S(T,n) = \sum_{k=0}^T a_k^{(n)}$. In particular for $T\leq \frac{n(n-1)}{2}$ we get the simple relationship
$$S(T,n) = a_T^{(n+1)}$$
i.e. the sum is encoded in the $T$'th coefficient of the next polynomial, $Q_{n+1}$, in the series.
Here is a simple implementation of this in Mathematica:
nmax = 4;
ak = Table[Table[0, {k, 1, (n (n + 1))/2 + 1}], {n, 1, nmax}];
ak[[1]] = {1, 1};
Do[
  ak[[n, i + j + 1]] += ak[[n - 1, j + 1]]; 
  , {n, 2, nmax}, {i, 0, n}, {j, 0, (n (n - 1))/2}];
S[n_, T_] = Sum[ak[[n, k]], {k, 1, T + 1}];

