Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a number of length $l$, the sum of the digits range from $0$ to $9l$

For each sum, there are $x$ permutations of digits. find the sequence of length $9l+1$ that solves $x$.

I found a function that solves this problem without expanding the polynomial equation $l$ times:

$f(n \in S,l,b) = \sum\limits_{i=0}^{\lfloor\frac{n}{b}\rfloor}(-1)^{i}{l \choose i}{n+l-1-bi \choose l-1}$

($l=l$, $b=10$,$S={0,1,...,9l}$)

Where $f(n,l,b)$ is the $n^{th}$ coefficient of a polynomial of length $l$ and base $b$ where $S={0,1,...,(b-1)l}$

(thanks to Tom De Medts for giving me the proper terms.)

Are there other functions that give the $n^{th}$ polynomial coefficient? I can't seem to find one.

share|improve this question
3  
My first impression is that this question would fit better on math.stackexchange.com, but perhaps I am missing some subtlety or connection to more advanced themes –  Yemon Choi Feb 18 '11 at 8:36
add comment

1 Answer 1

up vote 7 down vote accepted

Your sequences are simply the coefficients of the polynomials $$(1 + x + x^2 + \dots + x^9)^L .$$

(This is a straightforward application of the theory of generating functions.)

share|improve this answer
    
I am willing to believe you, but does your argument still hold after examining past the first 10 numbers in the sequence, when the summation starts to be used? I added a latex that I think is the closed form. –  mna Feb 18 '11 at 16:12
1  
Yes, the argument is always correct. For each digit, the possible outcomes are 0,1,...,9, so the generating function for each digit is $1 + x + x^2 + \dots + x^9$. Since you are asking for the number of possible strings consisting of $L$ digits and summing up to a given number $t$, the answer is precisely the coefficient of $x^t$ in the product of these $L$ generating functions. –  Tom De Medts Feb 18 '11 at 16:31
    
You have convinced me thanks! Now taking a side-step, is there a simpler function than my f(t,L)? –  mna Feb 18 '11 at 17:02
add comment

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.