Krdytkyu

Find coefficient of $x^6$ in
$(1+x)(1+x^2)^2.....(1+x^n)^n$

A creative approach. $prod_{kgeq 1}(1+x^k)^k$ is the exponential of
$$ sum_{kgeq 1}k log(1+x^k) = sum_{kgeq 1}ksum_{ngeq 1}frac{(-1)^{n+1}}{n} x^{kn}=sum_{mgeq 1}mx^m sum_{dmid m}frac{(-1)^{d+1}}{d^2} $$
or
$$ x+frac{3 x^2}{2}+frac{10 x^3}{3}+frac{11 x^4}{4}+frac{26 x^5}{5}+5 x^6 + O(x^7).$$
Since $exp(z)=1+z+o(z)$, it is enough to look for the coefficient of $x^6$ in
$$ 1+x+2 x^2+5 x^3+8 x^4+16 x^5+color{red}{28}, x^6 + O(x^7).$$
This coefficient can be found also through numerical integration, since it equals
$$ frac{1}{2pi i}oint_{|z|=varepsilon}expleft[z+frac{3 z^2}{2}+frac{10 z^3}{3}+frac{11 z^4}{4}+frac{26 z^5}{5}+5 z^6right]frac{dz}{z^7} $$
(any numerical approximation of this integral within an error $<frac{1}{2}$ does the job, since we know in advance that the value of this monster is a natural number).

Your function is effectively a generating function for the number of ways you can express a number as a sequence where the sum of the terms in the sequence is equal to our number and within the first $1$ terms all terms are either $0$ or $1$, within the next $2$ terms all terms are either $0$ or $2$, within the next $3$ terms all terms are either $0$ or $3$, etc... on up to the final $n$ terms where all terms are either $0$ or $n$.

$underbrace{underline{~}}_{1's}underbrace{underline{~}~underline{~}}_{2's}underbrace{underline{~}~underline{~}~underline{~}}_{3's}cdots underbrace{underline{~}~underline{~}~underline{~}~underline{~}~underline{~}~underline{~}}_{6's}$

One such sequence might be $underbrace{underline{0}}_{1's}underbrace{underline{0}~underline{0}}_{2's}underbrace{underline{3}~underline{0}~underline{3}}_{3's}cdots underbrace{underline{0}~underline{0}~underline{0}~underline{0}~underline{0}~underline{0}}_{6's}$

I would break down into cases based on the different ways that you can reach a total of $6$ using at most one $1$'s, at most two $2$'s, at most three $3$'s, etc..., where the terms appear in (non-strictly) increasing order, noting that we may stop at $6$ since if we continue past $6$ the sum would be larger than $6$ if we use any of those terms anyways.

The ways you can do this are $1+2+3$, $2+4$, $3+3$, $1+5$, $6$. You can check there are no other ways subject to our constraints.

Now, for each of these, let us figure out the number of ways to select which of the positions in our sequence receive the number in question and which receive the zeroes. For example in the case of $1+2+3$, there is one way to choose where to place the $1$. There are $2$ ways to choose how to place the $2$, and there are $3$ ways to choose how to place the $3$. This gives $1times 2times 3$ ways to have gotten a sum of $6$ using $1$'s, $2$'s and $3$'s and enough other zeroes to fill the spaces in the sequence subject to our constraints.

Similarly there are $2times 4, 1times 5$ and $6$ ways in the other cases respectively. The only one of our cases which doesn't follow this pattern is the case for $3+3$ which instead has $binom{3}{2}=3$ options for how to distribute the $0$'s instead.

This gives a grand total of:

$$1times 2times 3 + 2times 4 + 3 + 1times 5 + 6 = 6+8+3+5+6=28$$

Notet that the coefficient of $x^6$ is
begin{align}
sumprod_{k=1}^nbinom k{t_k}
end{align}
where the sum is taken over $0leq t_kleq k$ such that $sum_{k=1}^nkt_k=6$.
Note that $t_k=0$ for $k>6$.
The only possible sums $sum_{k=1}^6kt_k=6$ are:
begin{align}
6=1cdot 0+2cdot 0+3cdot 0+4cdot 0+5cdot 0+6cdot 1\
6=1cdot 1+2cdot 0+3cdot 0+4cdot 0+5cdot 1+6cdot 0\
6=1cdot 0+2cdot 1+3cdot 0+4cdot 1+5cdot 0+6cdot 0\
6=1cdot 0+2cdot 0+3cdot 2+4cdot 0+5cdot 0+6cdot 0\
6=1cdot 1+2cdot 1+3cdot 1+4cdot 0+5cdot 0+6cdot 0
end{align}
consequently, the required coefficient is
begin{align}
c
&=binom 10binom 20binom 30binom 40binom 50binom 61\
&+binom 11binom 20binom 30binom 40binom 51binom 60\
&+binom 10binom 21binom 30binom 41binom 50binom 60\
&+binom 10binom 20binom 32binom 40binom 50binom 60\
&+binom 11binom 21binom 31binom 40binom 50binom 60\
&=6+5+8+3+6\
&=28
end{align}

Here is my attempt at pitching the answer as simply as possible. Hope it's easy to understand.

If you want a systematic way of multiplying those then remember that the $k^{text{th}}$ row of Pascal's triangle gives $a_{k,r}$, the coefficients of $x^r$ in the expansion of $(1+x)^k$:

$$begin{array}{c|cccccccc}
kbackslash r& x^0 & x^1 & x^2& x^3& x^4& x^5& x^6\hline
0 & 1 &&&&&&\
1 & 1 & 1 &&&&&\
2 & 1 & 2 & 1 &&&&\
3 & 1 & 3 & 3 & 1 &&&\
4 & 1 & 4 & 6 & 4 & 1 &&\
5 & 1 & 5 & 10 & 10 & 5 & 1 &\
6 & 1 & 6 & 15 & 20 & 15 & 6 & 1end{array}$$

Remember also that each coefficient in row $k$ column $x^r$ is found by adding the coefficients in the previous row (row $k-1$) in columns $x^r$ and $x^{r-1}$. We represent this with the recurrence

$$a_{k,r}=a_{k-1,r}+a_{k-1,r-1}$$

Each row $k$ represents the expansion of $(1+x)times (1+x)^{k-1}$.

In a similar way we can expand your product

$$(1+x)(1+x^2)^2(1+x^3)^3cdots (1+x^k)^k$$

by creating a table of coefficients $b_{k,r}$ in which each row $k$ represents the resulting $x^r$ coefficients $(1+x^k)^k$ multiplied by the polynomial of the previous row.

Our recurrence is now

$$b_{k,r}=a_{k,0}b_{k-1,r}+a_{k,1}b_{k-1,r-k}+a_{k,2}b_{k-1,r-2k}+a_{k,3}b_{k-1,r-3k}+cdots$$

We can produce a table much like with Pascal's recurrence, viz:

$$begin{array}{c|cccccccc}
kbackslash r& x^0 & x^1 & x^2& x^3& x^4& x^5& x^6\hline
0 & 1 &&&&&&\
1 & 1 & 1 &&&&&\
2 & 1 & 1 & 2 & 2 & 1 & 1 &\
3 & 1 & 1 & 2 & 5 & 4 & 7 & 9\
4 & 1 & 1 & 2 & 5 & 8 & 11 & 17\
5 & 1 & 1 & 2 & 5 & 8 & 16 & 22\
6 & 1 & 1 & 2 & 5 & 8 & 16 & 28end{array}$$

Here the recurrence gives each successive row by multiplying the previous row coefficients by the relevant $a_{k,r}$ values and adding the result.

Since we only want $x^6$ there is no need to expand past row $6$ column $6$. We find that calculation gets easier with each successive row due to the recurrence ignoring $b_{k-1,r-s}$ terms where $s$ is not a multiple of $k$.

So our answer is, for all $k$

begin{array}{c|c}k & b_{k,6}\hline
0 & 0\
1 &0\
2 & 0\
3 &9\
4 &17\
5 &22\
6 &28\
7 &28\
vdots &vdots\end{array}

clearly the answer stays at $28$ for all $kge 6$.

Note: I've used $k$ instead of $n$.