driver's ed in the forest

• introduction to driving: parking
• mistaking the trees for the forest
• interlude: catalan crossover, off the chain
• what if we tried \(q\)-analogues?
• coda: Haiman and diagonal harmonics

time to talk about my favorite combinatorial sequences! okay, stop me if you’ve heard this one before – suppose we have \(n\) different cars, and we want to know the number of ways to park them in \(n\) spots in a line. the first spot has \(n\) options, the second has \(n-1\), and–

oh. you know that’s \(n!\) already. great! let’s talk about my second-favorite sequence instead. say each of the \(n\) cars is shaped like a domino. how many ways are there to park them inside a \(2 \times n\) rectangle–

uhh okay wait so you know that one’s Fibonacci already. okay, fine, let’s do my third favorite combinatorial sequence then. suppose you are driving from the city center to intersection of \(n\) Street North and \(n\) Avenue East. How many ways can you do this without–

wait, you’ve read the EC addendum and wrote own all of the bijections between the different ways to count Catalan objects? okay dang sorry. let’s do a deeper cut and talk about my second third fourth favorite combinatorial sequence…

out of character: I’ve been thinking about this sequence quite a lot recently and it’s come up quite a bit. I’m writing this for myself to quickly reference later in case I forget any of the nice things about this sequence. Catherine Yan has a really great chapter on this subject in the Handbook of Enumerative Combinatorics, and this subject ties in fairly strongly to \((q,t)\)-Catalan combinatorics and Macdonald polynomials, which are scary but pretty neat. I first heard about this topic and the objects they enumerate from Karola Meszaros and her undergraduate combinatorics class – they are in fact very neat!

introduction to driving: parking

returning to the first scenario – suppose now that we want to park our \(n\) different cars in the \(n\) spots, but there’s a catch now – the cars have opinions! each car has a preferred spot, indicated by the tuple \((s_i)_{i=1}^n\), where for each \(i\), \(1 \le s_i \le n\). going in order, car \(i\) will drive into the lot, passing each of the spots in ascending order, in search of their preferred spot \(s_i\) and attempt to park there. if their spot is occupied, they will continue to the next available spot in ascending order.

note that it’s possible that a sequence of preferences prevents a car from parking in any of the \(n\) spots! for instance, if \(n = 5\) and three cars want to park in spot number \(5\), then after the first car parks there, the other two cars will have nowhere to go. sad! in this scenario, we ask a slightly different question – how many preferences \((s_i)_{i=1}^n\) allow all the cars to park?

observe first that this number is at least \(n!\) – if all of the preferences are different, there are no collisions and every car gets to go its to preferred spot. trouble starts to arise when cars start to prefer the same spaces. in particular, note that for any \(1 \le k \le n\), a sequence of preferences allows all the cars to park iff \(\abs{\set{s_i \ge k}} \le n-k+1\). we call such sequences parking functions, and we’ll denote the set of them as \(\mc P_n\). note that this condition characterizing parking functions is not dependent on the specific sequence of elements \((s_i)_{i=1}^n\), only on the multiset that they form. therefore, \(\mc P_n\) admits an \(S_n\)-action – in other words, any valid parking function can be rearranged in any way to form another valid parking function! In this way, parking functions generalize permutations – \(S_n \subseteq \mc P_n\) viewed as one-line strings, and is \(S_n\)-equivariant.

As an explicit example, when \(n = 3\), we can first count the \(6\) permutations \(123, 132, 213, 231, 312, 321\). There’s more – we can obviously have \(111\), which is a fixed point under an \(S_3\)-action. We can also have \(112, 121, 211\), \(113, 131, 311\), and \(122, 212, 221\), all of which rotate under a 3-cycle. This gives a total of \(16\) parking function. Similarly, one can count the \(3\) parking functions \(11, 12, 21\) when \(n = 2\), and with a little more effort one can count \(125\) parking functions when \(n = 4\) (where we only list one element in every \(S_4\)-orbit):

\[1234 \, (\times 24), 1123, 1223, 1233, 1124, 1134, 1224 \, (\times 12),\] \[1122, 1133 \, (\times 6), 1112, 1113, 1114, 1222 (\times 4), 1111\]

Pollack (1968) has a really nice argument to determine the number of parking functions. Imagine adding an \((n+1)\)st parking spot labeled with a \(0\) so that cars can progress to \(0\) after the spot labeled \(n\) and loop back around to the first spot labeled \(1\). If the cars attempt to park in this scheme, then all of the cars can park provided everyone is willing to go around the back, leaving one spot empty. Note that increasing everyone’s preferences by \(1 \mod (n+1)\) cycles where the empty spot ends up. Moreover, given a preference sequence \((s_i)_{i=1}^n\) where now we allow \(0 \le s_i \le n\), the spot \(0\) is empty iff all of the \(s_i\) satisfy \(1 \le i \le n\) and no car goes around the back, i.e. the cars could have parked without the extra spot. Then exactly \(\frac 1{n+1}\) of the \((n+1)^n\) preference sequences are parking functions, giving us \(\abs{\mc P_n} = (n+1)^{n-1}\) parking functions!

For a computer scientist, we can think about this process like hashing \(n\) elements into an \(n\)-element array with linear probing, so the hash functions that don’t require some sort of overflow-handling are precisely the parking functions. Linear probing and statistics that measure its effectiveness have been studied extensively, and especially in the general setting where we are hashing into an \(m\)-element array with \(m > n\) – see Section 1.3.1 of Yan’s chapter for an extensive discussion.

okay, let’s do something completely different now.

mistaking the trees for the forest

how many trees are there with vertex set \([n]_0 = \set{0, 1, \dots, n}\)? This is given by the celebrated Cayley’s formula, which says the number of labeled trees with vertex set \([n]\) is \(n^{n-2}\). with our additional vertex \(0\), we again have \((n+1)^{n-1}\) such trees – our fourth favorite sequence again!

we can spend a long time discussing various methods of proving Cayley’s formula – Aigner-Ziegler’s Proofs from THE BOOK has several. Joyal has a really nice argument where this is related to the number of functions \([n] \to [n]\) overall (of which there are \(n^n\)). There are also a couple of other arguments that count these trees by counting forests on \([n]\) and then restrict to the case where the forest is a single tree. There’s also an argument that uses the Matrix-Tree Theorem (which states that the determinant of a \((\abs V - 1) \times (\abs V - 1)\) minor of the graph Laplacian counts the number of spanning trees on the graph) and applies this to the Laplacian of the complete graph.

One can also induct and use generating functions to show this, as it turns out. The following argument comes from Alex Postnikov’s class notes. In particular, one can consider the “degree generating function” for \(\mc T_n\). For any tree \(T \in \mc T_n\), let \(d_T(i)\) be the degree of the vertex \(i\) in \(T_n\). Then consider the polynomial

\[F_n(x_1, \dots, x_n) = \sum_{T \in \mc T_n} \prod_{i=1}^n x_i^{d_T(i) - 1}\]

Note that since every vertex in a tree is connected to at least one other, every exponent is non-negative and so this is a genuine polynomial. We show by induction that \(F_n(x_1, \dots, x_n) = (x_1 + \dots + x_n)^{n-2}\) for \(n \ge 2\).

This is clear for \(n = 2\). Note that setting \(x_n = 0\) removes all the terms where vertex \(n\) is not a leaf of the tree \(T\). For each tree where \(n\) is a leaf of a tree in \(\mc T_n\), this corresponds to a tree in \(\mc T_{n-1}\) with a choice of one of the vertices \([n-1]\) that the vertex \(n\) attaches to. Then,

\[F_n(x_1, \dots, x_{n-1}, 0) = (x_1 + \dots + x_{n-1}) F_{n-1}(x_1, \dots, x_{n-1}) = (x_1 + \dots + x_{n-1})^{n-2}\]

by induction. But this argument holds for any \(i \in [n]\), not just \(n\) itself! In particular, we have that

\[F_n(x_1, \dots, x_n)\Big|_{x_i = 0} = (x_1 + \dots + \hat {x_i} + \dots + x_n)^{n-2}\]

for any \(i \in [n]\) with an analogous argument.

If we let \(G_n(x_1, \dots, x_n) = F_n(x_1, \dots, x_n) - (x_1 + \dots + x_n)^{n-2}\), we know that \(G_n\) is a polynomial of degree at most \(n-2\) (since \(\deg F_n = 2(n-1) - n = n-2\)) that vanishes when any \(x_i = 0\). In particular, \(x_i\) must divide \(G_n\) for all \(i \in [n]\). But then since \(G_n\) is divisible by \(n\) distinct linear factors, we must then have that \(G_n = 0\) from degree considerations. Plugging in \(x_i = 1\) for all \(i \in [n]\) gives the desired count.

For completeness, one must mention the Prüfer code of a labeled tree. For a labeled tree on \(n\) vertices, the Prüfer code is a string \((c_j)_{j=1}^{n-2}\) length \(n-2\), where each character \(c_j\) in the string is an element of \([n]\). This code is iteratively constructed so that the \(j\)th element of the string is the neighbor of the leaf with the smallest label, where the leaf is then removed at the end of that step.

Given such a sequence in \([n]^{n-2}\), one can also reconstruct a unique labeled tree. In particular, one can construct the degree sequence \((d_i)_{i=1}^n\) of the tree. Suppose \(v, w\) are the last two distinct elements of the sequence – these are the last two vertices that remain and are connected at the end of the removal process. For \(i \neq v, w\), we have \(d_i = 1 + \abs{\set{j : c_j = i}}\), and otherwise \(d_i = 2 + \abs{\set{j : c_j = i}}\) (accounting for the edge that connects \(v\) and \(w\)). This information, along with the connectivity information given by the sequence, is sufficient to iteratively reconstruct the labeled tree starting with the leaves. Denoting the set of trees with vertex set \([n]\) as \(\mc T_n\), one can check that these two maps go between \(\mc T_n\) and \([n]^{n-2}\), and are inverses. This immediately counts the number of labeled trees \(\abs{\mc T_n}\) as \(n^{n-2}\).

We will immediately turn around and use these codes in the case where we are looking at trees on \([n]_0\), which we’ll denote by \(\mc T^\circ_{n+1}\). Now, these codes count labeled trees on \(n+1\) vertices, and we need codes of length \(n-1\) with entries in \([n]_0\). As an example when \(n = 3\), we can track these trees more easily by using their Prüfer codes. Here is the breakdown of these trees up to \(S_3\) symmetry by their codes:

Tree Type (up to symmetry)	Codes
Path with \(0\) at end	12, 13, 21, 23, 31, 32
Path with \(0\) in middle	01, 02, 03, 10, 20, 30
3-valent tree with \(0\) as leaf	11, 22, 33
3-valent tree with \(0\) in middle	00

now let’s bring parking functions back into the picture – how do they connect to the trees and the codes? Are there (nice) bijections between these sets?

the Handbook chapter (Yan) has a nice bijection between Prüfer codes \([n]_0^{n-1}\) and \(\mc P_n\) (also attributed to Pollack). For any Prüfer code (now of length \(n-1\)) \((c_j)_{j=1}^{n-1}\), we will construct a parking function \((s_i)_{i=1}^n\) where \((c_j)_{j=1} = \Delta(s_i)_{i=1}^n\) (where these successive differences are taken mod \((n+1)\)). The issue is to work out what the initial preference \(s_1\) should be to get something well-defined. In particular, consider the auxiliary sequence \((h_i)_{i=1}^n = \sum_{j=1}^i c_j \mod n+1\). Once we know \(s_1\), we can just let \(s_i = s_1 + h_i \mod n+1\). In particular, we want every such \(s_i\) to be nonzero \(\mod n+1\), and such a shift must exist – we get at most \(n\) distinct residues mod \(n+1\), and the smallest missing residue can be shifted to be zero.

Yan has a more detailed algorithm to explicitly compute this shift, using a property of the specification of the parking function. The specification \((r_i)_{i=1}^n\) for any sequence in \([n]^n\) counts the number of times each number appears, so that \(r_i = \abs{\set{k : s_k = i}}\). In the case of parking functions, we have that \(\sum_{i=1}^k r_i \ge k\) with equality when \(k = n\) – we call such specifications balanced. All parking functions have balanced specifications, so if the sequence \((h_i)_{i=1}^n\) above does not have a balanced specification, we can compute how much \(\sum_{i=1}^k r_i\) falls short of \(k\). Yan claims that letting \(a_1 = n - d\), where \(d\) is the smallest index that achieves the largest deficit from being balanced, i.e. \(d\) is the smallest index \(k\) achieving \(\min\set{\sum_{i=1}^k r_i - k}\).

Using this scheme, here is an extended table matching the trees with their codes and corresponding parking functions when \(n = 3\):

Tree Type (up to symmetry)	Codes	Parking Functions
Path with \(0\) at end	12, 13, 21, 23, 31, 32	231, 121, 312, 132, 212, 213
Path with \(0\) in middle	01, 02, 03, 10, 20, 30	112, 113, 221, 122, 311, 211
3-valent tree with \(0\) as leaf	11, 22, 33	123, 131, 321
3-valent tree with \(0\) in middle	00	111

Unfortunately, while in the first two columns we have some rough \(S_3\)-symmetry, this doesn’t carry as nicely over to the corresponding parking functions.

interlude: catalan crossover, off the chain

(this result is due to Kreweras, 1971 and Stanley, 1996.)

yet another neat fact about \((n+1)^{n-1}\) relates to non-crossing partitions! Non-crossing partitions on \([n]\) are set partitions \(\pi\) of \([n]\) such that there are not \(a < b < c < d\) and distinct blocks \(B, B'\) of \(\pi\) such that \(a, c \in B\) and \(b, d \in B'\). one can think of the elements of \([n]\) as points on a line or a circle and connecting the elements in the same block with arcs to describe a set partition – in this way, the non-crossing condition precisely describes what it means for the arcs to not cross.

set partitions are naturally ordered by refinement in the lattice \(\Pi_n\), and the non-crossing ones form a lattice under the same partial order that we call \(NC_n\).¹ These are particularly nice because they are one of the many Catalan objects! this lattice is also self-dual (which is not true of the normal set partition lattice). their maximal chains can also be labeled by (you guessed it)… parking functions!

looking at the Hasse diagram of non-crossing partitions, each covering relation is given by merging two blocks \(B\) and \(B'\) together. Stanley labels all such edges in the Hasse diagram in the following way – i f \(\min B < \min B'\), label this edge with \(\max \set{i \in B, i < \min B'}\), i.e. the biggest element in \(B\) that is less than the minimum of \(B'\). This then easily allows one to get maximal chains which end up being labeled by parking functions! In particular, the maximal chains of \(NC_{n+1}\) are in bijection with the parking functions \(\mc P_n\). This labeling also allows us to define a local action of \(S_n\) on this lattice, which is also pretty neat!

Using \(n = 3\) as our running example again, we need to first write down the \(C_{3+1} = 14\) non-crossing partitions on \(4\) elements, and put them in a lattice:

Here is this lattice with the edges labeled (assuming the dots are numbred in increasing order starting from the top left):

speaking of Catalan objects, parking functions can also be put in bijection with labeled Dyck paths. Dyck paths of course are probably The Catalan Object², so considering that there’s a relation to Catalan objects, these have to be involved. Here, we say a labeled Dyck path is one where each of the \(n\) north steps is labeled with an element of \([n]\), such that consecutive strings of north steps are in increasing order. To turn a parking function into a labeled Dyck path from \((0,0)\) to \((n,n)\), we let \(s_i\) be the index of the column of cells that the north step labeled \(i\) is in, i.e. if the north step from \((0,1)\) to \((0, 2)\) is labeled with a \(3\), \(s_3 = 1\).

This bijection is rather nice as there is a nice bijection between non-crossing partitions and Dyck paths. One can view a Dyck path of north and east steps as an instruction set that manages a stack of elements where the \(i\)th north step pushes \(i\) onto a stack and east steps pop elements off of the stacks. If we think of the consecutive runs of elements that are popped off as the blocks, we get non-crossing partitions of elements as a result of the first-in-last-out-ness of the stack. In particular, Dyck paths can also be ordered by refinement, and give an isomorphic lattice under containment of paths to the noncrossing partition lattice.

Moreover, a maximal chain of Dyck paths of length \(n+1\) can be given by a labeled Dyck path of length \(n\). Starting with the smallest Dyck path under containment which is just \(n+1\) alternating north and east steps, there are \(n\) spots where the path flips from an east step to a north step – label these from \(1\) to \(n\). Any order in which one can remove these spots by flipping the order of the neighboring east and north blocks gives a labeled Dyck path of length \(n\) where one puts a north step labeled \(i\) where the \(i\)th spot is removed, and in the column given by the number of east steps before that spot. (Or at least, I think this works? The gradual sorting of the east steps to after the north steps makes this well-defined, I think.) In particular, this bijection commutes with the parking function given by the maximal chain corresponding to chains in the non-crossing partitions lattice and the bijection between Dyck paths and non-crossing partitions. I think this is quite neat!

hooray for Catalan Things!

what if we tried \(q\)-analogues?

well fine! let’s go even further.

To do this, we need to define some statistics on these sets. Here are some of the statistics that end up being rather lucrative:

• for parking functions – the displacement \(D(s)\) counts the number of times a car fails to find a parking space, and the luck(??) \(\mathrm{lucky}(s)\) be the number of cars that get lucky, i.e. get their preferred spot. From the point of view of hash functions, the displacement counts the number of probes, and \(\mathrm{lucky}(s)\) counts the number of elements that hash directly into their place.
• for labeled trees (with a \(0\) vertex) – an inversion is a pair \((i, j)\) with \(i < j\) but \(j\) lies on the path from \(0\) to \(i\). As one might expect, we denote the number of inversions in a labeled tree \(T\) as \(\inv(T)\). We also can count the number of leaders in a tree \(T\) – this is the number of vertices that are the smallest in the subtree given by that vertex (directed away from the vertex \(0\)), which we call \(\mathrm{lead}(T)\).

This allows us to define

\[P_n(q) = \sum_{s \in \mc P_n} q^{D(s)}\] \[I_n(q) = \sum_{T \in \mc T^\circ_{n+1}} q^{\inv(T)}\]

One can show that \(P_n(q) = I_n(q)\) – both generalizing \((n+1)^{n-1}\) and providing a common \(q\)-analogue for this sequence. This can be done recursively, or with a bijection that preserves these statistics – Yan describes one due to Knuth that does exactly this. Moreover, this bijection also preserves \(\mathrm{lucky}\) and \(\mathrm{lead}\) – one can show that

\[\sum_{s \in \mc P_n} t^{\mathrm{lucky}(s)} = \sum_{T \in \mc T^\circ_{n+1}} t^{\mathrm{lead}(T)} = t \prod_{k=1}^{n-1} (k + (n-k+1)t).\]

These statistics are a little less common, but hhave also received study in other contexts!³

Both of these polynomials are related to yet another generating function. Suppose \(\mc G_n\) is the collection of all connected simple graphs on \(n\) vertices. Then if we define the edge-generating function for these graphs in the following way (with a shift):

\[C_n(q) = \sum_{G \in \mc G_{n+1}} q^{\abs{E(G)} - n}\]

Then it happens that \(I_n(1+q) = P_n(1+q) = C_n(q)\). How can we get this?

Schützenberger (1968) has a nice argument putting \(\mc P_n\) and \(\mc T_{n+1}^\circ\) in bijection, relating to searching algorithms. Given a parking function \((s_i)_{i=1}^n\), construct a tree such that \(i\) is a child of the \(s_i\)th vertex visited when doing breadth-first search starting at vertex \(0\) (breaking ties by visiting the added frontier vertices in increasing order). This can be done by iterating through from \(1\) to \(n\) in increasing order and adding the indices \(i\) such that \(s_i\) takes on these values as the leaves of the constructed tree, attached at the apporpriate vertex. Conversely, a breadth-first search immediately returns the parking function, so this map yields a bijection.

This bijection is not uniquely defined – Yan discusses how one can generalize Schützenberger’s bijection using an encoding of parking functions with their specification and a permutation. In particular, one can define a permutation \(\sigma\) from any parking function \((s_i)_{i=1}^n\) via

\[\sigma_i = \abs{j : a_j < a_i \text{ or } a_j = a_i \text{ and } j \le i}.\]

In particular, \(\sigma\) is the permutation that sorts the entries of the parking function into non-decreasing order, leaving equal elements in the same relative order. Conversely, given a specification, not all permutations are be compatible with the specification – in particular, we require that in \(\sigma^{-1}\), terms with indices that correspond to \(1 + \sum_{i=1}^k r_i, \dots, \sum_{i=1}^{k+1} r_i\) have to appear in increasing blocks. This ensures that elements of the same value in the parking function have their order preserved. The collection of pairs of balanced specification vectors and a choice of permutation compatible with them therefore are in bijection with parking functions.

We can use this encoding to generate many different bijections between parking functions and trees. To do this, pick your favorite well-defined scheme of traversing a tree, given by a choice function \(\gamma\) that gives a specific order to the traversal. This choice of choice function tells us the number of successors encountered at every stage of the traversal, and given the labels of the tree, gives us a permutation of those labels. Taking that to be a specification and a compatible permutation, this gives us a parking function. In particular, if we take this choice function to be that given by the breadth-first search with a queue, then we recover Schützenberger’s bijection. Moreover, as an intermediate, the specification describes the shape of the tree on each level (more or less) and the permutation describes how these levels fit together. Variations with depth-first search and different implementations of breadth-first search are used in the Handbook to describe a number of possible bijections.

In particular, using a breadth-first search with a queue on an arbitrary connected graph \(G\) on the vertices \([n]_0\), we get a spanning tree \(T\) on \([n]_0\). But which graphs on \([n]_0\) yield \(T\) as the spanning tree after this breadth first search? Note that we can safely add an edge \(\set{i, j}\) to the tree if when one of these vertices is processed, the other is in the queue. Call this set of safe edges to add without modifying the resulting spanning tree \(E'(T)\) – \(G\) is then determined by a subset of \(E'(T)\), given its spanning tree \(T\).

In order to get this count, we have to trace through the execution of the breadth-first search that produces this tree and track how many vertices are in the queue. For example, from the specification produced from this tree, the first vertex processed (the \(0\) vertex) has \(r_1\) neighbors, which all get added to the queue. All of these edges are already part of the tree, which we don’t want to count. The next vertex processed cannot be connected to any of the other vertices in the queue in the spanning tree, so all of those are valid edges to count as a part of \(E'(T)\)! In particular, we get \(r_1 - 1\) possible new edges to add. Processing \(r_1\) adds \(r_2\) neighbors of this first vertex to the queue, which leaves \(r_1 + r_2 - 2\) possible vertices that the second vertex processed can be connected to. Inducting and continuing in this way, we see that the \(i\)th vertex processed has \(-i + \sum_{k=1}^i r_k\) possible options. Counting this up across all \(n\) non-zero vertices we get

\[\abs{E'(T)} = \sum_{i=1}^n (n+1-i)r_i - \binom{n+1}2 = \binom {n+1} 2 - \sum_{i=1}^n i r_i\]

where \(\sum_{i=1}^n r_i = n\), since we eventually must process all \(n\) other nonzero vertices in the tree.

For any \(T\), let \(s\) be the corresponding parking function under Schutzenberger’s bijection. Observe that when we reverse this bijection, the sequence \((r_i)_{i=1}^n\) gives the specification for the tree we are trying to build. In particular, the sum \(\sum_{i=1}^n i r_i\) is equal to the sum of the entries in our parking function, \(\sum_{i=1}^n s_i\) by double counting. The size of \(E'(T)\) is therefore given by \(\binom{n+1}2 - \sum_{i=1}^n s_i\), which we claim is none other than the displacement of the corresponding parking function \(D(s)\)! Since every car must end up in some parking spot, for whichever parking spot \(p_i\) car \(i\) ends up in, \(p_i - s_i\) is how many spots car \(i\) fails to park in ghat spot, where when ranging over all \(i\), \(p_i\) ranges over \([n]\). Thus \(\abs{E'(T)}\) is precisely \(D(s)\), where \(s\) is the corresponding parking function under the breadth-first search bijection.

Let’s apply this observation to the polynomial \(C_{n}(q)\), which we described as a sum over all graphs on \(n+1\) vertices, \(\mc G_{n+1}\). Partitioning by their spanning trees \(T\) under the breadth-first search and noting that we can either count a factor of \(1\) or \(q\) depending on whether or not we pick up an element of \(E'(T)\), we get:

\[C_n(q) = \sum_{G \in \mc G_{n+1}} q^{\abs{E(G)} - n} = \sum_{T \in \mc T^\circ_{n+1}} (1+q)^{\abs{E'(T)}} = \sum_{s \in \mc P_n} (1+q)^{D(s)} = P_n(1+q)\]

Here, we implicitly pass our sum through the bijection beteween trees \(\mc T^\circ_{n+1}\) and parking functions \(\mc P_n\), which allows us to prove the identity claimed above.

What if we used a different search algorithm, like depth-first search (prioritizing the largest-numbered vertices)? We can run the same analysis, defining a set \(E''(T)\) for edges that a graph \(G\) with spanning tree \(T\) under this search algorithm could have. Similar to the above, we can characterize \(E''(T)\), and we claim that the edges \(\set{u, v}\) that we can add are in bijection with inversions of \(T\) (i.e. pairs \((i, j)\) with \(i < j\) and \(j\) lies on the path connecting \(0\) to \(i\))! In particular, for any inversion \((i, j)\) of our tree \(T\) with \(i < j\), if the predecessor of \(j\) is \(j'\), we claim that we may add \(\set{i, j'}\) to the graph (and this is an edge that cannot be in the tree \(T\)). One proves this inductively by showing that the search order of the vertices is preserved while adding any of these edges (as the search order uniquely determines the tree under this scheme). The critical observation is that if we are visiting the \(k\)th vertex in our search \(v_k\) and would normally be about to go to the next vertex \(v_{k+1}\), any added edges \(\set{v_k, j}\) must have \(j < v_{k+1}\), and this characterizes all possible edges added. Then, a similar manipulation shows

\[C_n(q) = \sum_{G \in \mc G_{n+1}} q^{\abs{E(G)} - n} = \sum_{T \in \mc T^\circ_{n+1}} (1+q)^{\abs{E''(T)}} = \sum_{T \in \mc T^\circ_{n+1}} (1+q)^{\inv(T)} = I_n(1+q)\]

This connects the \(q\)-analogues of our sequence with enumeration on connected graphs, which is super neat!

coda: Haiman and diagonal harmonics

parking functions have also started to appear in representation-theoretic contexts, which is simultaneously exciting and also for reasons that are a little scary. This connects back to Macdonald polynomials and \((q,t)\)-Catalan combinatorics and invokes some interesting algebraic geometry (specifically Hilbert schemes) which I don’t really want to fully unwrap here.

the punchline – one can define the space of diagonal harmonics as a set of invariant polynomials in \(x = (x_1, \dots, x_n)\) and \(y = (y_1, \dots, y_n)\) under an \(S_n\) action that permutes the \(x\)s and \(y\)s in the same way. In particular, when we define this space \(DH_n = \CC[x, y]^{S_n}\) in this way, the so-called \((n+1)^{n-1}\) conjecture is precisely that the dimension of this space is our fourth favorite sequence, \((n+1)^{n-1}\)!

Mark Haiman proved this by computing the multiplicity of various \(S_n\) representations in the bigraded components of \(DH_n\), or equivalently, when looking at the bivariate Hilbert series of \(DH_n\), the coefficients of certain symmetric functions. It turns out the best way to do this is in terms of the Macdonald polynomials \(H_\mu\), which naturally generalize the Schur polynomials to have two additional variables.⁴ (To be really technical, it was done in terms of the modified Macdonald polynomials \(\tilde H_\mu\), which are a plethystically-substituted⁵ version of these polynomials.) This was done using algebraic geometry methods akin to those used for the \(n!\) conjecture, describing the dimension/structure of a different \(S_n\)-invariant bigraded algebra.

Since there are \((n+1)^{n-1}\) parking functions and \((n+1)^{n-1}\) dimensions of this vector space, one might ask if one can match up parking functions and basis elements of this vector space – hence the representation-theoretic interpretation! There’s been progress in this direction – Haglund and Loehr conjectured an expression for the Hilbert series of \(DH_n\) as a sum over two statstics over parking functions, viewed as labeled Dyck paths as described above in our interlude. I think it’s been since proved as a result of work on the shuffle conjecture (in the realm of this Macdonald polynomial/\((q,t)\)-Catalan business)… but this starts to get into the weeds of more representation theory that’s a little beyond what I’m trying to dig into here, at least for now…

---

endnotes