Let the records of a permutation σ be its left-right minima, right-left minima, left-right maxima and right-left maxima. Conversely let a point (i, j) with j=σ(i) be an internal point of σ if it is not a record. Permutations without internal points have recently attracted attention under the name square permutations. We consider here the enumeration of permutations with a fixed number of internal points.We show that for each fixed i the generating function of permutations with i internal points with respect to the size is algebraic of degree 2. More precisely it is a rational function in the Catalan generating function. Our approach is constructive, yielding a polynomial uniform random sampling algorithm, and it can be refined to enumerate permutations with respect to each of the four types of records. © 2011 Elsevier B.V.
Disanto, D., Duchi, E., Rinaldi, S., Schaeffer, S. (2011). Permutations with few internal points. In Eurocomb 2011 (pp.291-296). Elsevier [10.1016/j.endm.2011.09.048].
Permutations with few internal points
Rinaldi S.;
2011-01-01
Abstract
Let the records of a permutation σ be its left-right minima, right-left minima, left-right maxima and right-left maxima. Conversely let a point (i, j) with j=σ(i) be an internal point of σ if it is not a record. Permutations without internal points have recently attracted attention under the name square permutations. We consider here the enumeration of permutations with a fixed number of internal points.We show that for each fixed i the generating function of permutations with i internal points with respect to the size is algebraic of degree 2. More precisely it is a rational function in the Catalan generating function. Our approach is constructive, yielding a polynomial uniform random sampling algorithm, and it can be refined to enumerate permutations with respect to each of the four types of records. © 2011 Elsevier B.V.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/27991
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo