Finding Gemstones: on the quest for mathematical beauty and truth
< Previous Post Next Post >

What is a q-analog? (Part 2)

This is a continuation of Part 1 of this series of posts on q-analogs.

Counting by q’s

Another important area in which q-analogs come up is in combinatorics. In this context, q is a formal variable, and the q-analog is a generating function in q, but viewed in a different light than usual generating functions. We think of the q-analog of as ``q-counting’’ a set of weighted objects, where the weights are given by powers of q.

Say you’re trying to count permutations of 1,,n, that is, ways of rearranging the numbers 1,,n in a row. There are n ways to choose the first number, and once we choose that there are n1 remaining choices for the second, then n2 for the third, and so on. So there are n!=n(n1)21 ways to rearrange the entries. For instance, the 3!=6 permutations of 1,2,3 are 123, 132, 213, 231, 312, 321.

Now, say we weight the permutations according to how ``mixed up’’ they are, in the sense of how many pairs of numbers are out of order. An inversion is a pair of entries in the permutation in which the bigger number is to the left of the smaller, and inv(π) denotes the number of inversions of the permutation π. The table below shows the permutations of 3 along with the number of inversions they contain.

pinv(p)qinv(p)123011321q2131q2312q23122q23213q3

We weight each permutation p by qinv(p), and q-count by summing these q-powers, to form the sum pSnqinv(p) where Sn is the set of all permutations of 1,,n. So for n=3, the sum is 1+2q+2q2+q3 by our table above.

We now come to an important philosophical distinction between q-analogs and generating functions. As a generating function, the sum 1+2q+2q2+q3 is thought of in terms of the sequence of coefficients, 1,2,2,1. Generatingfunctionologically, we might instead write the sum as i=0ciqi where ci is the number of permutations of length n with i inversions. But in q-analog notation, pSnqinv(p), we understand that it is not the coefficients but rather the exponents of our summation that we are interested in..

In general, a combinatorial q-analog can be defined as a summation of q-powers qstat(p) where p ranges over a certain set of combinatorial objects and stat is a statistic on these objects. Recall that we defined an ``interesting q-analog’’ of an expression P to be an expression Pq such that

  1. Setting q=1 or taking the limit as q1 results in P,
  2. Pq can be expressed in terms of (possibly infinite) sums or products of rational functions of q over some field,
  3. Pq gives us more refined information about something that P describes, and
  4. Pq has P-like properties.

Certainly setting q=1 in a combinatorial q-analog results in the total number of objects, and the q-analog gives us more information about the objects than just their total number. It’s also a polynomial in q, so it satisfies properties 1, 2, and 3 above. Let’s now see how our q-analog pSnqinv(p), which is a q-analog of n!, also satisfies property 4.

Notice that 1+2q+2q2+q3 factors as (1)(1+q)(1+q+q2). Indeed, in general this turns out to be the same q-factorial we saw in the last post! That is, pSnqinv(p)=(1)(1+q)(1+q+q2)(1+q++qn)=(n)q!. So it satisfies property 4 by exhibiting a product formula like n! itself. I posted a proof of this fact in this post, but let’s instead prove it by building up the theory of q-counting from the ground up.

The multiplication principle in combinatorics is the basic fact that the number of ways of choosing one thing from a set of m things and another from a set of n things is the product mn. But what if the things are weighted?

q-Multiplication Principle: Given two weighted sets A and B with q-counts M(q) and N(q), the q-count of the ways of choosing one element from A and another from B is the product M(q)N(q), where the weight of a pair is the sum of the weights of the elements.

Let’s see how this plays out in the case of (n)q!. If each entry in the permutation is weighted by the number of inversions it forms with smaller entries (to its right), then the first entry can be any of 1,2,,n, which contributes a factor of 1+q+q2++qn1 to the total. The next entry then can be any of the n1 remaining entries, and since the first entry cannot be the smaller entry of an inversion with the second, this choice contributes a factor of 1+q+q2++qn2 to the total by the same argument. Continuing in this fashion we get the q-factorial as our q-count.

Notice that even the proof was a q-analog of the proof that n! is the number of permutations of 1,,n, now that we have the q-Multiplication Principle.

That’s all for now! In the next post we’ll talk about how to use the q-Multiplication Principle to derive a combinatorial interpretation of the q-binomial coefficient, and discuss q-Catalan numbers and other fun q-analogs. Stay tuned!