Random 3-noncrossing partitions generation

In this paper, we introduce polynomial time algorithms that generate random $3$-noncrossing partitions and 2-regular, $3$-noncrossing partitions with uniform probability. A $3$-noncrossing partition does not contain any three mutually crossing arcs in its canonical representation and is $2$-regular if the latter does not contain arcs of the form $(i,i+1)$. Using a bijection of Chen et al. [PNAS, 2009, to appear], we interpret $3$-noncrossing partitions and $2$-regular, $3$-noncrossing partitions as restricted generalized vacillating tableaux. Furthermore, we interpret the tableaux as sampling paths of a Markov-processes over shapes and derive their transition probabilities.