# How to find the coefficient of $x^{l}$ in the expansion of $(1+x+x^{2}+...+x^{n})^{m}$ for some given $l$? [duplicate]

Suppose I'd like to find the coefficient of $$x^{l}$$ in the expansion of $$(1+x+x^{2}+...+x^{n})^{m}$$, where $$n$$ and $$m$$ are given positive integers, for some given integer $$l$$ such that $$n < l < mn$$. Is there a straightforward formula (in terms of some multinomial coefficient, or similar)?

Using the ideas of a linked post such as $$\left(\sum_0^n x^s\right)^m=(1-x^{n+1})^m (1-x)^{(-m)}$$ found a much more concise answer. Again using $$L$$ in place of $$l\;$$ the coeff of $$x^L$$ is $$\sum_{k=0}^{min(m,\frac L{(n+1)})}(-1)^k\binom{m}{k}\binom{m+L-k(n+1)-1}{L-k(n+1)}$$

For n=1 the answer is obvious so the obvious assumptions are n>1,m>1. For sufficiently small m or n you could likely write a reasonable formula but for general m,n I am not sure of a 'straightforward' or 'closed form' answer, depending upon exactly what one would classify as being in one of those 2 categories. Though one may express the answer perhaps in the form:

$$\sum_{m_1=0}^{min(m,L)}\sum_{m_2=0}^{min(m,L)}\dots \sum_{m_{min(L,n)}=0}^{min(m,L)}C(m_1,m_2,\dots,m_{min(L,n)})\prod_{j=0}^{min(L,n)}f_{j}^{(m-m_j)}\;$$

where $$f_j$$ is $$\frac{d^j}{d\:x^j}\sum_{i=0}^{n}x^i\;$$ , the superscripts $$(m-m_j)$$ are the powers or exponents and the $$C(m_1,m_2,\dots,m_{min(L,n)})$$ are constants which are the result of differentiating $$\left(\sum_{i=0}^{n}x^i\right)^m \;$$ L times where have written the capital L to stand for your $$l$$. Then we can set $$x=0$$ and divide by $$L!$$ to obtain the answer for desired coefficient which would then be

$$\frac1{L!}\left(\sum_{m_1=0}^{min(m,L)}\sum_{m_2=0}^{min(m,L)}\dots \sum_{m_{min(L,n)}=0}^{min(m,L)}C(m_1,m_2,\dots,m_{min(L,n)})\prod_{j=0}^{min(L,n)}({j!})^{(m-m_j)}\right)\;$$

Though finding and exressing the $$C(m_1,m_2,\dots,m_{min(L,n)})$$ coeff's may be quite unwieldly and have not done so as yet so
In order that the length of writing the formula or answer does not increase proportional to m or n I choose to solve it by a recursive routine which means it calls itself and is as follows. Have tried to write it in a kind of universal hopefully simple enough language that you could easily transfer it to fortran(my favorite) or basic or most any other symbolic math programs etc. The final answer, that is coeff. of $$x^L$$, is cf and have named the recursive routine nicf(ni,nl,nm,nn) with it's 4 arguments in parenthesis which follows where I have written capital L for your $$l$$.

nicf(ni,nl,nm,nn): for i=1 thru $$min(\frac{nl}{nn},nm)$$ do( if $$nl\!-\!i\:nn\!<\!nm\!-\!i\!+\!1$$ then $$cf\!=\!cf\!+\!ni\binom{nm}{i}\binom{nm-i}{nl-i\:nn}$$ ,if $$nm\!-\!i>0$$ then for j=2 thru $$min(nn\!-\!1,nl\!-\!i\:nn)$$ do nicf($$ni\binom{nm}{i},nl\!-\!i\:nn,nm\!-\!i,j$$) )

All quantities are integers and all terms in the routine are local except the accumulated answer cf which is global. Note $$ni\binom{nm}{i}...$$ means $$ni$$ times $$\binom{nm}{i}...\;$$ and $$\;i\:nn$$ means $$i$$ times $$nn$$, the perhaps small figure '1' and the $$1$$ both mean the same which is one, and where have written ...do cf(...) it means same as call cf(...) which may be more common in other languages. The $$\binom{a}{b}$$ means $$\frac{a!}{b!(a\!-\!b)!}$$. Now assuming you understand that routine it is used as follows in a simple program.

if L<m+1 then cf=$$\binom{m}{L}$$ else cf=$$0$$, for k=max(ceiling($$\frac{L}m$$),2) thru n do nicf($$1$$,L,m,k)

And the final answer will be cf=coeff. of $$x^L\;$$ Have tested it in symbolic program maxima for sufficiently large enough m,n,L to be reasonably sure it is correct. To try and write a better general formula etc. it seems it may be good to study partitions and perhaps generating functions such as in Knuth 'Art of Computer Programming' vol I fundamental algorithms.