Putnam 2005, Problem B-4

For positive integers $m$ and $n$, let $f(m,n)$ denote the number of $n$-tuples $(x_1, x_2, \ldots, x_n)$ of integers such that $|x_1| + |x_2| + \cdots + |x_n| \leq m$. Show that $f(m,n) = f(n,m)$.

Solution:
First solution: Define \(f(m,n,k)\) as the number of \(n\)-tuples \((x_1,x_2,\ldots,x_n)\) of integers such that \(|x_1| + \cdots + |x_n| \leq m\) and exactly \(k\) of \(x_1,\ldots,x_n\) are nonzero. To choose such a tuple, we may choose the \(k\) nonzero positions, the signs of those \(k\) numbers, and then an ordered \(k\)-tuple of positive integers with sum \(\leq m\). There are \(\binom{n}{k}\) options for the first choice, and \(2^k\) for the second. As for the third, we have \(\binom{m}{k}\) options by a "stars and bars" argument: depict the \(k\)-tuple by drawing a number of stars for each term, separated by bars, and adding stars at the end to get a total of \(m\) stars. Then each tuple corresponds to placing \(k\) bars, each in a different position behind one of the \(m\) fixed stars. We conclude that
\[
f(m,n,k) = 2^k \binom{m}{k} \binom{n}{k} = f(n,m,k);
\]
summing over \(k\) gives \(f(m,n) = f(n,m)\). (One may also extract easily a bijective interpretation of the equality.)

Second solution: (by Greg Kuperberg) It will be convenient to extend the definition of \(f(m,n)\) to \(m,n \geq 0\), in which case we have \(f(0,m) = f(n,0) = 1\).

Let \(S_{m,n}\) be the set of \(n\)-tuples \((x_1,\ldots,x_n)\) of integers such that \(|x_1| + \cdots + |x_n| \leq m\). Then elements of \(S_{m,n}\) can be classified into three types. Tuples with \(|x_1| + \cdots + |x_n| < m\) also belong to \(S_{m-1,n}\). Tuples with \(|x_1| + \cdots + |x_n| = m\) and \(x_n \geq 0\) correspond to elements of \(S_{m,n-1}\) by dropping \(x_n\). Tuples with \(|x_1| + \cdots + |x_n| = m\) and \(x_n < 0\) correspond to elements of \(S_{m-1,n-1}\) by dropping \(x_n\). It follows that
\[
f(m,n) = f(m - 1,n) + f(m,n - 1) + f(m - 1,n - 1),
\]
so \(f\) satisfies a symmetric recurrence with symmetric boundary conditions \(f(0,m) = f(n,0) = 1\). Hence \(f\) is symmetric.

Third solution: (by Greg Martin) As in the second solution, it is convenient to allow \(f(m,0) = f(0,n) = 1\). Define the generating function
\[
G(x,y) = \sum_{m=0}^\infty \sum_{n=0}^\infty f(m,n) x^m y^n.
\]
As equalities of formal power series (or convergent series on, say, the region \(|x|, |y| < 1/3\)), we have
\[
G(x,y) = \sum_{m \geq 0} \sum_{n \geq 0} x^m y^n \sum_{\substack{k_1,\ldots,k_n \in \mathbb{Z} \\ |k_1| + \cdots + |k_n| \leq m}} 1 = \sum_{n \geq 0} y^n \sum_{k_1,\ldots,k_n \in \mathbb{Z}} \sum_{\substack{|k_1| + \cdots + |k_n| \leq m}} x^m = \sum_{n \geq 0} y^n \sum_{k_1,\ldots,k_n \in \mathbb{Z}} \frac{x^{|k_1| + \cdots + |k_n|}}{1 - x} = \frac{1}{1 - x} \sum_{n \geq 0} y^n \left( \sum_{k \in \mathbb{Z}} x^{|k|} \right)^n = \frac{1}{1 - x} \cdot \frac{1}{1 - y(1 + x)/(1 - x)} = \frac{1}{1 - x - y - xy}.
\]
Since \(G(x,y) = G(y,x)\), it follows that \(f(m,n) = f(n,m)\) for all \(m,n \geq 0\).