Worked example C: bivariate generating functions and digit sums Ordinary generating functions are not limited to representing sequences that depend only on a single parameter. More parameters are possible, e.g. two parameters. It is also possible to mix types of generating functions, as in bivariate probability generating functions, where an ordinary generating function generates an exponential one. These types of generating functions are often referred to as super generating functions. Here we show an example of how to work with bivariate generating functions. Let n be a natural number and consider the integers from 0 to 102n − 1, where those integers that have fewer than 2n digits are padded with zeros on the left, so that all of them may be considered to have 2n digits. E.g. for n = 3 the range goes from 000000 to 999999. We will use bivariate generating functions to answer the following question: what is the sum of those integers in [0,102n − 1] whose first n digits sum to the same value as the last n digits, i.e. the digit sum of the first half is equal to the digit sum of the second half. (The term digital sum is also used for digit sums.) We call these integers balanced. E.g. the integer 124511 would contribute to the sum for n = 3, because 1+2+4=7=5+1+1. The value that it would contribute is simply 124511. It is certainly impossible to compute this sum by direct enumeration for large n (take n = 20, for example).

We let En denote the desired sum, and introduce gn,k, which gives the number of integers n digits long (left-padding with zeros as before to obtain 10n values) whose digits sum to k, and sn,k, which is the sum of the integers n digits long whose digits sum to k. The key observation is to note that

To see this, fix k, the digit sum, and consider the set of balanced integers of length 2n, the digit sum of the first and second half of which is k. This set of integers is created by pairing any integer of length n and digit sum k with any other, so any particular value occurs gn,k times in the first half (multiplied by 10n), and gn,k times in the second half. Adding all of these integers yields sn,k. The number of summands that contribute to En is given by

Copyright © 2006 egfh.com                    Powered by Engineer Partner The One Stop Outsource