##
**
Some Statistics on the Hypercubes of Catalan Permutations
**

###
Filippo Disanto

Department of Biology

Stanford University

Stanford, CA 94305

USA

**Abstract:**

For a permutation σ of length 3, we define the oriented graph
*Q*_{n}(σ).
The graph *Q*_{n}(σ)
is obtained by imposing edge constraints
on the classical oriented hypercube *Q*_{n},
such that each path going
from 0^{n} to 1^{n} in
*Q*_{n}(σ)
bijectively encodes a permutation
of size *n* avoiding the pattern σ. The orientation of the edges
in
*Q*_{n}(σ)
naturally induces an order relation ≼_{σ}
among its nodes. First, we characterize ≼_{σ}.
Next, we
study several enumerative statistics on
*Q*_{n}(σ), 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**