An application of Bivariate Ordinary Generating functions

It's interesting to note how each type of Generating function has its own advantages and disadvantages. For example, we saw how, given an OGF or an EGF, partial sums are readily available with certain simple manipulations. But in case of DGFs, we had to rely on Dirichlet's Hyperbola method to evaluate the partial sums.

On the other hand, if you are able to calculate the number of numbers satisfying a 'property' via DGF, then it's not too hard to also calculate the sum of numbers satisfying the same 'property' with a simple change in the DGF. However, it is not the case with OGFs.

Consider the question of finding the number of numbers with atmost $n$ digits whose digit-sum is $k$. We can easily construct its OGF as follows.

$f(x) = (1+x+x^2+\cdots+x^9)^n$

The above expression simply says that each digit can take any value from 0 to 9. Expand $f(x)$ and the coefficient of $[x^k]$ will give you the required answer.

Here we consider the question of finding the sum of numbers with atomst $n$ digits with a digit-sum of $k$. I'm not saying that this cannot be done with an one-variable OGF, but certainly using a bivariate OGF makes things simpler. In addition to noting how much each digit adds to the sum, we must also make a note of each of the digit with its place value. We define some functions as follows:

$f_n(x,y) = 1+xy^{10^{n-1}}+x^2y^{2.10^{n-1}}+\cdots+x^9y^{9.10^{n-1}}$

Each function $f_n(x,y)$ encodes the information about the $n$th digit, making a note of what it adds to the digit sum and digit with its place value. Defining a new function

$f(x,y)=f_1(x,y).f_2(x,y)\cdots.f_n(x,y)$

gives what we need. Differentiating the above generating function w.r.t $y$ and substituting $y=1$ (If you wanna know what this does, refer 'Multivariate Generating Functions' in 'Analytic Combinatorics'), tells us how much each digit contributes to the overall 'sum of numbers with atmost $n$ digits'. . We now let,

$g(x)=\dfrac{d}{dy}f(x,y)\biggl\vert_{y=1}$

This Generating function we are left with is a single variable OGF in which the coefficient of $x^k$ gives the sum of numbers whose digit-sum is $k$. Play around with numbers with certain other 'properties' and you will really see what this post is trying to convey.

I think my next post will be on Multiset Cycle Indices, though am not sure where and/or how to start. C ya then.



Until then
Yours Aye,
Me