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

Question

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.

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, Commented Feb 18, 2011 at 8:36

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

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

6,6141 gold badge27 silver badges48 bronze badges

$\begingroup$ 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. $\endgroup$
– mna
Commented Feb 18, 2011 at 16:12
1

$\begingroup$ 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. $\endgroup$
– Tom De Medts
Commented Feb 18, 2011 at 16:31
$\begingroup$ You have convinced me thanks! Now taking a side-step, is there a simpler function than my f(t,L)? $\endgroup$
– mna
Commented Feb 18, 2011 at 17:02

Add a comment |

1 Answer 1