How many good integers less than $10^n$ are there?

80 Views Asked by At

Positive integer is good if it has $1$ as a digit. How many good integers less than $10^n$ are there?

The problem is trivial and it solution is easy to find. I'm asking about the method of solving with GF. Let's make an exponential generating function $$H(x) = ({x\over 1!} + {x^2\over 2!}+ {x^3\over 3!}+...) (1+{x\over 1!} + {x^2\over 2!}+ {x^3\over 3!}+...)^9$$ $$ = (e^x-1)e^{9x}$$

My question here is, why this function really "recognise" good numbers? Namely the same GF is for any other number. Wouldn't it be more correcly to write $$H(x) = ({a\over 1!} + {a^2\over 2!}+ {a^3\over 3!}+...) (1+{x\over 1!} + {x^2\over 2!}+ {x^3\over 3!}+...)^9$$ $$ = (e^a-1)e^{9x}$$ or even $$H(x) = (e^{x_1}-1) e^{x_2}e^{x_3}... e^{x_{10}}$$ and of course such GF doesn't really help much here, or does it?

1

There are 1 best solutions below

8
On BEST ANSWER

Well for a start, because these are exponential generating functions, the correct way to extract coefficients would be$^\dagger$

$$ \sum_{i,j} c_{i,j} \frac{a^ix^j}{i!j!} \longmapsto c_{0,n} + \binom n1 c_{1,n-1} + \binom n2 c_{2,n-2} + \binom n3 c_{3,n-3} + \dots + c_{n,0}. $$

If $n = i + j$ these terms are

$$ \binom{i+j}i c_{ij} = \frac{(i+j)!}{i!j!} c_{i,j}.$$

Then this sum $\sum \binom ni c_{i,n-i}$ is the same as the coefficient of $x^n/n!$ when you set $a = x$.

$$ \sum_{i,j} c_{i,j} \frac{a^ix^j}{i!j!} \mapsto \sum_{i,j} c_{i,j} \frac{x^{i+j}}{i!j!} = \sum_{i,j} c_{i,j} \frac{(i+j)!}{i!j!} \frac{x^{i + j}}{(i + j)!} $$

Now collecting all the terms where $i + j = n$ we get

$$ \sum_n \left(\sum_{i + j = n} \binom{i + j}{i} c_{i,j} \right) \frac{x^n}{n!}. $$


$^\dagger$ The simple reason why we add the binomial coefficients (for EGFs) is they make the formula work out correctly as you can see above.

The more involved reason that explains this better is that exponential generating functions correspond to putting structures on sets. In this example the sets are the decimal places and the structures are the digits. Specifically:

$$ \mathcal{A} = \text{the digit 1}, \\ \mathcal{X} = \text{all other digits}. $$

Here the EGF of $\mathcal{A}$ is $e^a - 1$ because there is a unique way to make a number with $n$-decimal places where every digit is $1$ and we subtract $1$ to exclude $n = 0$. The EGF of $\mathcal{X}$ is $e^{9x}$ since there are $9^n$ numbers with $n$-decimal places that don't contain a $1$.

When we multiply the structures $\mathcal{A} * \mathcal{X}$, what that means in EGF-land is to partition the decimal places into two sets, put an $\mathcal{A}$-structure on one set (i.e. make those digits 1) and put an $\mathcal{X}$-structure on the remaining digits (i.e. make those digits any other digit). For example the number $11316$ corresponds to taking a partition $\{1,2,4\} \cup \{3,5\}$ of $\{1,2,3,4,5\}$, putting $1$'s in spots $1,2,4$ and putting non-$1$'s in spots $3,5$. By removing the $a^0$ term from the EGF for $\mathcal{A}$ we are disallowing a partition where there are zero $1$'s.

It is exactly this partitioning that gives you the binomial coefficients because there are $\binom{n}{i}$ ways to partition the decimal places to give you $i$ $1$'s and $n - i$ non-$1$'s.


If we wanted to, we could track every digit by a different variable. This would give the EGF $e^{x_0}(e^{x_1} - 1)e^{x_2}e^{x_3} \cdots e^{x_9}$. The coefficient $c_{i_0,i_1,\dots,i_9}$ counts numbers with $i_k$ digits equal to $k$.

To get the number we are interested in, we want to collect all tuples where $i_0 + i_1 + \dots + i_9 = n$. These correspond to all the ways to partition the decimal of a number with $n$-decimal places into $10$ sets where we then put $0$'s in the first set of decimal places and $1$'s into the second and so on.

The number of ways of partitioning $n$ into sets of size $i_0, i_1, \dots, i_9$ with $i_0 + \dots + i_9 = n$ is by definition given by the multinomial coeficient equal to $\binom n{i_0,\dots,i_9} = \frac{n!}{i_0! \cdots i_9!}$. As above, the sum

$$ \sum_{i_0 + \dots + i_9 = n} = \binom n{i_0,\dots,i_9} c_{i_0,\dots,i_9} $$

is obtained by setting all the variables $x_0 = x_1 = \dots = x_9 = x$ and looking at the coefficient of $x^n$.