Clusters, generating functions and asymptotics for consecutive patterns in permutations
Presented by Prof. Marc NOY
Type: Oral presentation
We use the cluster method to enumerate permutations avoiding consecutive patterns. We reprove and generalize in a unified way several known results and obtain new ones, including some patterns of length 4 and 5, as well as some infinite families of patterns of a given shape. By enumerating linear extensions of certain posets, we find a differential equation satisfied by the inverse of the exponential generating function counting occurrences of the pattern. We prove that for a large class of patterns, this inverse is always an entire function. We also complete the classification of consecutive patterns of length up to 6 into equivalence classes, proving a conjecture of Nakamura.