# Generating function of $(1 + x + x^{10})^{20}$

I try to find the generating function of $(1 + x + x^{10})^{20}$. My main problem is that all the forumalas I know, based on sequence (meaning, $1 + x + x^2 + x^3+\dots$ and so on), and I don't success to convert it to any sequence.

• Have you tried applying the Binomial theorem? If it's the coefficients your after (the coefficients of the powers of $x$) then this may help... – Pixel Jan 18 '13 at 14:51
• I think you mean the opposite - what is the sequence for which $(1 + x + x^{10})^{20}$ is the generating function. Because generating functions are functions based on a sequence, and $(1 + x + x^{10})^{20}$ is a function... – Thomas Andrews Jan 18 '13 at 14:51
• Do you just want to expand the power $(1+x+x^{10})^{20}=1+20x+190x^2+\ldots +20x^{191}+ x^{200}$ or do yo want the generating function of the sequence $(a_n)$ with $a_n=(1+n+n^{10})^{20}$? – Hagen von Eitzen Jan 18 '13 at 14:52
• @HagenvonEitzen I need to know what is the sequence for which (1+x+x10)20 is the generating function – Adam Sh Jan 18 '13 at 15:01
• @ThomasAndrews yes, you right. But I still don't know how to do that – Adam Sh Jan 18 '13 at 15:02

$$(1 + x + x^{10})^{20}=((1+(x+x^{10}))^{20}=\sum_{k=0}^{20}\binom{20}{k}(x+x^{10})^k=$$ $$=\sum_{k=0}^{20}\binom{20}{k}x^k(1+x^{9})^k=\sum_{k=0}^{20}\binom{20}{k}x^k\sum_{j=0}^{k}\binom{k}{j}x^{9j}=\sum_{k=0}^{20}\sum_{j=0}^{k}\binom{20}{k}\binom{k}{j}x^{k+9j}$$ let $0\leq k+9j=t\leq200\Rightarrow j=\frac{t-k}{9},k=t-9j$ $$\sum_{k=0}^{20}\sum_{j=0}^{k}\binom{20}{k}\binom{k}{j}x^{k+9j}=\sum_{k=0}^{20}\sum_{t=0}^{200}\binom{20}{k}\binom{k}{\frac{t-k}{9}}x^{t}=\sum_{t=0}^{200}\sum_{j=0}^{20}\binom{20}{t-9j}\binom{t-9j}{j}x^{t}$$ $\binom{k}{\frac{t-k}{9}}=0$ if $\frac{t-k}{9}$ is not integer
• When you make the change of variable $t = k + 9j$, it might be better to use it to replace $k$ rather than to replace $j$. It might help to observe that both sums can range over all integers (the terms not included are zero anyways) – Hurkyl Jan 18 '13 at 16:10
The sequence for which $(1+x+x^{10})^{20}$ is the generating function, is $1, 20, 190, 1140, 4845, 15504, 38760, 77520, 125970, 167960, 184776, 168340, 129390, 96900, 116280, 248064, 547485, 1008900, 1511830, 1847580, 1847751, 1515060, 1036830, 697680, 813960, 1705440, 3546540, 6049980, 8314400, 9237820, 8315160, 6065940, 3682200, 2403120, 3294600, 7209360, 14137710, 22174140, 27713590, 27713400, 22175565, 14186160, 7635720, 5426400, 9593100, 21318000, 38818140, 55427940, 62355150, 55426800, 38814264, 21395520, 10445820, 9767520, 21744360, 46636032, 77602365, 99768240, 99768240, 77597520, 46597272, 21705600, 10581480, 15736560, 39031320, 77613024, 116396280, 133024320, 116396280, 77597520, 38876280, 15116400, 9573720, 22713360, 55465560, 99768240, 133024320, 133024320, 99768240, 55426800, 22296690, 7558200, 9321780, 27790920, 62355150, 99768240, 116396280, 99768240, 62355150, 27713400, 8481980, 3359200, 9363770, 27713400, 55426800, 77597520, 77597520, 55426800, 27713400, 9237800, 2032316, 2015520, 8314020, 22170720, 38798760, 46558512, 38798760, 22170720, 8314020, 1847560, 352716, 1511640, 6046560, 14108640, 21162960, 21162960, 14108640, 6046560, 1511640, 167960, 125970, 1007760, 3527160, 7054320, 8817900, 7054320, 3527160, 1007760, 125970, 0, 77520, 542640, 1627920, 2713200, 2713200, 1627920, 542640, 77520, 0, 0, 38760, 232560, 581400, 775200, 581400, 232560, 38760, 0, 0, 0, 15504, 77520, 155040, 155040, 77520, 15504, 0, 0, 0, 0, 4845, 19380, 29070, 19380, 4845, 0, 0, 0, 0, 0, 1140, 3420, 3420, 1140, 0, 0, 0, 0, 0, 0, 190, 380, 190, 0, 0, 0, 0, 0, 0, 0, 20, 20, 0, 0, 0, 0, 0, 0, 0, 0, 1$ (and then only $0$'s)
Note that $a_n$ counts the number of ways to write $n$ as sum of $20$ numbers $\in\{0,1,10\}$.