Welcome to MathOverflow

Question

0

1

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.

edited Feb 18 2011 at 22:38

asked Feb 18 2011 at 8:20

mna
55●4

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 2011 at 8:36

Tom De Medts · Accepted Answer · 2011-02-18 10:45:57Z UTC

7

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.)

answered Feb 18 2011 at 10:45

Tom De Medts
2,941●7●17

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 2011 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 2011 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 2011 at 17:02

How many permutations for each sum of digits of a number of length l? (solved but asking for insight)

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.