Is there a "local" algorithm which takes as its input a parking function and returns the non-crossing partition labelled by that sequence?

Background: A parking function is a sequence of positive integers which is a permutation of a sequence $a_1\leq \ldots \leq a_n$ satisfying $a_k \leq k$ for all $k$. In a 1996 article, Richard Stanley showed that there is a bijection between the set of parking functions and the set of maximal chains in the lattice of non-crossing partitions. He gives an algorithm that injectively assigns to each maximal chain a parking function, and then relies on the fact that the two sets have the same cardinality to deduce surjectivity. I'm asking whether in the meantime someone has found an algorithm that produces the inverse function.

By "local" I mean one that does not have as its first step to label all the maximal chains of non-crossing partitions.

  • $\begingroup$ I'd love to get a complete answer to that question as well. During my flight in the morning, I figured a way to construct this bijection, but it is not completely "local" in your sense. For a primitive parking function (i.e., one that is weakly increasing) there is a fairly standard way to produce the corresponding maximal chain in the noncrossing partition lattice. And for non-primitive parking functions, there is a way to reorganize the maximal chain of the corresponding primitive rearrangement. If you are interested, I will write a full answer containing the construction. $\endgroup$ – Christian Stump Apr 15 '12 at 9:25

I still hope there is a complete (and easy) answer to the question, but as mentioned in my comment above, and since no one else answered so far, I give a description of the inverse map that is not completely local, but still "better" than first labelling all chains in the noncrossing partition lattice. (I just worked it out briefly, so I am not saying this is the best way of doing it, but it is easy enough to be worked out in 30 min.)

A parking function is called primitive if it is weakly increasing. Every parking function can be obtained from a primitive parking function by a series of transpositions of consecutive numbers. E.g.

$$112355 \mapsto 121355 \mapsto 211355 \mapsto 213155 \mapsto 213515 \mapsto 213551.$$

We do not yet have seen here a definition of noncrossing partitions and maximal chains in the noncrossing partition lattice. So observe that a chain in the noncrossing partition lattice can be seen as factorizations of the long cycle $(1,2,\ldots,n) \in \mathcal{S}_n$ into a product of $n$ transpositions $(ij)$. The map from these factorizations to parking functions mentioned above is then the map $\phi$ sending $c = (i_1j_1) \ldots (i_nj_n)$ to the sequence $(i_1,\ldots,i_n)$. In Stanley's article, it is shown that $\phi(factorization)$ is indeed a parking function, and that this map is a bijection. To obtain $\psi := \phi^{-1}$ we must therefore start with a sequence $(i_1,\ldots,i_n)$ and turn it into a factorization $c = (i_1j_1) \ldots (i_nj_n)$.

We do this in two steps: first, we define $\psi$ for primitive parking functions, and then obtain $\psi$ for general parking functions by a sequence of transpositions of factors $(i_kj_k)(i_{k+1}j_{k+1}) \mapsto (i_{k+1}j_{k+1})(i_k\tilde j_k)$, such that $$(i_kj_k)(i_{k+1}j_{k+1}) = (i_{k+1}j_{k+1})(i_k\tilde j_k).$$ Observe that this uniquely determines $\tilde j_k$, and that this is not a valid procedure for any two transpositions. Nonetheless, this works for sequences coming from parking functions.

Let $seq = (i_1,\ldots,i_n)$ be a primitive parking function. $\psi(seq)$ is then given by sending the last $1$ in $seq$ to the transposition $(12)$. Afterwards, send the last $i \in 1,2$ to $(i,3)$, then the last $i \in 1,2,3$ to $(i,4)$ and so on. For example, replacing letters in $112355$ in this way gives $$ \begin{align*} 112355 &\mapsto 1\ (12)\ 2355 \mapsto 1\ (12)(23)\ 355 \mapsto 1\ (12)(23)(34)\ 55 \newline &\mapsto (15)(12)(23)(34)\ 55 \mapsto (15)(12)(23)(34)\ 5\ (56) \newline &\mapsto (15)(12)(23)(34)(57)(56) \end{align*} $$ It is straightforward to check that this yields indeed a factorization of the long cycle, and by construction, we have $\phi(\ (15)(12)(23)(34)(57)(56)\ ) = 112355$, as desired.

Now, to obtain the parking function $211553$, we first interchange positions $2$ and $3$, and interchange the factors such that $(i_2j_2)(i_3j_3) = (i_3j_3)(i_2\tilde j_2)$ so we obtain

$$ \psi( 121355 ) = (15)(23)(13)(34)(57)(56).$$ Here, the third factor became the second, and the second factor $(12)$ turns into $(13)$. We keep going with this procedure and obtain $$ \begin{align*} \psi(112355) &= (15)(12)(23)(34)(57)(56) \newline \psi(121355) &= (15)(23)(13)(34)(57)(56) \newline \psi(211355) &= (23)(15)(13)(34)(57)(56) \newline \psi(213155) &= (23)(15)(34)(14)(57)(56) \newline \psi(213515) &= (23)(15)(34)(57)(14)(56) \newline \psi(213551) &= (23)(15)(34)(57)(56)(14). \end{align*} $$ This completes the construction. I didn't present that proof that both steps in the procedure actually work, but they should in fact do.

If someone wants sees a direct way of computing $\psi(213551)$, please post it! And if I should clarify anything, or if someone finds mistakes, please let me know (I haven't yet gone though all details to prove that this procedure works, and I would only do it if this is not yet known, and people are interested).

Best, Christian

  • $\begingroup$ Thanks for the answer, Christian. I was trying to write a program to do some homology computations. In the meantime I found a mathematica package called posets.m, by Curtis Greene and students, that generates the non-crossing partition lattice in a convenient form, from which one can, with some work, generate all maximal chains and their labels. In case that info might be useful to someone ... The algorithm for primitive parking functions I also found on the web, in the thesis of A. Rattan (Waterloo). And I guess ${\tilde j}_2$ can be found by the usual conjugation routine in the $S_n$. $\endgroup$ – Michael Falk May 9 '12 at 15:39
  • $\begingroup$ You can also do all these computations in Sage, where I implemented the noncrossing partition lattice. If you are interested, I will prepare a worksheet that does compute the noncrossing partition lattice and make it publicly available at sage.lacim.uqam.ca. It basically looks like W = CoxeterGroup(['A']) NC = W.noncrossing_partition_lattice() chains = NC.maximal_chains() + some little work for getting the edge labels right. $\endgroup$ – Christian Stump May 10 '12 at 5:20
  • $\begingroup$ That would be great - all I can do with Mathematica is type A. $\endgroup$ – Michael Falk May 14 '12 at 20:17
  • 1
    $\begingroup$ For completeness, I also post the public worksheet here: sage.lacim.uqam.ca/home/pub/14 $\endgroup$ – Christian Stump Jun 12 '12 at 6:58

P. Biane. Parking functions of types A and B Electron. J. Combin. 9 (2002), no. 1, Note 7, 5 pp.


I think your best bet might be to take a route through something else. For example, parking functions have an easy map to labelled Dyck Paths and those IIRC have an easy map to non-crossing partitions. Or any of the other Catalan-type structures with an appropriate modification. Parking Functions and Generalized Catalan Numbers might be of some help


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.