1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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... $\endgroup$ – Pixel Jan 18 '13 at 14:51
  • 3
    $\begingroup$ 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... $\endgroup$ – Thomas Andrews Jan 18 '13 at 14:51
  • 1
    $\begingroup$ 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}$? $\endgroup$ – Hagen von Eitzen Jan 18 '13 at 14:52
  • $\begingroup$ @HagenvonEitzen I need to know what is the sequence for which (1+x+x10)20 is the generating function $\endgroup$ – Adam Sh Jan 18 '13 at 15:01
  • $\begingroup$ @ThomasAndrews yes, you right. But I still don't know how to do that $\endgroup$ – Adam Sh Jan 18 '13 at 15:02
3
$\begingroup$

$$(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

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Hurkyl Jan 18 '13 at 16:10
  • $\begingroup$ After your comment I edit the answer $\endgroup$ – Adi Dani Jan 18 '13 at 16:36
1
$\begingroup$

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\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.