Parking functions of types A and B (Q1599525)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Parking functions of types A and B |
scientific article |
Statements
Parking functions of types A and B (English)
0 references
10 June 2002
0 references
A (type A) parking function is a sequence of positive integers \((a_1,\dots, a_n)\) such that its increasing re-arrangement \((b_1,\dots, b_n)\) satisfies \(b_i\leq i\). A (type B) parking function satisfies \(a_i\leq n\). Thus \((1,3,3)\) is of (type B) but not of (type A). A non-crossing partition of \([1,n]= (1,2,\dots,n)\) is a partition such that for no \(a< b< c< d\) do \(a\) and \(c\) belong to one block and \(b\) and \(d\) to some different block. \(\text{NC}_n\) is the lattice of non-crossing partitions of \([1,n]\) in the refinement order with Stanley's edge-labeling of \(\text{NC}_{n+1}\) providing a proof that maximal chains of \(\text{NC}_{n+1}\) are in one-one correspondence with (type A) parking functions. A non-crossing partition of \(\{-1,-2,-n,1,2,\dots, n\}\) under sign-change belongs to \(\text{NC}^B_N\). The author produces an alternative proof of Stanley's result via the natural embedding of \(\text{NC}_{n+1}\) in the Cayley graph of \(S_{n+1}\) and uses an analogous embedding of \(\text{NC}^B_N\) into the Cayley graph of \(W_n\), the hyper-octahedral group, to provide a parallel treatment of the (type B) case, and in both cases an elegant way to obtain the result given.
0 references
symmetric group
0 references
parking function
0 references
lattice of non-crossing partitions
0 references
refinement order
0 references
edge-labeling
0 references
maximal chains
0 references
Cayley graph
0 references