Journal of Integer Sequences, Vol. 18 (2015), Article 15.2.2

Some Statistics on the Hypercubes of Catalan Permutations

Filippo Disanto
Department of Biology
Stanford University
Stanford, CA 94305


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 0n to 1n 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.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000079 A000108 A000245 A000295 A001793 A009766 A038207 A047520 A065109.)

Received April 16 2014; revised version received November 11 2014; December 17 2014. Published in Journal of Integer Sequences, January 24 2015.

Return to Journal of Integer Sequences home page