2009/11/16 by Qin, Jing, Reidys, Christian M.
#05c10 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.0911.2960
In this paper, we introduce polynomial time algorithms that generate random k-noncrossing partitions and 2-regular, k-noncrossing partitions with uniform probability. A k-noncrossing partition does not contain any k 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 \it et al. \citeChen,Reidys:08tan, we interpret k-noncrossing partitions and 2-regular, k-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.