This post continues the series on Generating Functions. The first installment was discussing the problem about changing dollar into coins. The second post was about degeneracy of energy levels in central field in quantum mechanics. The connection between previous and current problems is not too difficult to see yet the method of generating functions applied to counting “lucky numbers” has its own interesting twist.

Generating Functions: Part 3. Lucky Tickets.

Here we discuss another elementary problem about counting, which can be solved with a clever choice of generating function.

Lucky Tickets

Section 9 in [1] contains a series of problems on generating functions. The example 9.2 problem is worth discussion in connection to the previous post. It is related to so called “lucky tickets” in a roll of all tickets numbered with $2n$ digits so for example $n=3$ their numbers are running from 000000 to 999999. Obviously, there are $N=10^{2n}$ tickets in the roll.

Definition. Ticket in a $2n$ -digits tickets roll is called lucky if the sum of first $n$ digits equals the sum of last $n$ digits.

Problem 2. Find number $L$ of lucky tickets in complete $2n$ -digits roll for $n = 3$ .

First step would be to find how many ways there are to have sum of first 3 digits equal $s \in \{0,1, . . ., 27\}$ . This can be achieved with the aid of generating function:

(1) $F(x)=(1+x+x^2+ . . . + x^9)^3$

$=\frac{(1-x^{10})^3}{(1-x)^3}$

Its coefficients in the expansion

(2) $F(x)=\sum_{s=0}^{27}A_s x^s$

would give number of combinations we are interested for each possible sum value $s$ . However we are not interested in the individual values of $s$ but rather in the cases when two sums of digits are equal regardless of the particular value of the sum.

For that end, we consider different generating function for the last three digits:

(3) $F(x^{-1})=(1+x^{-1}+x^{-2}+ . . . + x^{-9})^3$

$=\frac{(1-x^{-10})^3}{(1-x^{-1})^3}$

which achieves the same as (1) except it does it with negative powers of $x$ . Now observe what happens in the product:

(4) $G(x)=F(x^{-1})F(x)$ $=\frac{(1-x^{10})^6}{x^{27}(1-x)^6}$

It is easy to see that only the terms with opposite powers of $x$ will contribute to the term $B_0$ in expansion

(5) $G(x)=\sum_{s=-27}^{27}B_s x^s$

The key is that the terms corresponding to the opposite powers of $s$ are exactly corresponding to the number of ways we can get sum $s$ on either first or last three digits. Hence the solution to the problem 2 can be found by calculating $B_0$ in (2).

That can be achieved by applying formulas for binomial expansion

(6) $(1-x^{10})^6 = 1-C^1_6x^{10}+C^2_6x^{20}-C^3_6x^{30}+C^4_6x^{40}-C^5_6x^{50}+x^{60}$

and:

(7) $(1-x)^{-6}$ $=\sum_{s=0}^{\infty}C_{5+s}^5 x^s$

which comes from general formula for negative exponents (see (2) in the previous post on generating functions).

From (6) and (7) we are interested in terms that have combined power 27, which would cancel with $x^{27}$ in denominator of (5). It is easy to find such combinations:

(8) $L=C_{32}^5-C_{22}^5C_{6}^1+C_{12}^5C^2_6 = 55252$

That gives probability of getting lucky ticket about 5.5%. A funny detail is that in Russia you are supposed to eat lucky ticket to make it bring luck to you

References

[1] A.A.Sveshnikov “Problems in Probability Theory, Mathematical Statistics and Theory of Random Functions“, Dover, 1979, 481 pages.

3DMatics