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

Permutations with few internal points

DISANTO, FILIPPO;
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
Disanto, Filippo; Duchi, E; Rinaldi, F; Schaeffer, G.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/849455
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact