Partial Sums of Generating Function Coefficients

Now that I've begun to blog a little Mathematics, I suddenly find it difficult hold myself from not blogging. I started digging my amateurish works in mathematics and I found some worth blogging. Lemme start with one on the Exponential Generating Functions.

Well, Generating functions are ubiquitous in Mathematics. There are many forms of generating functions available at a mathematician's arsenal depending on which area of mathematics he's working. If I have to give my favorites, I would go for the Ordinary generating functions (OGFs) and the Exponential generating functions (EGFs) mostly because of their versatility in Combinatorics. Apart from these two, I find Dirichlet's generating functions (DGFs) and Lambert's generating functions (LGFs) of Number theory fascinating.

The idea of this post nothing innovative or original but began when I noticed something in the OGFs and wondered how to do the same for EGFs. Let's move on to that 'something'...

The Ordinary generating function of a sequence $a_n$ is $G(a_n;x)=f(x)=\sum_{n=0}^{\infty} a_n x^n$.
Therefore, we find $[x^n]f(x)=a_n$.

Let's define a new sequence, $b_n=\sum_{r=0}^na_r$. Let's denote the OFG of this new sequence by $G(b_n;x)=g(x)$. How would one find $g(x)$ given $f(x)$?

$\begin{align}
g(x)&=b_0+b_1x+b_2x^2+\cdots\\
&=a_0+(a_0+a_1)x+(a_0+a_1+a_2)x^2+\cdots\\
&=(a_0+a_1x+a_2x^2+\cdots)+(a_0+a_1x+a_2x^2+\cdots)x+(a_0+a_1x+a_2x^2+\cdots)x^2+\cdots\\
\end{align}$

Recognizing $a_0+a_1x+a_2x^2+\cdots$ as the OGF of $f(x)$, we get
$\begin{align}
g(x)&=f(x)+xf(x)+x^2f(x)+\cdots\\
&=(1+x+x^2+\cdots)f(x)\\
&=\frac{f(x)}{1-x}
\end{align}$

Hence $g(x)$, whose OGF coefficients are the sums of $f$'s OGF coefficients, can be found by simply diving $f(x)$ by $1-x$. Let's apply it in an example..

$x(1-x)^{-2}=x+2x^2+3x^3+\cdots=\sum_{n=0}^{\infty}nx^n$, and
$x(1-x)^{-3}=\binom{2}{2}x+\binom{3}{2}x^2+\binom{4}{2}x^3=\sum_{n=0}^{\infty}\binom{n+1}{2}x^n$ which is indeed true.

In short, $\displaystyle\sum_{r=0}^n[x^r]f(x)=[x^n](\frac{f(x)}{1-x})$.

Many would have known of this result. There's absolutely nothing new about it and any material you find on the internet would give you this one. But the question that led me to this post is how would this 'translate' to the EGFs?

Let $ f = \sum_{i=0}^\infty a_i \dfrac{x^i}{i!}$
Then $D^k f = \sum_{i=k}^\infty a_i \dfrac{x^i}{i!}$ where $D \equiv \dfrac{d}{dx}$

Summing for all $k \geq 0$,
$f + Df + D^2f + D^3f + ... = \sum_{i=0}^\infty a_i^{\infty} \dfrac{x^i}{i!}$ where $a_n^\infty = \sum_{j=n}^\infty a_j$

Denoting the RHS by $y$, we can write the above as,
$(1-D)^{-1}f=y$ (ie) $(1-D)y=f$

Solving it with Mathematica gives,
$y(x)= c e^x - e^x\int e^{-x}f(x)dx$ (c being an arbitrary constant)

Hence $y$, whose EGF coefficients are the partial sums of $f's$ EGF coefficients, has an integral expression of the above form.

Unlike the OGF version, we have
$\sum_{r=0}^nr![x^r]f(x)=a_0+a_1+a_2+\cdots+a_n=a_0^{\infty}-a_{n+1}^{\infty}=0![x^0]y(x)-(n+1)![x^{n+1}]y(x)$

In light of the above formulae, we can just set $c$ to be $0$ in the expression for $y$. That is we can re-write the formulae as,

$y(x)= -e^x\int e^{-x}f(x)dx$

In my opinion, this formulae is more subtle than the one we saw for the OGFs and is not at all obvious at first sight. Let's see what the formula gives for some functions..

$xe^x=1.\dfrac{x}{1!}+2.\dfrac{x^2}{2!}+3.\dfrac{x^3}{3!}+\cdots=\sum_{n=0}^{\infty}n \dfrac{x^n}{n!}$

$\sum_{r=0}^nr![x^r]xe^x=1+2+3+\cdots+n$

Using the formulae above, $y(x)=-e^x\int e^{-x}xe^xdx=-e^x\int xdx=\dfrac{-x^2e^x}{2}=-\dfrac{x^2}{2}-\dfrac{x^3}{2.1!}-\dfrac{x^4}{2.2!}-\cdots$

It is also easy to note that, $n![x^n]\dfrac{-x^2e^x}{2}=-\dbinom{n}{2}$

Hence,$0![x^0]\dfrac{-x^2e^x}{2}-(n+1)![x^{n+1}]\dfrac{-x^2e^x}{2}=-\dbinom{0}{2}+\dbinom{n+1}{2}=\dbinom{n+1}{2}$ as expected.

Though these results produce compact expressions for the partial sums, we have to note that they do not always give closed form solutions. For example, one may be tempted to use EGF of $(1-x)^{-1}$ to find a formulae for sum of the first $n$ factorials. But soon we find that the resulting integral in the formula above is not that easy to evaluate to give a close from solution. Nevertheless, these expressions come in handy at situations unexpected and as such would prove to surprisingly useful.

As always, I've enjoyed blogging and the joy has only doubled when it is about Mathematics. Hope you did not feel that you've wasted your time. I'll try to keep blogging at my present pace and see ya soon.


Until then
Yours Aye,
Me

Pólya's Enumeration Theorem with Applications - Part I

Hi All, its been a long time again and I thought I would not be blogging again anytime soon. But recently, I came across what can arguably called one of the most powerful and beautiful theorem in Combinatorics, The Pólya Enumeration Theorem. When I started reading about it and applied it to solve certain enumeration problems I just couldn't stop but wonder this marvelously simple theorem. Maybe, had Gauss discovered it he would have called it 'The Remarkable Theorem in Combinatorics'.

Pólya's Enumeration Theorem's usefulness comes from its ability to solve a great many variety of counting problems which would otherwise be too hard to solve or would require a customized approach that give you insights for that particular problem but cannot be generalized to very many other class of problems. The theorem uses the fundamental concepts of Group Theory, especially the permutation groups.

After surfing through a lot of material in the web to clearly understand the theorem I stumbled upon the PDF titled 'Counting and Coloring with Symmetry - A presentation of Pólya's Enumeration Theorem with Applications' by Amanda Noel Bjorge. This PDF was easy to follow because it explains every step of all the proofs with examples which makes it easier for the reader to follow. Of course, you've got to have some understanding of basic group theory and this PDF takes it from there. Yet another material I found very useful is Polya's Counting theory by Mollee Huisinga.

Now one may ask, If I have this PDF what is the point in creating a post about the same theorem? After all am an amateur and what more could I possibly add to an already well written thesis? Well, most of all the files available on the internet seems to explain the theorem in a more academic way. What I intend to do is to present the theorem to myself and maybe, add a few things which a casual google search may not reveal. So I suggest one should first read the file above for it will make following this post a lot easier and interesting.

To start with, I assume you've developed an understanding about the permutation groups and their corresponding pattern index. In particular, the cycle index formula for the Symmetric group is extremely interesting and required a bit of thought before I completely understood it. The four basic permutation groups that appear frequently in counting problems are the Symmetric group, the Alternating group, the Cyclic group and  the Dihedral group. Of these, the most easiest to understand are the last two. Mainly because they have a geometric description and can be visualized as placing beads or balls in a regular n-gon.

So when the question is about n-bead necklace discounting rotational symmetries, you understand that the answer has to do with Cyclic group and when it is about discounting both rotational and reflectional symmetries, you use the dihedral group.

To begin with, let's look at a simple example:

Example 1: How many 4-bead necklaces can formed with $m$ different colored beads discounting rotational symmetries?

Strictly speaking (or blogging), we don't need Pólya's Enumeration Theorem to find this. Burnside's Lemma will suffice. To solve this we first need the cycle index of the Cyclic group of degree 4, conventionally denoted as $Z_{C_4}$.

$Z_{C_4}(x_1,x_2,x_3,x_4)=\frac{1}{4}(x_1^4+x_2^2+2x_4)$

We substitute $m$ for all $x_i$'s, which gives us, $Z_{C_4}(m,m,m,m)=\frac{1}{4}(m^4+m^2+2m)$

Say you have three different colored beads, substitute $m =3$ in the above expression and you will have  $Z_{C_4}(3,3,3,3)=24$

Example 2: But what if I have one White bead, one Black bead and two Red beads and I want the number of 4-bead necklaces discounting rotational symmetries?

Here's where Pólya comes to the rescue. Plainly, the theorem says let $x_i=W^i+B^i+R^i$ and the coefficient of $WBR^2$ will give you the required answer. With a little help from Mathematica, we find

$Z_{C_4}(W+B+R, W^2+B^2+R^2, W^3+B^3+R^3, W^4+B^4+R^4)=B^4 + B^3 R + 2 B^2 R^2 + B R^3 + R^4 + B^3 W + 3 B^2 R W +$
$3 B R^2 W + R^3 W + 2 B^2 W^2 + 3 B R W^2 + 2 R^2 W^2 + B W^3 +
 R W^3 + W^4$

Hence you can form $3$ 4-bead necklaces with the above restrictions. Though the theorem doesn't show how these three necklaces will be, with little thought we find them to be brww, bwrw and rbww. Note that the first and third arrangements are different as you cannot transform one into the other using rotations.

The same logic applies to the Dihedral group as well. Just find the cycle index of the Dihedral group and follow the same procedure.

But what of the Symmetric and Alternating groups? We visualized the Cyclic and Dihedral groups with n-gons and applied them to n-bead necklaces. Well, I cannot find an equivalent way for visualizing the Symmetric and Alternating groups. But as for application, we can use the Symmetric groups in n-ball Urns. Both these groups helps us in solving urn problems where order doesn't matter.

Example 3: Say if we have 4 Urns and balls of $m$ different colors. In how many ways can you put one ball in each urn?

Now if the order matters, then this is one the most elementary questions in Combinatorics. Each urn has $m$ choices. Hence the answer is $m^4$. But the Symmetric group doesn't take order into account. So Let's see what Burnside's Lemma gives. We first need $Z_{S_4}$.

$Z_{S_4}(x_1,x_2,x_3,x_4)=\frac{1}{24}(x_1^4+6x_1^2x_2+3x_2^2+8x_1x_3+6x_4)$

One could easily see that $Z_{S_4}(m,m,m,m)=(m^4+6m^3+11m^2+6m)/24$. For $m=3$, this gives $Z_{S_4}(3,3,3,3)=15$

Let's finish applying the Pólya's Enumeration theorem with three colors - White, Black and Red.

$Z_{S_4}(W+B+R, W^2+B^2+R^2, W^3+B^3+R^3, W^4+B^4+R^4)=B^4 + B^3 R + B^2 R^2 + B R^3 + R^4 + B^3 W + B^2 R W +$
$B R^2 W +R^3 W + B^2 W^2 + B R W^2 + R^2 W^2 + B W^3 + R W^3 + W^4$

These are the 15 combinations that we got from Burnside's Lemma. Note that bbbr and brbb are different when you take order into account whereas they are counted as same when order doesn't matter.

Now you maybe tempted to disregard Symmetric groups as uninteresting in Pólya's Enumeration theorem. But they come in a remarkable fashion when we try to understand the Alternating groups. The 'definition' of Alternating groups, which am about to give, is one of the high points of this discussion. In fact, I cannot find any material in the internet which clearly spells this application.

Example 4: Let's take same 4-urn problem. But now we want is the number of ways you can put one ball in each urn such that no urns have balls of the same color?

Clearly, if you have 4 urns and only three different colored balls, you cannot do it. But if you have 4 different colored balls, you can do it in 1 way. In fact, the answer to the question is too simple. Its $\binom{m}{4}$ when you have $m$ different colored balls. Let's see whether Burnside's Lemma gives the same answer. But first we need the cycle index. But of what? The Alternating group? The Symmetric group? No. Its the difference between the cycle index of the Alternating group and the Symmetric group.

Equation (14) of the PDF gives a succinct way of calculating this.

$Z_{A_n}-Z_{S_n}=Z_{S_n}(x_1,-x_2,x_3,-x_4,...)$, which we will denote by $Z_{-S_n}(x_1,x_2,x_3,x_4,...)$ for convenience. Hence we see that the Alternating group comes in a disguised form to solve a special class of constraint namely 'no two are alike'.

$Z_{A_4}-Z_{S_4}(x_1,x_2,x_3,x_4)=Z_{S_4}(x_1,-x_2,x_3,-x_4)=Z_{-S_4}(x_1,x_2,x_3,x_4)=\frac{1}{24}(x_1^4-6x_1^2x_2+3x_2^2+8x_1x_3-6x_4)$

So in case of $m$ colors, we have $Z_{S_4}(m,-m,m,-m)=Z_{-S_4}(m,m,m,m)=(m^4-6m^3+11m^2-6m)/24=\binom{m}{4}$

Note that $Z_{-S_4}(m,m,m,m)=0$ for $m<4$.

Pólya's Enumeration Theorem for the same gives,

$Z_{-S_4}(x_1,x_2,x_3,x_4)=B G R W + B G R Y + B G W Y + B R W Y + G R W Y$, where $x_i=W^i+B^i+R^i+G^i+Y^i$.

We have used five colors for this example because using anything less than four colors will only give us $0$.

Frankly, we don't see very good use of the last example as a source of solving problems. But I see the power of Symmetric and Alternating polynomials are apparent when we start using compositions of the permutation groups. See Example 6.1 and Figure 8 in the PDF to see what I mean.

The same problem also gives us further scope to understand our notion of the Alternating group. In the said Example the author has used the Symmetric group because he was looking for the number of arrangements of 2 necklaces without regard to order. Hence the three arrangements are {bbbb, wwbb}, {bbbb, wbwb}, and {bwbb, bwbb}. The third arrangement repeats the same necklace twice. But what if we only want the arrangements where no two necklaces are alike. Here we would be using our idea of Alternating group along with the Symmetric group.

Using $Z_{-S_2}$ and $Z_{C_4}$ we get,

$Z_{-S_2[C_4]}(W+B,...,W^8+B^8)=B^7 W + 2 B^6 W^2 + 3 B^5 W^3 + 3 B^4 W^4 + 3 B^3 W^5 + 2 B^2 W^6 + B W^7$

Now we see that, of the 15 arrangements of 2 necklaces each with 4 beads, there are 2 with a total combination of 6 black beads and 2 white beads such that the two necklaces are different from each other.

To sum up the permuatation groups, we give the following:

• Cyclic group: Discounts rotational symmetry.
• Dihedral group: Discounts rotational and relfectional symmetry.
• Symmetric group: Arrangements not taking order into account.
• Alternating group: Arrangements not taking order into account and no two patterns are alike.

We'll continue with the other applications of the theorem in this post. Write ya later.



Until then
Yours Aye
Me