Some Statistics on the Hypercubes of Catalan Permutations
Department of Biology
Stanford, CA 94305
For a permutation σ of length 3, we define the oriented graph
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
bijectively encodes a permutation
of size n avoiding the pattern σ. The orientation of the edges
naturally induces an order relation ≼σ
among its nodes. First, we characterize ≼σ.
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,
(Concerned with sequences
Received April 16 2014; revised version received November 11 2014; December 17 2014.
Published in Journal of Integer Sequences, January 24 2015.
Journal of Integer Sequences home page