For a permutation σ of length 3, we define the oriented graph Qn(σ). The graph Qn(σ) is obtained by imposing edge constraints on the classical oriented hypercube Qn, such that each path going from 0^n to 1^n in Qn(σ) bijectively encodes a permutation of size n avoiding the pattern σ. The orientation of the edges in Qn(σ) naturally induces an order relation ≼_σ among its nodes. First, we characterize ≼_σ. Next, we study several enumerative statistics on Qn(σ), including the number of intervals, the number of intervals of fixed length k, and the number of paths (or permutations) intersecting a given node.

Some statistics on the hypercubes of Catalan permutations

DISANTO, FILIPPO
2015

Abstract

For a permutation σ of length 3, we define the oriented graph Qn(σ). The graph Qn(σ) is obtained by imposing edge constraints on the classical oriented hypercube Qn, such that each path going from 0^n to 1^n in Qn(σ) bijectively encodes a permutation of size n avoiding the pattern σ. The orientation of the edges in Qn(σ) naturally induces an order relation ≼_σ among its nodes. First, we characterize ≼_σ. Next, we study several enumerative statistics on Qn(σ), including the number of intervals, the number of intervals of fixed length k, and the number of paths (or permutations) intersecting a given node.
Disanto, Filippo
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: http://hdl.handle.net/11568/849467
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact