Find the generator function

Question

Using the alphabet $\Sigma = \{0,1,2,3,4,5,6,7,8,9\}$ , we want to form -digit strings allowing infinite repetition of digits but asking for at least one occurrence of the digit 0 (in any position).

1. Calculate the number of numbers that can be formed, with combinatorial arguments.
2. Formulate the corresponding generating function in the specific measurement and report the coefficient where the result is.

So far I found that the total number of numbers that can be formed in total is $10^n$ minus the total numbers that can be formed without the 0 are $9^n$. So the answer to the first question is $10^n - 9^n$. But for the second question, I have no clue.

Answer 1

Actually it is pretty simple, for

• $n=2$ , $10^2 -9^2$

• $n=5$ , $10^5 -9^5$ etc.

So, for any $n$ value, find the coefficient of $x^n$ in the expansion of $$\frac{1}{1-10x}-\frac{1}{1-9x}$$ $$(1+10^1x+10^2x^2+10^3x^3+...+10^nx^n+.. )-(1+9x+9^2x^2+9^3x^3+...+9^nx^n+...)$$

$$\frac{x}{90x^2-19x+1}$$

Answer 2

My answer uses exponential generating functions (e.g.f.'s), and the following lemma:

Product formula for exponential generating functions: Suppose that there are $a_n$ ways to put an $A$-structure on a set of size $n$ ($n\ge 0$). Similarly, there are $b_n$ ways to put a $B$-structure on an $n$-element set. Let $c_n$ be the number of ways to partition a set of size $n$ into two labeled parts, then put an $A$-structure on the first part, and a $B$-structure on the second part. If $A(x)$ is the e.g.f. for the sequence $(a_n)_{n\ge 0}$, and similarly $B(x)$ for $(b_n)_{n\ge 0}$ and $C(x)$ for $(c_n)_{n\ge 0}$, then $$C(x)=A(x)\times B(x).$$

For your problem, we will multiply ten e.g.f.'s together, one for each digit. Note that choosing an $n$-digit string is equivalent to partitioning the set of $n$ digit places into $10$ labeled parts. We do not put a structure on each part; rather, there is exactly one way to place a structure on each part, in that we must fill the chosen spots with that digit.

To summarize, let $F_k(x)$ be the e.g.f. for the $k^\text{th}$ digit. That is, $$ F_k(x)=\sum_{n\ge 0} \text{# (ways fill $n$ chosen spots with digit $k$)}\frac{x^n}{n!} $$This means the generating function for the digits $1$ through $9$ is $$ F_1(x)=\dots=F_9(x)=\sum_{n\ge 0}1\cdot \frac{x^n}{n!}=e^x $$ However, the e.g.f. for $0$ is slightly different. Since there must be at least one zero, there are $0$ ways to put a structure on a set of size $0$. That is, we must sum over only $n\ge 1$, and we get $$ F_0(x)=\sum_{n\ge 1}\frac{x^n}{n!}=e^x-1 $$ Using the product formula, the generating function for the number of $n$-digit decimal strings is $$ \prod_{i=0}^9 F_i(x)=e^{9x}(e^x-1)=e^{10x}-e^{9x} $$ Finally, the number of $n$-digit strings is $n!$ times the coefficient of $x^n$ in the above, which is $n!\cdot (\frac{10^n}{n!}-\frac{9^n}{n!})=10^n-9^n$.