From "Noncrossing partitions in surprising locations" by Jon McCammond:

"Certain mathematical structures make a habit of reoccuring in the most diverse list of settings. Some obvious examples exhibiting this intrusive type of behavior include the Fibonacci numbers, the Catalan numbers, the quaternions, and the modular group. In this article, the focus is on a lesser known example: the noncrossing partition lattice. The focus of the article is a gentle introduction to the lattice itself in three of its many guises: as a way to encode parking functions, as a key part of the foundations of noncommutative probability, and as a building block for a contractible space acted on by a braid group.

The noncrossing partition lattice is a relative newcomer to the mathematical world. First defined and studied by Germain Kreweras in 1972 , it caught the imagination of combinatorialists beginning in the 1980s and has come to be regarded as one of the standard objects in the field. In recent years it has also played a role in areas as diverse as low-dimensional topology and geometric group theory as well as the noncommutative version of probability. Due no doubt to its recent vintage, it is less well-known to the mathematical community at large than perhaps it deserves to be, but hopefully this short paper will help to remedy this state of affairs."

Through the years, I've noted some guises of the NCPs:

1) Refined partitions of a polygon by nonintersecting line segments drawn between its vertices. These are enumerated in OEIS A134264, a natural refinement of the Narayana numbers A001263, whose row sums are the Catalan numbers A000108. (Similar to transforming $x$ to $x+1$ in the Narayana polynomials to obtain the f-polynomials for the associahedra, if $h_0$ is replaced by $x/(1+x)$ and the other $h_n$ by $( 1+x)^n$, the reversed f-polynomials (A033282, A086810) for the associahedra are obtained from the partition polynomials of A134264.)

2) Appropriately marked NCPs generate the partition polynomials that give the coefficients of the formal power series $f^{(-1)}(x)$ that is the compositional inverse of a formal power series $f(x)$, in terms of the coefficients of the power series for the shifted reciprocal $x/f(x)$ .

3) Number of Dyck paths of semilength $n$ whose ascent lengths form the $k$-th partition of the integer $n$ (cf. A125181).

4) Number of ordered trees with $n$ edges whose node degrees form the $k$-th partition of the integer n  (cf A125181)

5.) The $n$-th NCP partition polynomial multiplied by $n$ gives the number of terms in the homogeneous symmetric monomials generated by $[x(1) + x(2) + ... + x(n+1)]^n$ under the umbral mapping $x(m)^j = h_j ,$ for any $m$. This connects compositional inversion, Sheffer Appell sequences, and the Hirzebruch criterion for the Todd class.

6) The sequence of NCP polynomials form an Appell sequence as polynomials in a distinguished indeterminate, a special type of Sheffer polynomial sequence in the same family as the Bernoulli polynomials.

7) The NCP polynomials give the moments associated to the free cumulants in free probability theory. (Cf. "Three lectures on free probability" by Novak and LaCroix, and the Ebrahimi-Fard and Patras refs in A134264.)

8) There is a bijection between NCPs and primitive parking functions. (See Lemma 3.8 on p. 28 of Rattan, "Parking functions and other combinatorial structures.)

9) In the combinatorial Hopf algebras of symmetric polynomials/functions, Sym, presented in "Hopf algebras and the logarithm of the S-transform in free probability" by Mastnak and Nica, the polynomials $y_n$ are the NCPs with the elementary symmetric polynomials (ESPs, denoted by $e_n$) as their indeterminates. The relationship between the o.g.f., $E(x)$, of the ESPs and the o.g.f., $H(x)$, of the complete homogeneous symmetric polynomials (CSPs, denoted by $h_n$) is


and, since the $y_n$ by A134264 (link above) are also the coefficients of the inverse of $xH(-x)$, the $y_n$ when expressed in terms of the CSPs (cf. A263633) become the normalized signed partition polynomials of A133437 (with an index shift in the indeterminates and overall sign change for every other polynomial). These are the refined, signed face polynomials of the associahedra, the antipode of a Faa-di-Bruno-like Hopf algebra based on the refined Lah polynomials (A130561, normalized elementary Schur polynomials) and inversion of o.g.f.s rather than the refined Bell polynomials (A036040) and inversion of e.g.f.s. (More on these types of Hopf algebras in the MO-Q "Guises of the Stasheff polytopes" and "Hopf monoids and generalized permutahedra" by Aguiar and Ardila.)

What are some other guises of the NCPs?

  • 3
    $\begingroup$ The lattice of noncrossing partitions is isomorphic to the interval $[e,c]$ of the absolute order on the symmetric group between the identity element $e$ and a fixed Coxeter element $c$. This way of viewing noncrossing partitions is key in generalizing the notion to other types. $\endgroup$ – Sam Hopkins Aug 21 '19 at 21:30
  • 2
    $\begingroup$ This is by now very well known; a standard source is the monograph of Armstrong: arxiv.org/abs/math/0611106. $\endgroup$ – Sam Hopkins Aug 21 '19 at 21:41
  • 1
    $\begingroup$ In fact, what I said is also Lemma 4.3 in the first link you posted (the survey by Jon McCammond). $\endgroup$ – Sam Hopkins Aug 21 '19 at 21:46
  • 1
    $\begingroup$ Look up "Easy Quantum Groups" $\endgroup$ – JP McCarthy Sep 10 '19 at 20:55
  • 1
    $\begingroup$ See e.g. arxiv.org/pdf/1201.4723.pdf $\endgroup$ – JP McCarthy Sep 11 '19 at 8:52

Your Answer

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

Browse other questions tagged or ask your own question.