0
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ 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 $\endgroup$
    – Yemon Choi
    Feb 18, 2011 at 8:36

1 Answer 1

7
$\begingroup$

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

$\endgroup$
3
  • $\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
    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$ 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
    Feb 18, 2011 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.