I am given the following function:
$f(x) = \prod_{k=1}^{n}(1+x^k).$
What is a fast way to find coefficient of $x^n$ in its Maclaurin series expansion i.e. $\frac{f^{(n)}(0)}{n!}$?
(I suspect this function is somehow used in number theory but I'm not quite familiar with the topic).
Update:
Following the answer from MathOverview I can find the third order derivative:
$\begin{align} D_x^{(3)}f(x) = & \sum \limits_{1 \le k_1 \le n} k_1(k_1-1)(k_1-2)x^{k_1-3} \prod \limits_{\substack{1 \le k_0 \le n \\ k_{0} \ne k_1}} (1+x^{k_0}) + \\ + & \sum \limits_{1 \le k_1 \le n} \sum \limits_{\substack{1 \le k_2 \le n \\ k_2 \ne k_1}} k_1 (k_1-1) k_2 x^{k_1+k_2-3} \prod \limits_{\substack{1 \le k_0 \le n \\ k_0 \ne k_1, k_2}} (1+x^{k_0}) + \\ + & \sum \limits_{1 \le k_1 \le n} \sum \limits_{\substack{1 \le k_2 \le n \\ k_2 \ne k_1}} k_1 k_2 (k_1 + k_2 -2) x^{k_1+k_2-3} \prod \limits_{\substack{1 \le k_0 \le n \\ k_0 \ne k_1, k_2}} (1+x^{k_0}) + \\ + & \sum \limits_{1 \le k_1 \le n} \sum \limits_{\substack{1 \le k_2 \le n \\ k_2 \ne k_1}} \sum \limits_{\substack{1 \le k_3 \le n \\ k_3 \ne k_1, k_2}} k_1 k_2 k_3 x^{k_1 + k_2 + k_3 - 3} \prod \limits_{\substack{1 \le k_0 \le n \\ k_0 \ne k_1, k_2, k_3}} (1+x^{k_0}) \end{align}$
(it is assumed here that $x^k = 0$ if $k < 0$).
Considering the first three derivatives, it looks like the $n$-th order derivative is going to be a sum of $2^{n-1}$ huge terms. Actually, since I'm interested in $f^{(n)}(0)$, I only need to find coefficients of $x^0$, and there are probably not that many of them. However, I still don't understand how to find them efficiently.
This is not a complete answer. But an indication of the way to go to get your answer. The way is to make the successive derivatives until a pattern is realized and we use an inductive reasoning for the general case. \begin{align} D_{x} f(x) = & D_{x}\left(\prod_{1\leq k_0\leq n}(1+x^{k_{0}})\right) \\ = & \sum_{1\leq k_{1}\leq n} k_{1}\cdot x^{k_{1}-1}\cdot\left(\prod_{\substack{1\leq k_{0}\leq n\\ k_{0}\neq k_{1}}}(1+x^{k_0})\right) \\ \end{align} \begin{align} D_x^{(2)} f(x) = & D_x\left( \sum_{1\leq k_{1}\leq n} k_{1}\cdot x^{k_{1}-1} \cdot \left( \prod_{\substack{1\leq k_{0}\leq n\\ k_{0}\neq k_{1}}} (1+x^{k_0}) \right) \right) \\ = & \sum_{1\leq k_{1}\leq n} D_x\left( k_{1}\cdot x^{k_{1}-1} \cdot \left( \prod_{\substack{1\leq k_{0}\leq n\\ k_{0}\neq k_{1}}} (1+x^{k_0}) \right) \right) \\ = & \sum_{1\leq k_{1}\leq n} D_x \left( k_{1}\cdot x^{k_{1}-1} \right) \cdot \left( \prod_{\substack{1\leq k_{0}\leq n\\ k_{0}\neq k_{1}}} (1+x^{k_0}) \right) \\ + & \sum_{1\leq k_{1}\leq n} \left( k_{1}\cdot x^{k_{1}-1} \right) \cdot D_x \left( \prod_{\substack{1\leq k_{0}\leq n\\ k_{0}\neq k_{1}}} (1+x^{k_0}) \right) \\ = & \sum_{1\leq k_{1}\leq n} k_{1}\cdot(k_{1}-1)\cdot x^{k_{1}-2} \left( \prod_{\substack{1\leq k_{0}\leq n\\ k_{0}\neq k_{1}}} (1+x^{k_0}) \right) \\ + & \sum_{1\leq k_{1}\leq n} \sum_{\substack{1\leq k_{2}\leq n \\ k_{2}\neq k_{1} }} k_{1}\cdot k_{2}\cdot x^{k_{1}+k_{2}-2} \cdot \left( \prod_{\substack{1\leq k_{0}\leq n\\ k_{0}\neq k_{1},k_{2}}} (1+x^{k_0}) \right) \end{align} And so on...