This is inspired by an old Putnam problem from 2005, and a solution given by Professor Greg Martin (a Professor of Mathematics at the University of British Columbia, also a user on MO). The question is

Question (Putnam 2005): For non-negative integers $m,n$, let $f(m,n)$ denote the number of $n$-tuples $(x_1, \cdots, x_n)$ of integers such that $|x_1| + \cdots + |x_n| \leq m$. Show that $f(m,n) = f(n,m)$.

Greg's proof essentially boiled down to showing that the generating function $$\displaystyle G(x,y) = \sum_{m,n \geq 0} f(m,n) x^m y^n$$ is symmetric in $x,y$.

Update: Since it seems that MAA took down the Putnam directory and the old solutions are no longer easily accessible, I shall give the proof here. The credit goes entirely to Professor Martin.

We write

$$\displaystyle G(x,y) = \sum_{n \geq 0} \sum_{m \geq 0} f(m,n)x^m y^n$$ $$\displaystyle = \sum_{n \geq 0} \sum_{m \geq 0} x^m y^n \sum_{\substack{k_1, \cdots, k_n \in \mathbb{Z} \\ |k_1| + \cdots + |k_n| \leq m}} 1$$ $$\displaystyle = \sum_{n \geq 0} y^n \sum_{k_1, \cdots, k_n \in \mathbb{Z}} \sum_{m \geq |k_1| + \cdots + |k_n|} x^m$$ $$\displaystyle = \sum_{n \geq 0} y^n \sum_{k_1, \cdots, k_n \in \mathbb{Z}} \frac{x^{|k_1| + \cdots + |k_n|}}{1 - x}$$ $$\displaystyle = \frac{1}{1-x}\sum_{n \geq 0} y^n \left(\sum_{k \in \mathbb{Z}} x^{|k|}\right)^n$$ $$\displaystyle = \frac{1}{1-x} \sum_{n \geq 0} y^n \left(\frac{1+x}{1-x}\right)^n$$ $$\displaystyle = \frac{1}{1-x} \frac{1}{1 - y(1+x)/(1-x)}$$ $$\displaystyle = \frac{1}{1-x-y-xy}.$$

This seemed a fascinating approach to me back then (2005 was the first time I wrote the Putnam, and Greg was our Putnam coach at UBC), and even more so today when I looked back at it given that some of my work involves some clever generating function arguments (based on the answers given to me by Richard Stanley on a question I posted here). So the question I pose is:

Are there any other interesting quantities $f(n_1, \cdots, n_k)$ involving parameters $n_1, \cdots, n_k$ with $k \geq 2$ say that are symmetric in the parameters, and the proof comes from showing that the generating function

$$\displaystyle \sum_{n_1, \cdots, n_k} f(n_1, \cdots, n_k)x_1^{n_1} \cdots x_k^{n_k}$$ is symmetric?

  • 1
    $\begingroup$ I guess you're aware of the number of semistandard Young tableaux of given shape $\lambda$ and weight $\left(n_1,n_2,...,n_k\right)$. $\endgroup$ – darij grinberg Feb 2 '14 at 15:46
  • 1
    $\begingroup$ Any statistics on some set of combinatorial objects which are symmetrically distributed give rise to such a symmetric generating function. Can you give a little more info on how generating functions are used essentially in the proof you are talking about? $\endgroup$ – Sam Hopkins Feb 3 '14 at 4:51
  • 1
    $\begingroup$ Putnam problems back to 1985, and solutions back to 1995, are currently available at kskedlaya.org/putnam-archive $\endgroup$ – Gerry Myerson Jul 25 '14 at 5:22
  • 1
    $\begingroup$ Mahonian statistics for permutations and their generalizations usually enjoy symmetric generating functions. However, you can usually prove these facts via bijections as well. Are you interested then in questions where symmetry is only known to come from a generating function argument? $\endgroup$ – Alex R. Jul 25 '14 at 16:46

This is not exactly what I was looking for, but there is an old result due to Apostol that seems to employ the kind of the kind of generating function trickery that is used above. The following is a proof of the fact that $\zeta(2) = \frac{\pi^2}{6}$ without the use of complex analysis.

First consider the integral

$$\displaystyle I = \int_0^1 \int_0^1 \frac{dx dy}{1- xy}.$$

For $|xy| < 1$ we may expand $\displaystyle \frac{1}{1-xy}$ as $$\displaystyle \frac{1}{1-xy} = \sum_{n \geq 0} (xy)^n.$$ This turns the integral into

$$\displaystyle \int_0^1 \int_0^1 \left(\sum_{n \geq 0} x^n y^n \right)dxdy$$

$$\displaystyle = \sum_{n \geq 0} \int_0^1 y^n \frac{1}{n+1} dy$$ $$\displaystyle = \sum_{n \geq 0} \frac{1}{(n+1)^2} = \sum_{n \geq 1} \frac{1}{n^2}.$$

On the other hand, we may rotate the coordinates by 45 degrees clockwiswe to obtain

$$\displaystyle x = (u-v)/\sqrt{2}, y = (u+v)/\sqrt{2}, 1 - xy = 1 - (u^2 - v^2)/2.$$

By the symmetry of the new region of integration and the integrand, we may decompose the integral into two parts

$$\displaystyle I_1 = 2 \int_0^{\sqrt{2}/2} \left(\int_0^u \frac{2dv}{2 - u^2 - v^2} \right)du$$


$$\displaystyle I_2 = 2 \int_{\sqrt{2}/2}^{\sqrt{2}} \left(\int_{0}^{\sqrt{2}-u}\frac{2dv}{2 - u^2 - v^2} \right)du.$$

We first evaluate $I_1$. Using the usual integration technique involving arctan, we obtain

$$\displaystyle I_1 = 4 \int_0^{\sqrt{2}/2} \frac{1}{\sqrt{2 - u^2}} \arctan \left(\frac{u}{\sqrt{2-u^2}} \right)du.$$

Make the substitution $u = \sqrt{2} \sin \theta$ we obtain

$$\displaystyle I_1 = 4 \int_0^{\pi/6} \frac{1}{\sqrt{2} \cos \theta} \arctan\left(\frac{\sqrt{2}\sin \theta}{\sqrt{2} \cos \theta} \right) \sqrt{2} \cos \theta d \theta$$ $$\displaystyle = 4 \int_0^{\pi/6} \theta d \theta = \frac{\pi^2}{18}.$$

Similarly, we obtain that

$$\displaystyle I_2 = \int_{\sqrt{2}/2}^{\sqrt{2}} \frac{1}{\sqrt{2 - u^2}}\arctan\left(\frac{\sqrt{2} - u}{\sqrt{2 - u^2}}\right)du.$$

In this case, we use the substitution $u = \sqrt{2} \cos 2\theta$, the choice of which will be clear soon. Continuing, we have

$$\displaystyle I_2 = 4 \int_{\pi/6}^0 \frac{1}{\sqrt{2} \sin 2\theta} \arctan \left(\frac{\sqrt{2} - \sqrt{2}\cos 2 \theta}{\sqrt{2 - 2 \cos^2 2 \theta}}\right)(-2\sqrt{2}) \sin 2\theta d\theta$$ $$\displaystyle = 8 \int_0^{\pi/6} \arctan\left( \frac{\sqrt{2}(1 - \cos 2\theta)}{\sqrt{2}\sin 2 \theta}\right)d\theta$$ $$\displaystyle = 8 \int_0^{\pi/6} \arctan\left(\frac{2\sqrt{2}\sin^2 \theta}{2\sqrt{2}\sin \theta \cos \theta}\right) d\theta$$ $$\displaystyle = 8 \int_0^{\pi/6} \theta d\theta = \frac{\pi^2}{9}.$$

Then we have $I = I_1 + I_2 = \displaystyle \frac{\pi^2}{18} + \frac{\pi^2}{9} = \frac{\pi^2}{6}.$


The following isn't an example of showing directly that the coefficients are symmetric but, establishing that the generating function is symmetric is instrumental in the calculation of an auxiliary quantity involved.

I think an amazing example of this kind of proof is Stanley's proof for the number of reduced decompositions of the long permutation. Specifically because a bijective proof of this fact (such as Edelman and Greene's) is considerably harder to establish. Moreover, this proof uses what seems like a minimal amount of knowledge about reduced decompositions (again compared to the bijective proof). What follows is a very rough outline of the proof. See "On the Number of Reduced Decompositions of Elements of Coxeter Groups - Stanley" for details.

Setup: Let $S_n$ be the symmetric group and $s_i:=(i,i+1)$ be an adjacent transposition. For any permutation $w$, write $w=s_{a_1}s_{a_2}\cdots s_{a_p}$, where $p$ is equal to the length of $w$ (the number of inversions in $w$). Call this sequence $(a_1,\cdots,a_p)$ a reduced decomposition of $w$, and denote by $\mbox{Red}(w)$ the set of all reduced decompositions of $w$. Let $w_0:=(n,n-1,\cdots,1)$ be the long permutation (the one with the most inversions in $S_n$, so $p=\binom{n}{2}$). For example, in $S_3$, if $w=321$, then


so $|\mbox{Red}(w)|=2$.

Let $\lambda:=\lambda(n)$ be a tableau shape $(n-1,n-2\cdots,1)$ (a staircase tableau) and $f_\lambda$ to be the number of Standard Young tableau of shape $\lambda$.

Theorem (Stanley): $|\mbox{Red}(w_0)|=f_\lambda$

Sketch of Proof:

The key idea is to define the so called Stanley Symmetric function (the umbrella term for these is Gessel quasisymmetric functions). For any $w\in S_n$, again let $p$ be the length of $w$. Then define

$$F_w(x_1,\cdots,x_p)=\sum_{(a_1,\cdots,a_p)\in \mbox{Red}(w)}\sum_{\substack{1\leq k_1\leq k_2\cdots\leq k_p\\ k_i<k_{i+1} \ \mbox{if } a_i<a_{i+1}}}x_{k_1}x_{k_2}\cdots x_{k_p}.$$

An immediate observation is that the coefficeint $x_1\cdots x_p$ occurs exactly once for each reduced decomposition of $w$. Thus we're interested in calculating $[x_1\cdots x_p]F_w(x_1,\cdots, x_p)$.

Key Theorem: $F_w(x_1,\cdots,x_p)$ is symmetric in $x_i$'s.

The original proof of this theorem is purely constructive and relies on the fact that adjacent transpositions form a Coxeter group, along with a number of facts of how one can, in a sense, decompose a permutation $w$ uniquely into an increasing product of adjacent transpositions.

Assuming the above theorem for a moment, we can expand $F_w$ in terms of Schur polynomials as:

$$F_w(x_1,\cdots,x_p)=\sum_{\lambda \vdash p}\alpha_{\lambda p}s_\lambda(x_1,\cdots,x_p),$$

where one can further show that $\alpha_{p\lambda}$ are nonnegative integers. Since $[x_1\cdots x_p]s_\lambda(x_1,\cdots,x_p)=f_\lambda$, we get:

$$|\mbox{Red}(w)|=\sum_{\lambda \vdash p}\alpha_{p\lambda}f_\lambda.$$

The final step is to show that when $w=w_0$ is the long permutation, that everything in the sum vanishes except for the staircase partition $(n-1,n-2,\cdots,1)$ and that the corresponding $\alpha$ for this partition is simply 1. This is done by showing that this particular staircase partition encodes the inversion structure of the long permutation $w_0$. Specifically, the only partitions that survive in the above sum are intimately related to the patterns that occur in the corresponding permutation. As well, the $\alpha$'s are also connected in this way. There are still some details left but the proof follows through.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.