Generating function for number of $1$’s used to write $0$ to $n$ in base $10$

combinatoricsgenerating-functions

I am looking to find a generating function that will answer the question "how many $1$'s are used to write the sequence of numbers from $0$ to $n$ in base $10$".

For example, to write the number from $0$ to $10$, there are $2$ numbers with a $1$ digit: $1$ and $10$.

If the generating function is $F$, then the coefficient of $x^10$ in $F(10)$ should be $2$. Hopefully this has made it clear what I am seeking.

I found that there exists an entry for this sequence on OEIS(A094798), which also lists a generating function(at least, that's what I assumed the "g.f" meant. However, it appears the generating function is recursive, which doesn't make sense to me.

My question boils down to this: Are recursive generating functions useful? How can we extract the coefficients from such a function?

The recursive g.f. is making think that it's either incorrect, or not-useful for finding coefficients.

I'm new to all this, so any help, guidance, resources, etc would be helpful as well. Thanks in advance!

Best Answer

Many generating functions simply encode an existing algorithm as a power series. Here the algorithm is recursive:

Count the number of 1's in 0 to 9

Count the number of 1's in 0 to 99

Count the number of 1's in 0 to 999

And you can have a thought about what is the recursive relationship between steps. Should be something like

\begin{align} f(999) &= 10 * f(99) + 100 \\ f(99) &= 10 * f(9) + 10 \\ f(9) &= 10 * f(0) + 1 \end{align}

So $f(9) = 1, f(99) = 20$ and $f(999) = 300$

The generating function encodes all of the recursive relationships between $f(n)$ and $f(10n + k)$. Specifically, $g(x)$ is the generating function for $f(n)$ and $g(x^{10})$ is the generating function for $f(10n)$. I'm bringing this up because I want to emphasize that generating functions are not magical, they're often literally just recurrence relations just encoded as rational functions and in particular computing the sequence from the generating function is just as hard/just as easy as computing the recurrence(s) explicitly.

You can use it like this (in SageMath):

g(x) = 0
for i in range(3):
    g(x) = x/((1-x)*(1-x^10)) + ((1-x^10)/(1-x))^2*g(x^10)
g(x).series(x, 1000).coefficients(sparse=False)

Each time we update $g(x)$, it becomes up to the next power of $10$.

Note: the OEIS page has an incorrect formula for $g(x)$, it should be $1 - x^{10}$ not $(1 - x)^{10}$. If someone has an account they should edit this.

Related Question