Lifting the ‘stars and bars’ identity

Wildon's Weblog 2024-09-22

Let $\left(\!\binom{n}{k}\!\right)$ denote the number of $k$ -multisubsets of an $n$ -set. A basic result in enumerative combinatorics is that

$\left(\!\binom{n}{k}\!\right) = \binom{n+k-1}{k} \qquad (1)$

One proof of this uses the method of stars and bars. The link will take you to Wikipedia; for a similar take on the method, interpreting $\left(\!\binom{n}{k}\!\right)$ as the number of ways to put $k$ unlabelled balls into $n$ numbered urns, see Theorem 2.3.3 in my draft combinatorics textbook.

The purpose of this post is to give a combinatorial proof of the $q$ -binomial version of this identity and then to show that this $q$ -lift can be restated as an equality of two symmetric functions specialized at the powers of $q$ , and so is but a shadow of an algebraic isomorphism between two representations of $\mathrm{SL}_2(\mathbb{C})$ . I finish by explaining how my joint work with Eoghan McDowell shows that this isomorphism exists for representations of $\mathrm{SL}_2(\mathbb{F})$ over an arbitrary field $\mathbb{F}$ . Each lifting step, indicated by increasing equation numbers, gives a more conceptual, and often more memorable result. It is not yet clear what formulation might deserve to be called the ‘ultimate lift’ of the stars and bars equality.

Subsets are enumerated by $q$ -binomial coefficients

Given a subset $X$ of $\mathbb{N}_0$ , we define its weight, denoted $\mathrm{wt}(X)$ , to be its sum of entries. We shall adopt a slightly unconventional approach and define the $q$ -binomial coefficient $\genfrac{[}{]}{0pt}{}{n}{k}_q \in \mathbb{C}[q]$ to be the enumerator by weight of the $k$ -subsets of $\{0,1,\ldots, n-1\}$ , normalized to have constant term $1$ . That is,

$\genfrac{[}{]}{0pt}{}{n}{k}_q = q^{-k(k-1)/2} \sum_{X \subseteq \{0,1,\ldots, n-1\}} q^{\mathrm{wt}(X)}.$

(This property of $q$ -binomial coefficients appears to me to be fundamental, but it is not always stressed in introductory accounts.) Clearly $\genfrac{[}{]}{0pt}{}{n}{k}_q$ is a polynomial in $q$ . For example

$\begin{aligned} \genfrac{[}{]}{0pt}{}{4}{2}_q&= q^{-1}(q^{0+1} + q^{0+2} + q^{0+3} + q^{1+2} + q^{1+3} + q^{2+3}) \\ &= 1 + q + 2q^2 + q^3 + q^4, \end{aligned}$

and $\genfrac{[}{]}{0pt}{}{n}{0}_q = \genfrac{[}{]}{0pt}{}{n}{n}_q = 1$ and $\genfrac{[}{]}{0pt}{}{n}{1}_q = 1 + q + \cdots + q^{n-1}$ for all $n \in \mathbb{N}_0$ . We now recover the usual definition of $\genfrac{[}{]}{0pt}{}{n}{k}_q$ . As a preliminary lemma we need a $q$ -lift of Pascal’s Rule $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ , which we prove by adapting the standard bijective proof.

Lemma. If $n \in \mathbb{N}_0$ and $k \in \mathbb{N}$ then

$\genfrac{[}{]}{0pt}{}{n}{k}_q = q^{n-k} \genfrac{[}{]}{0pt}{}{n-1}{k-1}_q + \genfrac{[}{]}{0pt}{}{n-1}{k}_q.$

Proof. Removing $n-1$ from a $k$ -subset of $\{0,1,\ldots,n-1\}$ containing $n-1$ puts such $k$ -subsets in bijection with the $k-1$ subsets of $\{0,1,\ldots, n-2\}$ , enumerated by $\genfrac{[}{]}{0pt}{}{n-1}{k-1}_q$ . This map decreases the weight by $n-1$ . The $k$ -subsets of $\{0,1,\ldots, n-1\}$ not containing $n-1$ are in an obvious weight preserving bijection with the $k$ -subsets of $\{0,1,\ldots, n-2\}$ , enumerated by $\genfrac{[}{]}{0pt}{}{n-1}{k}_q$ . Therefore,

$q^{k(k-1)/2} \genfrac{[}{]}{0pt}{}{n}{k}_q = q^{n-1} q^{(k-1)(k-2)/2} \genfrac{[}{]}{0pt}{}{n-1}{k-1}_q + q^{k(k-1)/2} \genfrac{[}{]}{0pt}{}{n-1}{k}_q.$

Cancelling $q^{k(k-1)/2}$ , using that

$(k-1)(k-2)/2 + k-1 = k(k-1)/2,$

we obtain the required identity. $\Box$

For $n \in \mathbb{N}_0$ , we define the quantum number $[n]_q$ by $[n]_q = 1 + q + \cdots + q^{n-1}$ and the quantum factorial $[n]_q!$ by $[n]_q! = [n]_q[n-1]_q \ldots [1]_q$ . Obsere that specializing $q$ to $1$ these become $n$ and $n!$ , respectively. (See the section on characters below for the connection with the alternative convention in which quantum numbers are Laurent polynomials.) Note that in the following proposition, if $k = 0$ then both products are empty and so $\genfrac{[}{]}{0pt}{}{n}{0}_q = 1$ for all $n \in \mathbb{N}_0$ .

Proposition. If $n$ , $k \in \mathbb{N}_0$ then

$\genfrac{[}{]}{0pt}{}{n}{k}_ q = \frac{[n]_q[n-1]_q \ldots [n-k+1]_q}{[k]_q!}.$

Proof. Working by induction on $n+k$ using the previous lemma we have

$\begin{aligned} \genfrac{[}{]}{0pt}{}{n}{k}_q &= q^{n-k}\genfrac{[}{]}{0pt}{}{n-1}{k-1}_q + \genfrac{[}{]}{0pt}{}{n-1}{k}_q \\ &= q^{n-k} \frac{[n-1]_q\ldots [n-k+1]_q[n-k]_q}{[k-1]_q!} \\ &\qquad \qquad \qquad + \frac{[n-1]_q\ldots [n-k+1]_q[n-k]_q}{[k]_q!} \\&= \frac{[n-1]_q\ldots [n-k+1]_q}{[k]_q!} \bigl( q^{n-k}[k]_q + [n-k]_q \bigr) \\ &= \frac{[n-1]_q \ldots [n-k+1]_q}{[k]_q!} [n]_q \\ \end{aligned}$

where we used the inductive hypothesis to go from line 1 to line 2 and then

$q^{n-k}[k]_q + [n-k]_q = q^{n-k}(1+q + \cdots + q^{k-1}) + 1 + q + \cdots + q^{n-k-1} = 1 + q + \cdots + q^{n-1} = [n]_q$

for the final equality. $\Box$

Partitions in a box are enumerated by $q$ -multibinomial coefficients

Given a multisubset $M$ of $\{0,1,\ldots, n-1\}$ , we define its weight to be its sum of entries (taken with multiplicities). Let

$\left[\!\genfrac{[}{]}{0pt}{}{n}{k}\!\right]_q = \sum_M q^{\mathrm{wt}(M)}$

be the corresponding enumerator. (The double brackets notation is not standard.) For example

$\begin{aligned} \left[\!\genfrac{[}{]}{0pt}{}{3}{2}\!\right]_q &= q^{0+0} + q^{0+1} + q^{0+2} + q^{1+1} + q^{1+2} + q^{2+2} \\ &= 1 + q + 2q^2 + q^3 + q^4 \\ &= \genfrac{[}{]}{0pt}{}{4}{2}\end{aligned}$

and $\left[\!\genfrac{[}{]}{0pt}{}{n}{0}\!\right]_q = 1$ and

$\left[\!\genfrac{[}{]}{0pt}{}{n}{1}\!\right]_q = q^0 + q^1 + \cdots + q^{n-1} = [n]_q = \genfrac{[}{]}{0pt}{}{n}{1}_q$

for all $n \in \mathbb{N}_0$ . This equality $\left[\!\genfrac{[}{]}{0pt}{}{3}{2}\!\right]_q = \genfrac{[}{]}{0pt}{}{4}{2}_q$ is not a coincidence.

The $q$ -stars and bars identity

The $k$ -multisubsets enumerated by $\genfrac{[}{]}{0pt}{}{n}{k}_q$ are in obvious bijection with sequences $(j_1,\ldots, j_k)$ where $0 \le j_1 \le \ldots \le j_k \le n-1$ . In turn, such sequences are in bijection with $k$ subsets of $\{0,\ldots, n+k-2\}$ by the map

$(j_1,\ldots, j_k) \mapsto \{ j_1+0,j_2+1, \ldots, j_k+(k-1) \}.$

The composite map takes a multisubset of weight $w$ to a subset of weight $w + k(k-1)/2$ . By the first section, $q^{k(k-1)/2}\genfrac{[}{]}{0pt}{}{n+k-1}{k}_q$ enumerates $k$ -subsets of $\{0,1,\ldots, n+k-2\}$ by their weight. We therefore have a bijective proof that

$\left[\!\genfrac{[}{]}{0pt}{}{n}{k}\!\right]_q = \genfrac{[}{]}{0pt}{}{n+k-1}{k}_q .\qquad(2)$

This is the $q$ -lift of (1), that $\left(\!\binom{n}{k}\!\right) = \binom{n+k-1}{k}$ . It seems striking to me that this bijection is easier to describe that the stars and bars bijection, while proving a more general result.

The abacus interpretation

We digress to give another combinatorial interpretation of $\left[\!\genfrac{[}{]}{0pt}{}{n}{k}\!\right]_q$ . Observe that a partition whose Young diagram is contained in the $k \times (n-k)$ box is uniquely specified by the sequence $0 \le j_1 \le \ldots \le j_k \le n-k$ of $x$ -coordinates of its $k$ distinct upward steps. (See examples shortly below.) Moreover, since an upward step at $x$ -coordinate $j$ adds $j$ boxes to the partition, the size of the partition is the weight of the multisubset $\{j_1,\ldots, j_k\}$ . Therefore $\genfrac{[}{]}{0pt}{}{n}{k}_q$ enumerates partitions in the $k \times (n-k)$ box by their size. Using this partition setting, the map

$(j_1,\ldots, j_k) \mapsto \{ j_1+0,j_2+1, \ldots, j_k+(k-1) \}$

from weakly increasing sequences to subsets of $\{0,1,\ldots, n-1 \}$ corresponds to recording a partition not by the $x$ coordinates of its upward steps, but instead by the step numbers of its upward steps, numbering steps from $0$ .

Illustrative examples with $k =4$ and $n-k = 5$ of the partitions $(4,3,3,2)$ and $(5,4,1)$ are shown in the diagram below with step numbers in bold.

Below each partition is the corresponding abacus: note that the step numbers of the upward steps are simply the bead positions on the abacus. This is related to Loehr’s beautiful labelled abaci model for antisymmetric functions.

Exercise. Use the abacus to give an alternative proof of the lemma, restated below

$\genfrac{[}{]}{0pt}{}{n}{k}_q = q^{n-k} \genfrac{[}{]}{0pt}{}{n-1}{k-1}_q + \genfrac{[}{]}{0pt}{}{n-1}{k}_q.$ Perhaps surprisingly, this is not the unique $q$ -lift of Pascal’s Rule. Use the abacus in a different way to prove that

$\genfrac{[}{]}{0pt}{}{n}{k}_q = \genfrac{[}{]}{0pt}{}{n-1}{k-1}_q + q^k \genfrac{[}{]}{0pt}{}{n-1}{k}_q.$

Exercise. Prove that

$(1 + qz)(1+q^2 z) \ldots (1+q^{n-1}z) = \sum_{k=0}^n q^{k(k-1)/2} \genfrac{[}{]}{0pt}{}{n}{k}_q z^k$

This is one of many identities that generalize the usual Binomial Theorem.

Symmetric functions.

For $k \in \mathbb{N}_0$ let $e_k$ and $h_k$ be the elementary and complete symmetric functions of degree $k$ in variables $x_1,x_2,\ldots$ . Thus $e_k$ is the sum of all products of $k$ distinct variables and $h_k$ is the sum of all products of $k$ variables, repetitions allowed. More generally, let $s_\lambda$ denote the Schur function labelled by the partition $\lambda$ as defined combinatorially by

$s_\lambda= \sum_{t \in \mathrm{SSYT}(\lambda)} x^t$

where if the semistandard tableau $t$ has $c_i$ entries of $i$ for each $i \in \mathbb{N}$ then $x^t = x_1^{c_1} x_2^{c_2} \ldots$ . It is a good basic exercise to show that $e_k = s_{(1^k)}$ and $h_k = s_{(k)}$ . It is immediate from our definition of $q$ -binomial coefficients that $e_k(1,q,\ldots, q^{n-1}) = q^{k(k-1)/2} \genfrac{[}{]}{0pt}{}{n}{k}_q$ and it is immediate from the $q$ -stars and bars identity that

$h_k(1,q,\ldots, q^{n-1}) = \left[\!\genfrac{[}{]}{0pt}{}{n}{k}\!\right] = \genfrac{[}{]}{0pt}{}{n+k-1}{k}_q$

and so $h_k(1,q,\ldots, q^{n-k}) = \genfrac{[}{]}{0pt}{}{n}{k}.$ The $q$ -stars and bars identity becomes

$h_k(1,q,\ldots, q^{n-1}) = q^{-k(k-1)/2} e_k(1,q,\ldots, q^{n+k-2}) \qquad(3)$

All these identities are special cases of the result, almost immediate from the combinatorial definition of Schur functions that $s_\lambda(1,q,\ldots, q^{k-1})$ enumerates semistandard tableaux with entries from $\{0,1,\ldots, k-1\}$ by their weight, i.e.~their sum of entries.

Characters of $\mathrm{SL}_2(\mathbb{C})$

The reason for bringing in symmetric functions is the following theorem which connects representations of $\mathrm{SL}_2(\mathbb{C})$ with plethysms of symmetric functions and hence enumeration of semistandard tableaux. Let $\nabla^\lambda$ denote the Schur function labelled by the partition $\lambda$ ; if $E$ is a $d$ -dimensional vector space then the trace of the diagonal matrix with entries $\alpha_1, \ldots, \alpha_d$ acting on $\nabla^\lambda(E)$ is $s_\lambda(\alpha_1,\ldots, \alpha_d)$ . It is an instructive exercise to verify from this property that $\nabla^{(k)}E \cong \mathrm{Sym}^k E$ and $\nabla^{(1^k)}E \cong \bigwedge^k E$ .

Theorem. Let $E$ be the natural representation of $\mathrm{SL}_2(\mathbb{C})$ . The representations $\nabla^\lambda \mathrm{Sym}^\ell E$ and $\nabla^\mu \mathrm{Sym}^m E$ are isomorphic if and only if the specialized Schur functions $s_\lambda(1,q,\ldots, q^\ell)$ and $s_\mu(1,q,\ldots, q^m)$ are equal up a power of $q$ .

Proof. See Theorem 3.4(b) and (d) in my joint paper with Rowena Paget. $\Box$

One reason for not giving full details at this point is that it enables me to suppress an annoying technicality. By our definition, the representation $\mathrm{Sym}^\ell E$ of $\mathrm{GL}_2(\mathbb{C})$ has character

$h_\ell(x_1,x_2) = x_1^\ell + x_1^{\ell-1}x_2 + \cdots + x_2^\ell.$

(Or to be precise, the trace of the diagonal matrix with entries $\alpha, \beta$ acting on $\mathrm{Sym}^\ell E$ is this polynomial evaluated at $x_1 = \alpha$ , $x_2 = \beta$ .) Restricting to $\mathrm{SL}_2(\mathbb{C})$ , we should impose the relation $x_1x_2 = 1$ , meaning that if $x_1 = Q$ then $x_2 = Q^{-1}$ , and so we work most naturally with Laurent polynomials in $Q$ . (This is essential since unequal characters of $\mathrm{GL}_2(\mathbb{C})$ may become equal on restriction to $\mathrm{SL}_2(\mathbb{C})$.) Thus as a representation of $\mathrm{SL}_2(\mathbb{C})$ , $\mathrm{Sym}^\ell\! E$ has character

$s_\ell (Q,Q^{-1}) = Q^\ell + Q^{\ell-2} + \cdots + Q^{-\ell}$

and more generally, $\nabla^\lambda \mathrm{Sym}^\ell E$ has character

$s_\lambda(Q^{\ell}, Q^{\ell-2}, \ldots, Q^{-\ell}) = (s_\lambda \circ s_\ell)(Q, Q^{-1})$

where $\circ$ is the plethysm product. (This is the main idea needed to prove the theorem.) One can always pass from a Laurent polynomial identity in $\mathbb{C}[Q,Q^{-1}]$ to a polynomial identity in $\mathbb{C}[q]$ polynomials by setting $q = Q^2$ and multiplying through by a suitable power of $Q$ , so it is possible to work in either setting.

Exercise. Give as many proofs as you can that the $q$ -binomial coefficient $\genfrac{[}{]}{0pt}{}{n}{k}_q$ is centrally symmetric; that is, writing $[z^a]f(z)$ for the coefficient of $z^a$ in the polynomial $f(z)$ , we have

$[z^r] \genfrac{[}{]}{0pt}{}{n}{k}_q = [z^{n(n-1)/2-r}] \genfrac{[}{]}{0pt}{}{n}{k}_q$

for all $r \in \mathbb{N}_0$ . [Hint: there is a one-line proof using $Q$ -characters. For a proof at the level of polynomials, show that the reverse of a polynomial $f(q)$ of degree $c$ is $z^c f(q^{-1})$ , and that the palindromic property is preserved by multiplication and division, and then apply this to the formula in the proposition.]

It is worth noting that the sum of centrally symmetric polynomials (as opposed to Laurent series) is centrally symmetric if and only if they have the same degree. This seems to me to be one obstacle to giving a representation theory interpretation of identities such as the $q$ -lift of Pascal’s Rule in the first lemma.

Exercise. Use the representation theory of $\mathrm{SL}_2(\mathbb{C})$ to show that the $q$ -binomial coefficients $\genfrac{[}{]}{0pt}{}{n}{k}_q$ are unimodal; that is, the coefficients increase up to the middle degree(s) and then decrease.

The Wronksian isomorphism.

Taking $\lambda = (1^k)$ and $\mu = (k)$ in the theorem, we obtain that the representations $\bigwedge^k \mathrm{Sym}^\ell E$ and $\mathrm{Sym}^k \mathrm{Sym}^m E$ of $\mathrm{SL}_2(\mathbb{C})$ are isomorphic if and only if $e_k(1,q,\ldots, q^{\ell-1}) = q^{\ell(\ell-1)/2}\genfrac{[}{]}{0pt}{}{\ell}{k}_q$ and $h_k(1,q,\ldots, q^{m-1}) = \genfrac{[}{]}{0pt}{}{m+k-1}{k}_q$ are equal up a power of $q$ . (These equalities were proved in the previous subsection.) We therefore set $\ell = n + k -2$ and obtain the Wronksian isomorphism.

$\bigwedge^k \mathrm{Sym}^{n+k-2} E \cong \mathrm{Sym}^k \mathrm{Sym}^{n-1} E \qquad (4)$

of representations of $\mathrm{SL}_2(\mathbb{C})$ , lifting the $q$ -stars and bars identity $\left[\!\genfrac{[}{]}{0pt}{}{n}{k}\!\right]_q = \genfrac{[}{]}{0pt}{}{n+k-1}{k}_q$ to the level of representations. Instead going down to the level of ordinary binomial coefficients, by setting $q=1$ , we obtain $\left(\!\binom{n}{k}\!\right) = \binom{n+k-1}{k}$ which is where we started. This is however only the start of the story: in my joint paper with Eoghan McDowell, we showed that the modified Wronksian isomorphism

$\bigwedge^k \mathrm{Sym}^{n+k-2}\! E \cong \mathrm{Sym}_k \mathrm{Sym}^{n-1} \! E \qquad(5)$

in which the symmetric power $\mathrm{Sym}^k \! E$ (defined as a quotient of $E^{\otimes k})$ is replaced with its dual $\mathrm{Sym}_k E$ (defined as a submodule of $E^{\otimes k}$ ), holds as an isomorphism of representations of $\mathrm{SL}_2(\mathbb{F})$ for an arbitrary field $\mathbb{F}$ . This is the most refined lift I know to date of stars and bars.

Exercise. Let $E = \langle u, v \rangle$ . Show that, regarded as a representation of $\mathrm{GL}_2(\mathbb{C})$ , $\mathrm{Sym}^2 \! E = \langle u^2, v^2, uv \rangle$ has $\langle u^2, v^2\rangle$ as an irreducible $2$ -dimensional submodule with quotient isomorphic to the determinant representation and, dually,

$\mathrm{Sym}_2 E = \langle u\otimes u, v \otimes v, u \otimes v + v \otimes u \rangle$

has $\langle u \otimes v + v \otimes u$ as a one-dimensional submodule isomorphic to the determinant representation, with quotient the irreducible $2$ -dimensional representation already seen.

For much more on duality and multilinear constructions see this earlier blog post.

Lifting the ‘stars and bars’ identity

Wildon's Weblog 2024-09-22

Subsets are enumerated by -binomial coefficients

Partitions in a box are enumerated by -multibinomial coefficients

The -stars and bars identity