Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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... –  pbs Jan 18 '13 at 14:51
3  
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
1  
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

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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
    
After your comment I edit the answer –  Adi Dani Jan 18 '13 at 16:36

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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