MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
My first impression is that this question would fit better on, but perhaps I am missing some subtlety or connection to more advanced themes – Yemon Choi Feb 18 '11 at 8:36
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|cite|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
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

Your Answer


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.