Some Statistics on the Hypercubes of Catalan Permutations

Filippo Disanto Department of Biology Stanford University Stanford, CA 94305 USA

                     fdisanto@stanford.edu

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.

1 Introduction

In this paper, we study several structural and enumerative properties of the classical oriented hypercube Q_{n} when the hypercube satisfies certain additional edge constraints. The constraints are given in terms of permutation patterns, focusing on patterns of length 3.

The connection between the oriented hypercube Q_{n} defined over the set of n-binary words Σ^{n} and the set of permutations of size n is determined by considering each path in Q_{n} going from 0^{n} to 1^{n} as a permutation. There are exactly n! paths from 0^{n} to 1^{n} and each one of these uniquely determines a permutation. More precisely, the permutation π_{p} associated with the path p has the entry i placed in position j if the i-th step of p creates an entry 1 in position j. See (3) and (4).

Taking only those permutations that avoid a pattern σ of length 3, it is possible to characterize those edges of Q_{n} that need to be removed to maintain the correspondence paths-permutations. In this way, a new ordered structure, Q_{n}(σ), can be defined, where, as in Q_{n}, the partial order in Q_{n}(σ) is naturally induced by the orientation of the edges (Fig. 1).

According to the classical definition of pattern avoidance, the set of permutations of size n that avoid a pattern σ is denoted by Av_{n}(σ) and, when |σ| = 3, the cardinality of Av_{n}(σ) is given by the well-known [10] sequence of Catalan numbers

c_{n} = |Av_{n}(σ)| = \frac{1}{n + 1}\binom{2n}{n};  (1)

see sequence \underline{A000108} of [9]. Several authors (see [2] and references therein) have focused on the bijective and enumerative properties of these permutations. To the best of our knowledge, their hypercube graph structure has not been investigated.

1.1 Motivation

Our general aim is to introduce — and hopefully motivate further studies of — certain subgraphs Q_{n}(σ) of the oriented hypercube Q_{n} that can be defined for particular sets of permutation patterns σ. As a case study, we investigate patterns of length three for which Q_{n}(σ) relates to the c_{n} permutations of Av_{n}(σ).

By linking hypercubes to classes of permutations, we can explore how permutation pattern constraints can affect the different combinatorial statistics defined over the poset and oriented graph Q_{n}. In this spirit, we study the number of intervals (Section 3) and number of paths intersecting a given node (Section 4) in the oriented graphs Q_{n}(σ). We consider the number of intervals in order to investigate the underlying poset structure of Q_{n}(σ) and compare it with that of the classic hypercube. The second statistic measures instead how the symmetries of the hypercube Q_{n} are modified in Q_{n}(σ).

The effect of the introduced constraints is quite strong, both from a quantitative and a qualitative point of view. For instance, we show that the expectation of the number of nodes that lie at Hamming distance k and above a randomly selected node depends on both k and n in the unconstrained Q_{n}, whereas in Q_{n}(σ) it depends only on k if n is large enough. Another interesting new structural property of the oriented hypercube that emerges when pattern constraints are imposed is the loss of symmetry. More precisely, whereas in the unconstrained case Q_{n} each node of given rank D (= number of 0’s) is intersected by a fixed number n!/\binom{n}{D} of paths, other parameters (Table 1) become important when pattern avoidance is considered. Section 4 is indeed dedicated to the computation, for σ ∈ {123, 132}, of the number of paths/permutations that intersect a node w in Q_{n}(σ). This value does not only depend on the rank of the node and it is strongly affected by the choice of the pattern σ.

Due to their topological structure, hypercubes find applications in the modelling of physical phenomena, with examples ranging from computer science to evolutionary biology. Changing the geometric structure of a model can be of help in understanding how results can be affected by deviations from the standard scenario. For instance, in evolutionary biology, the oriented graph structure of Q_{n} is commonly used to model accessibility phenomena in random fitness landscapes [5, 6]: paths through the nodes of the hypercube represent the possible evolutionary histories of a gene. In the model, the gene can be affected by binary mutations 0, 1 at its n positions (loci). Each node of Q_{n} is assigned a random variable that determines the fitness value of that particular outcome. Researchers study the probability that there is an accessible (i.e. fitness increasing) path from a global minimum (typically 0^{n}) to a global maximum (typically 1^{n}). Recently, investigators have explored the relationships of graph topology to the availability of accessible paths by defining fitness landscapes over different geometric structures (e.g., [8]). The enumerative results provided in this paper can be used in the accessibility computations for models of fitness landscapes defined over the constrained hypercubes Q_{n}(σ).

Finally, it is worth mentioning that the approach presented here to define Q_{n}(σ) for patterns σ of length 3 can be extended to include other permutation patterns (Section 6).

1.2 Summary of the results

In this study, we focus on patterns σ = 132, 123 as representatives of the two clusters {132, 231, 312, 213} and {123, 321} that are not equivalent when considered under the standard operators of mirror image, complement, and inverse.

For each pattern σ, in Section 2 we define the oriented (sub)graph Q_{n}(σ), which is obtained by removing particular edges from the classic oriented hypercube Q_{n}. For both σ = 132, 123 the number of nodes in the graph Q_{n}(σ) is 2^{n} (as in Q_{n}) and the number of paths going from 0^{n} to 1^{n} is given by the n-th Catalan number c_{n}. Indeed, each path of Q_{n}(σ) encodes a permutation of Av_{n}(σ). However, though the considered two classes of permutations Av_{n}(132) and Av_{n}(123) are equinumerous, Q_{n}(132) and Q_{n}(123) are not isomorphic graphs. We conclude the section by characterizing the order relation ⪯_{σ} induced on the nodes of Q_{n}(σ) by the orientation of the edges.

In Section 3, we study e_{n}, the number of intervals, and e_{n,k}, the number of intervals of fixed length k, in the posets (Q_{n}(σ), ⪯_{σ}). These statistics are independent of the pattern σ and they thus show a new common feature of permutations avoiding patterns of length 3. We provide a closed formula for e_{n},

e_{n} = 2^{n−3}(n^{2} + 3n + 8).

We determine a recursion on k for the value e_{n,k} (24). For instance, if 0 ≤ k ≤ 5, we find

e_{n,0} = 1 · 2^{n}
e_{n,1} = 2 · 2^{n} − n − 2
e_{n,2} = 3 · 2^{n} − n^{2} − 2n − 3
e_{n,3} = 4 · 2^{n} − \frac{1}{2}n^{3} − \frac{1}{2}n^{2} − 3n − 4
e_{n,4} = 5 · 2^{n} − \frac{1}{6}n^{4} + \frac{1}{6}n^{3} − \frac{11}{6}n^{2} − \frac{19}{6}n − 5
e_{n,5} = 6 · 2^{n} − \frac{1}{24}n^{5} + \frac{1}{6}n^{4} − \frac{23}{24}n^{3} − \frac{2}{3}n^{2} − \frac{9}{2}n − 6.

In general, we show that for every k

e_{n,k} = (k + 1) · 2^{n} + O(n^{k}).

In Section 4, we find closed formulas to compute T_{σ}(w), the number of paths (or permutations) intersecting a given node w ∈ Q_{n}(σ). In the notation of Table 1, we find

T_{132}(w) = \binom{D + d}{D} · \frac{D − d + 1}{D + 1} · ∏_{i=0}^{ℓ} c_{u_{i}},

T_{123}(w) = \binom{D + d}{D} · \frac{D − d + 1}{D + 1} · \binom{U + u}{U} · \frac{U − u + 1}{U + 1}.

(2)

In general, T_{132}(w) ≠ T_{123}(w), and we show by simulations that requiring w to satisfy certain constraints can increase or decrease the value of T_{132}(w) with respect to the value of T_{123}(w).

We conclude in Section 5 by introducing a new problem related to path intersection in Q_{n}(σ) and solving some preliminary instances.

2 Constrained hypercubes

2.1 Hypercube and permutations

We let Q_{n} denote the classic oriented hypercube on the set of binary words Σ^{n} = {0, 1}^{n}. Each node of the oriented graph Q_{n} is a binary word of length n. Q_{n} has exactly 2^{n} nodes.

If w_{1}, w_{2} ∈ Σ^{n}, their Hamming distance h(w_{1}, w_{2}) is defined as the number of positions at which the two strings w_{1}, w_{2} are different. For instance, h(0010, 1001) = 3 because at the first, third and fourth position the two considered words do not match each other.

If w_{1}, w_{2} ∈ Σ^{n}, we find an oriented edge of Q_{n} going from w_{1} to w_{2} if and only if the Hamming distance h(w_{1}, w_{2}) = 1 and h(w_{1}, 0^{n}) < h(w_{2}, 0^{n}). The edge orientation naturally induces an order relation ⪯ among the nodes of Q_{n}. We thus consider Q_{n} as a poset in what follows.

With respect to the strict order relation ≺, the number of distinct increasing paths through the nodes of Q_{n} from 0^{n} to 1^{n} is given by n!. If S_{n} denotes the set of permutations of size n, the bijective correspondence holding between a path p of Q_{n} and a permutation π_{p} ∈ S_{n} is sketched in the following example given for size n = 5:

p = 00000 → 00010 → 01010 → 01011 → 11011 → 11111  (3)
π_{p} = 00000 → 00010 → 02010 → 02013 → 42013 → 42513.  (4)

The rule that leads from p to π_{p} is such that, at each step, we place the lowest available entry in the permutation in the position specified by the new entry 1 in the path.

2.1.1 Edge constraints of the hypercube

For each pattern σ ∈ {132, 123}, we define the oriented graph Q_{n}(σ) as a constrained version of Q_{n} such that the previously described bijection p ↦ π_{p} maps paths of Q_{n}(σ) onto permutations of Av_{n}(σ). For σ = 132 and σ = 123 the definition of Q_{n}(σ) is given as follows:

(i) The constrained hypercube Q_{n}(132) (Fig. 1 (right)) is obtained by removing from Q_{n} those edges w_{1} → w_{2} connecting two words w_{1} ≺ w_{2} such that there exist indices j_{1} < j_{2} < j_{3} with w_{2}(j_{3}) = 1, w_{1}(j_{3}) = 0, w_{1}(j_{1}) = 1, and w_{1}(j_{2}) = 0. In other words, we remove edges of type

w_{1} = α 1 β 0 γ 0 δ ↛ α 1 β 0 γ 1 δ = w_{2}.

(ii) The constrained hypercube Q_{n}(123) (Fig. 1 (left)) is obtained by removing from Q_{n}

those edges of type

w_{1} = α 1 β 0 γ 0 δ ↛ α 1 β 1 γ 0 δ = w_{2}.

Note that, in both cases (i) and (ii), all the nodes in Σ^{n}\{0^{n}, 1^{n}} have outdegree and indegree greater than or equal to one in Q_{n}(σ). Therefore, for any fixed σ ∈ {132, 123}, each node of Σ^{n} has at least one path of Q_{n}(σ) that intersects it. In particular, the set of nodes of Q_{n}(σ) corresponds to the entire set of binary words Σ^{n} as it is in Q_{n}.

2.2 Structural properties of the constrained hypercubes

Inspection of Fig. 1 (circled nodes) shows that the two depicted graphs are not isomorphic. Indeed, suppose there exists an isomorphism ϕ : Q_{4}(123) ↦ Q_{4}(132). The isomorphism ϕ would give ϕ(0000) = 0000 and ϕ(1000) = 1000, because 1000 is the only node of outdegree 1 that covers 0000. Furthermore, because 1001 (resp., 1100) is the only node that covers

Figure 1: The oriented graphs Q_{4}(123) (left) and Q_{4}(132) (right). There are c_{4} = 14 possible paths from 0000 to 1111 following the orientation specified by the arrows. Circled nodes result in two non-isomorphic regions. This fact shows that Q_{4}(123) is not isomorphic to Q_{4}(132) (see text in Section 2.2).

1000 in Q_{4}(123) (resp., Q_{4}(132)), we would have ϕ(1001) = 1100. Besides covering node 1000, node 1001 (resp., 1100) covers node 0001 (resp., 0100) in Q_{4}(123) (resp., Q_{4}(132)). Therefore, we would obtain

ϕ(0001) = 0100.  (5)

At the same time, equality (5) is not compatible with an isomorphism ϕ because node 0001 of Q_{4}(123) has outdegree 3, whereas node 0100 of Q_{4}(132) has outdgree 2. It follows that the two graphs Q_{n}(132) and Q_{n}(123) are not in general isomorphic.

2.2.1 Order relation in Q_{n}(132) and Q_{n}(123)

As for the classic hypercube Q_{n}, when σ ∈ {132, 123}, the orientation of the edges in Q_{n}(σ) determines an order relation ⪯_{σ} among the 2^{n} nodes of Q_{n}(σ). By the definition of Q_{n}(σ), the order relation ⪯_{σ} is clearly a restriction of ⪯. It is interesting to note that, even if the two graphs Q_{n}(132) and Q_{n}(123) are not in general isomorphic (Fig. 1), there is a duality holding between the order relations ⪯_{132} and ⪯_{123}. The duality can be shown introducing some further notation as follows.

Let w be a binary word. We denote by D = D(w) the total number of entries 0 in w and we denote by d = d(w) ≤ D the length of the maximal (left) prefix of w containing only 0’s (Table 1). We define the word w^{(i)} (D ≥ i ≥ 0) as the word obtained by replacing the first i entries 0 of w with 1. For instance, given w = 001101, we have w^{(0)} = 001101, w^{(1)} = 101101, w^{(2)} = 111101, and w^{(3)} = 111111.

The definition of w^{(i)} can be extended to i ≤ 0 as follows: if D ≥ j ≥ 0, then w^{(−j)} is the word obtained by replacing the last j entries 0 of w with 1. Taking as above w = 001101, we have w^{(0)} = 001101, w^{(−1)} = 001111, w^{(−2)} = 011111, and w^{(−3)} = 111111.

Table 1: Key parameters defined over the words in Σ^{n}. For instance, if w = 00101110, then d = 2, u = 0, ℓ = 2, u_{1} = 1, and u_{2} = 3, whereas, setting w = 1101011, we obtain d = 0, u = 2, ℓ = 3, u_{1} = 2, u_{2} = 1, and u_{3} = 2.

D(w)  number of 0’s in w

d(w) length of the maximal prefix of w containing only 0’s

U(w)  number of 1’s in w

u(w) length of the maximal suffix of w containing only 1’s

u_{i}(w) length of the i-th (from left to right) block of 1’s in w

ℓ(w)  number of blocks of consecutive 1’s in w

With this notation, the next result describes the order relation ⪯_{σ} existing among the nodes of Q_{n}(σ) as it is induced by the orientation of the edges of Q_{n}(σ).

Proposition 1. We have the following:

(i) If w_{1}, w_{2} ∈ Σ^{n} and d = d(w_{1}), then w_{1} ⪯_{132} w_{2} if and only if

w_{2} = w · (w_{1}(d + 1)w_{1}(d + 2) ⋯ w_{1}(n))^{(i)},  (6)

where i ≥ 0, w is any word of length d, and w_{1}(m) denotes the m-th letter of w_{1}.

(ii) If w_{1}, w_{2} ∈ Σ^{n} and d = d(w_{1}), then w_{1} ⪯_{123} w_{2} if and only if

w_{2} = w · (w_{1}(d + 1)w_{1}(d + 2) ⋯ w_{1}(n))^{(−j)},  (7)

where j ≥ 0, w is any word of length d, and w_{1}(m) denotes the m-th letter of w_{1}.

Proof. The result follows directly from the characterization of the covering relation in the posets Q_{n}(132) and Q_{n}(123). In Q_{n}(132) (resp., Q_{n}(123)), a node v_{2} covers a node v_{1} if and only if v_{2} can be obtained from v_{1} either by replacing any 0 belonging to the maximal prefix of 0’s in v_{1} with an entry 1 or by replacing the first 0 (resp., last 0) to the right of the leftmost 1 in v_{1} with an entry 1.

Remark 2. As a corollary, Proposition 1 allows to define an inductive procedure ψ that, given a path p of Q_{n}(132), creates a dual path ψ(p) of Q_{n}(123). This mapping is in fact a bijection between Av_{n}(132) and Av_{n}(123) that, as far as we know, has not been previously described in the framework of hypercubes.

Given a path p of Q_{n}(132), such as

p = w_{0} → w_{1} → ⋯ → w_{n},

we define

ψ(p) = w′_{0} → w′_{1} → ⋯ → w′_{n}

inductively as follows. Set w′_{0} = 0^{n} and assume that we have already defined w′_{i} for each 0 ≤ i ≤ j. According to Proposition 1 (i), the word w_{j+1} that covers w_{j} is obtained from w_{j} as

w_{j+1} = w · (w_{j}(d + 1)w_{j}(d + 2) ⋯ w_{j}(n))^{(+i)},  (8)

where d = d(w_{j}), w is a word of length d such that h(w, 0^{d}) ≤ 1, and i = 1−h(w, 0^{d}) ∈ {0, 1}. Given (8), we set

w′_{j+1} = w · (w′_{j}(d + 1) w′_{j}(d + 2) ⋯ w′_{j}(n))^{(−i)},  (9)

where w is as in (8).

In particular, because d(w_{0}) = d(0^{n}) = n, we have w_{1} = w′_{1} and, more in general, d(w_{j}) = d(w′_{j}) for all 0 ≤ j ≤ n. Therefore, because the word w placed at the beginning of w′_{j+1} has length d(w′_{j}), the word w′_{j+1} covers w′_{j} in agreement with statement (ii) of Proposition 1.

The bijection ψ acts on single paths, and it does not imply isomorphism properties of the two considered constrained hypercubes. In particular, if a pair of paths (p_{1}, p_{2}) share (or do not share) certain nodes in Q_{n}(132), the same does not necessarily hold in Q_{n}(123) for the pair (ψ(p_{1}), ψ(p_{2})). For instance, (2341, 1234) do not intersect in Q_{4}(132), but both ψ(2341) = 2431 and ψ(1234) = 1432 pass through the node 1011 in Q_{4}(123).

3 Number of intervals

In this section, we study the number of intervals of Q_{n}(σ). We are thus interested in those pairs (w_{1}, w_{2}) ∈ Σ^{n} × Σ^{n} with w_{1} ⪯_{σ} w_{2}. By Proposition 1, the statistic number of intervals does not depend on the pattern σ and we denote by e_{n} the number of intervals in Q_{n}(σ) for each σ ∈ {132, 123} .

3.1 Enumeration of e_{n}

Fix a word w_{1}. By Proposition 1, the number of words w_{2} greater than or equal to w_{1} in Q_{n}(σ) is given by

2^{d}(D − d + 1),  (10)

where D = D(w_{1}) and d = d(w_{1}).

Summing over all possible words w_{1}, e_{n} can be computed as

e_{n} = 2^{n} + ∑_{D=0}^{n−1} ∑_{d=0}^{D} 2^{d}(D − d + 1)\binom{n − d − 1}{n − D − 1}.  (11)

The sequence (e_{n})_{n≥1} starts as

3, 9, 26, 72, 192, 496, 1248, 3072, 7424, 17664.

Furthermore, observe that

ẽ_{n} = e_{n} − 2^{n} = ∑_{D=0}^{n−1} ∑_{d=0}^{D} 2^{d}(D − d + 1)\binom{n − d − 1}{n − D − 1}  (12)

counts the number of strict intervals of Q_{n}(σ). Strict intervals are those pairs (w_{1}, w_{2}) with w_{1} ≺_{σ} w_{2}.

The next proposition gives a closed formula for ẽ_{n} (and thus for e_{n}).

Proposition 3. For all n ≥ 1, we have

ẽ_{n} = ∑_{D=0}^{n−1} ∑_{d=0}^{D} 2^{d}(D − d + 1)\binom{n − d − 1}{n − D − 1} = 2^{n−3}(n^{2} + 3n).

Proof. Observe that by performing the substitution A = n − d and B = n − D, we obtain

ẽ_{n} = 2^{n} ∑_{B=1}^{n} ∑_{A=B}^{n} (\frac{1}{2})^{A} (A − B + 1)\binom{A − 1}{B − 1}.

By induction on n, we have

ẽ_{n} = 2^{n} [∑_{B=1}^{n−1} [∑_{A=B}^{n−1} (\frac{1}{2})^{A} (A − B + 1)\binom{A − 1}{B − 1}] + (\frac{1}{2})^{n} (n − B + 1)\binom{n − 1}{B − 1}] + 1

= 2ẽ_{n−1} + 2^{n} [∑_{B=1}^{n−1} (\frac{1}{2})^{n} (n − B + 1)\binom{n − 1}{B − 1}] + 1

= 2ẽ_{n−1} + 2^{n} (\frac{1}{4} − 2^{−n} + \frac{n}{4}) + 1
= 2ẽ_{n−1} + 2^{n−2}(n + 1)
= 2 · 2^{n−4}((n − 1)^{2} + 3(n − 1)) + 2^{n−2}(n + 1) = 2^{n−3}(n^{2} + 3n).

This concludes the proof.

Proposition 3 shows that (ẽ_{n})_{n} provides a new interpretation of sequence \underline{A001793} of [9]. Furthermore, we have the following corollary.

Corollary 4. A node of Q_{n}(σ) has on average

\frac{ẽ_{n}}{2^{n}} = \frac{n^{2} + 3n}{8}

nodes strictly above it.

It is interesting to observe that, in the unconstrained hypercube Q_{n}, the number of intervals w_{1} ⪯ w_{2} is given by

∑_{D=0}^{n} 2^{D}\binom{n}{D} = 3^{n}.  (13)

Thus, on average, a random node of Q_{n} has an exponential

\frac{3^{n} − 2^{n}}{2^{n}} ∼ (3/2)^{n}  (14)

number of nodes strictly above it.

3.2 The number of intervals of given length k

In this section, we refine our previous results by considering the number of intervals with length equal to k; i.e., we count those word pairs (w_{1}, w_{2}) such that w_{1} ⪯_{σ} w_{2} and h(w_{1}, w_{2}) = k. We denote by e_{n,k} the number of intervals of length k, and so e_{n} = ∑_{k=0}^{n} e_{n,k}. Note that Proposition 1 ensures, also in this case, that the statistic e_{n,k} does not depend on the pattern σ ∈ {132, 123}.

By (6) and (7), for a given word w_{1}, the number of words w_{2} greater than or equal to w_{1} in Q_{n}(σ) and such that h(w_{1}, w_{2}) = k is given by

∑_{i=0}^{D−d} \binom{d}{k − i},  (15)

where D = D(w_{1}) and d = d(w_{1}).

Indeed, in the notation of Proposition 1, if w_{2} is obtained from w_{1} as

w_{2} = w · (w_{1}(d + 1)w_{1}(d + 2) ⋯ w_{1}(n))^{(i)},  (16)

then their Hamming distance k = h(w_{1}, w_{2}) equals the sum of i and U(w), the latter being the number of entries in w equal to 1. That is, from (16) we have

k = h(w_{1}, w_{2}) = i + U(w)

Table 2: Values of e_{n,k} for 1 ≤ n ≤ 10 and 0 ≤ k ≤ 10.
e_{n,k}  k
0  1  2  3  4  5  6  7  8 9 10
n = 1  2  1  0  0  0  0  0  0  0 0 0
n = 2  4  4  1  0  0  0  0  0  0 0 0
n = 3  8  11  6  1  0  0  0  0  0 0 0
n = 4 16  26  21  8  1  0  0  0  0 0 0
n = 5 32  57  58  34  10  1  0  0  0 0 0
n = 6 64 120 141 108 50  12  1  0  0 0 0
n = 7 128 247 318 291 180 69  14  1  0 0 0
n = 8 256 502 685 708 535 278 91 16 1 0 0
n = 9 512 1013 1434 1612 1406 906 406 116 18 1 0
n = 10 1024 2036 2949 3512 3400 2568 1442 568 144 20 1

and (15) easily follows. Note that if D < k — that is, there are not enough 0’s in w_{1} — then formula (15) returns 0 because k − i ≥ k − (D − d) = d + (k − D) > d.

Summing over all possible nodes w_{1} of Q_{n}(σ), we thus obtain

e_{n,k} = \binom{n}{k} + ∑_{D=0}^{n−1} ∑_{d=0}^{D} \binom{n − d − 1}{n − D − 1} ∑_{i=0}^{D−d} \binom{d}{k − i}.  (17)

Using the sum in (17), we can compute the first terms of the sequences ((e_{n,k})_{n})_{k}. These terms are shown in the table 2 for 1 ≤ n ≤ 10 and 0 ≤ k ≤ 10. Note that the first column corresponds to entry \underline{A000079} of [9] while the second and the third appear respectively as sequences \underline{A000295} (Eulerian numbers) and \underline{A047520}.

Using (17), we can write that ∀k ≥ 0 and ∀n ≥ k + 1

e_{n,k+1} − e_{n,k} = \binom{n}{k + 1} − \binom{n}{k} + ∑_{D=0}^{n−1} ∑_{d=0}^{D} \binom{n − d − 1}{n − D − 1} [\binom{d}{k + 1} − \binom{d}{k − (D − d)}]

= \binom{n}{k + 1} − \binom{n}{k} + a_{n,k} − b_{n,k},  (18)

where, with 1 ≤ k + 1 ≤ n,

a_{n,k} ≡ ∑_{D=0}^{n−1} ∑_{d=0}^{D} \binom{n − d − 1}{n − D − 1}\binom{d}{k + 1} = 2^{n} − ∑_{i=0}^{k+1} \binom{n}{i} and  (19)

b_{n,k} ≡ ∑_{D=0}^{n−1} ∑_{d=0}^{D} \binom{n − d − 1}{n − D − 1}\binom{d}{k − (D − d)} = (n − k)\binom{n}{k}.  (20)

To prove the equality in (19), observe that

a_{n,k} = ∑_{D=0}^{n−1} ∑_{d=0}^{n−1} \binom{n − d − 1}{n − D − 1}\binom{d}{k + 1} = ∑_{d=0}^{n−1} \binom{d}{k + 1} ∑_{D=0}^{n−1} \binom{n − d − 1}{n − D − 1}

= ∑_{d=0}^{n−1} \binom{d}{k + 1} ∑_{D=d}^{n−1} \binom{n − d − 1}{n − D − 1} = ∑_{d=0}^{n−1} \binom{d}{k + 1}2^{n−d−1}

= 2^{n−1} ∑_{d=k+1}^{n−1} \binom{d}{k + 1} (\frac{1}{2})^{d}  (21)

Thus, from (21), the recursion

a_{n,k} = 2a_{n−1,k} + \binom{n − 1}{k + 1}.  (22)

Now, by induction on n, assuming that (19) holds for a_{n−1,k}, by substituting in (22) we have

a_{n,k} = 2a_{n−1,k} + \binom{n − 1}{k + 1} = 2 (2^{n−1} − ∑_{i=0}^{k+1} \binom{n − 1}{i}) + \binom{n − 1}{k + 1}

= 2^{n} − ∑_{i=0}^{k+1} \binom{n − 1}{i} − ∑_{i=0}^{k} \binom{n − 1}{i} = 2^{n} − [∑_{i=0}^{k+1} \binom{n}{i} − \binom{n − 1}{i − 1}] − ∑_{i=0}^{k} \binom{n − 1}{i}

= 2^{n} − ∑_{i=0}^{k+1} \binom{n}{i} − [∑_{i=0}^{k} \binom{n − 1}{i} − ∑_{i=0}^{k+1} \binom{n − 1}{i − 1}] = 2^{n} − ∑_{i=0}^{k+1} \binom{n}{i}

Checking (19) for a_{k+1,k} completes the proof. To prove the equality in (20), note that

b_{n,k} = ∑_{D=k}^{n−1} ∑_{d=0}^{D} \binom{n − d − 1}{n − D − 1}\binom{d}{k − (D − d)}.

Thus, setting A = n − d and B = n − D, we have the recursion

b_{n+1,k} = ∑_{B=1}^{n+1−k} ∑_{A=B}^{n+1} \binom{A − 1}{B − 1}\binom{n + 1 − A}{k − A + B}

= [∑_{B=1}^{n−k} ∑_{A=B}^{n+1} \binom{A − 1}{B − 1}\binom{n + 1 − A}{k − A + B}] + ∑_{A=B=n+1−k}^{n+1} \binom{A − 1}{n − k} · 1

= \binom{n + 1}{k} + ∑_{B=1}^{n−k} ∑_{A=B}^{n+1} \binom{A − 1}{B − 1}\binom{n + 1 − A}{k − A + B}

= \binom{n + 1}{k} + [∑_{B=1}^{n−k} ∑_{A=B}^{n} \binom{A − 1}{B − 1}\binom{n + 1 − A}{k − A + B}] + ∑_{B=1}^{n−k} \binom{n}{B − 1}\binom{0}{k − n − 1 + B}

= \binom{n + 1}{k} + ∑_{B=1}^{n−k} ∑_{A=B}^{n} \binom{A − 1}{B − 1} [\binom{n − A}{k − A + B} + \binom{n − A}{k − 1 − A + B}]

= \binom{n + 1}{k} + b_{n,k} + ∑_{B=1}^{n−k} ∑_{A=B}^{n} \binom{A − 1}{B − 1}\binom{n − A}{k − 1 − A + B}

= \binom{n + 1}{k} + b_{n,k} + [ ∑_{B=1}^{n−(k−1)} ∑_{A=B}^{n} \binom{A − 1}{B − 1}\binom{n − A}{k − 1 − A + B}] − ∑_{A=B=n+1−k}^{n} \binom{A − 1}{n − k} · 1

= \binom{n + 1}{k} + b_{n,k} + b_{n,k−1} − \binom{n}{k − 1} = b_{n,k} + b_{n,k−1} + \binom{n}{k}.  (23)

Now, by induction on n and k, assuming that (20) holds for b_{n,k} and b_{n,k−1}, by substituting in (23),

b_{n+1,k} = (n − k)\binom{n}{k} + (n − k + 1)\binom{n}{k − 1} + \binom{n}{k}
= (n − k) [\binom{n}{k} + \binom{n}{k − 1}] + \binom{n + 1}{k}
= (n + 1 − k)\binom{n + 1}{k}.

Checking (20) for b_{n,0} (∀n ≥ 1) and b_{k+1,k} (∀k ≥ 0) completes the proof.

Finally, plugging (19) and (20) in (18) we obtain a recursion for the number of intervals of a given length.

Proposition 5. Starting with e_{n,0} = 2^{n}, for every k ≥ 0 and for every n ≥ k + 1, we have

e_{n,k+1} = e_{n,k} + 2^{n} − ∑_{i=0}^{k} \binom{n}{i} − (n − k + 1)\binom{n}{k}.  (24)

For 0 ≤ k ≤ 5 and n ≥ k, formulas for e_{n,k} are shown below

e_{n,0} = 1 · 2^{n}
e_{n,1} = 2 · 2^{n} − n − 2
e_{n,2} = 3 · 2^{n} − n^{2} − 2n − 3
e_{n,3} = 4 · 2^{n} − \frac{1}{2}n^{3} − \frac{1}{2}n^{2} − 3n − 4
e_{n,4} = 5 · 2^{n} − \frac{1}{6}n^{4} + \frac{1}{6}n^{3} − \frac{11}{6}n^{2} − \frac{19}{6}n − 5
e_{n,5} = 6 · 2^{n} − \frac{1}{24}n^{5} + \frac{1}{6}n^{4} − \frac{23}{24}n^{3} − \frac{2}{3}n^{2} − \frac{9}{2}n − 6.

By iterating (24), we obtain the next corollary.

Corollary 6. For a fixed k ≥ 0, when n ≥ k, we have

e_{n,k} = (k + 1) · 2^{n} + Pol_{k}(n),  (25)

where Pol_{k}(n) is a polynomial of degree k in n. Therefore, the average number of nodes at distance k from a randomly selected one is given by

\frac{e_{n,k}}{2^{n}} = k + 1 + O (\frac{n^{k}}{2^{n}} ) (n → ∞).  (26)

Formula (26) says that, if n is large enough, each node of Q_{n}(σ) has on average k + 1 nodes at distance k above it. In the unconstrained hypercube Q_{n}, the number of intervals of length k is given by

∑_{D=0}^{n} \binom{D}{k}\binom{n}{D} = 2^{n−k}\binom{n}{k};  (27)

also see sequences \underline{A038207} and \underline{A065109} of [9]. Thus, on average, a random node of Q_{n} has

\binom{n}{k}/2^{k}  (28)

nodes above at distance k. This value strongly depends on n (and k), whereas in Q_{n}(σ), for n sufficiently large, the only parameter is k (26).

4 Number of permutations intersecting a node

In this section, we compute the number of permutations belonging to Av_{n}(σ) that intersect a given node w of Q_{n}(σ). This number is denoted by T_{σ}(w) or simply by T (w). For a fixed node w, in general T_{132}(w) ≠ T_{123}(w). The statistic T_{σ}(w) thus depends on the pattern σ. To start, let us focus on σ = 132.

Table 3: Values of α_{d,D} for 0 ≤ d ≤ 10 and 1 ≤ D ≤ 10.
α_{d,D}  d
0 1 2 3  4  5  6  7  8  9  10
D = 1 1 1 0 0  0  0  0  0  0  0  0
D = 2 1 2 2 0  0  0  0  0  0  0  0
D = 3 1 3 5 5  0  0  0  0  0  0  0
D = 4 1 4 9 14 14  0  0  0  0  0  0
D = 5 1 5 14 28 42 42  0  0  0  0  0
D = 6 1 6 20 48 90 132 132  0  0  0  0
D = 7 1 7 27 75 165 297 429 429  0  0  0
D = 8 1 8 35 110 275 572 1001 1430 1430  0  0
D = 9 1 9 44 154 429 1001 2002 3432 4862 4862  0
D = 10 1 10 54 208 637 1638 3640 7072 11934 16796 16796

4.1 Case σ = 132

For a node w, we define α(w) as the number of paths in Q_{n}(132) going from w to 1^{n}. Similarly, β(w) counts those paths from 0^{n} to w. Then T (w) = α(w) · β(w).

Let us start by computing α(w). Using the notation of Table 1, we have recursion (29), which is obtained by summing α(w′) over the nodes w′ that cover w:

α(w) = α_{d,D} = α_{d,D−1} · (1 − δ_{d,D}) + (∑_{i=0}^{d−1} α_{i,D−1}) ,  (29)

where α_{0,1} = α_{1,1} = 1.

Formula (29) allows the calculation of the terms α_{d,D}, for the first values of d and D. Results are collected in Table 3.

As it easily follows from (29), each entry of Table 3 above is computed by summing the entries in the previous row with a lesser or equal d-value. This results in the equivalent recursion

α_{d,D} = α_{d−1,D} + α_{d,D−1},

where α_{0,1} = α_{1,1} = 1 and α_{d,D} = 0 if d > D . Table 3 thus corresponds to a well-known [1] Catalan triangle \underline{A009766} whose entries also determine the distribution of important statistics defined for other Catalan structures, such as the length of the last descent or the number of primitive subpaths [4] in Dyck paths.

Defining the generating function

A(x, y) = ∑_{D≥1} ∑_{d=0}^{D} α_{d,D}x^{d}y^{D},

then

A(x, y) = \frac{1}{1 − y} − 1 + xy + +y ∑_{D≥1} ∑_{d=1}^{D} α_{d,D}x^{d}y^{D} + x ∑_{D≥2} ∑_{d=0}^{D−1} α_{d,D}x^{d}y^{D}

= \frac{1}{1 − y} − 1 + xy + y (A(x, y) − \frac{1}{1 − y} + 1)

+x [A(x, y) − y − xy − (\frac{1 − \sqrt{1 − 4xy}}{2xy} − 1 − xy)] .

Solving gives

A(x, y) = \frac{1 − 2xy − 2y^{2} − \sqrt{1 − 4xy}}{2y(x + y − 1)}

and coefficients α_{d,D} are therefore

α(w) = \binom{D + d}{D} · \frac{D − d + 1}{D + 1}.  (30)

To compute the number of paths going from 0^{n} to a node w, we consider, as in Table 1, the parameters u_{1}, u_{2}, …, u_{ℓ}, where ℓ = ℓ(w) is the number of blocks of consecutive 1’s in w and u_{i} = u_{i}(w) is the length of the i-th block taken from left to right. Indeed, observe that each path connecting 0^{n} to w = w(u_{1}, …, u_{ℓ}) first creates the sequence of 1’s corresponding to u_{ℓ}, followed by the sequence corresponding to u_{ℓ−1}, and so on up to u_{1}. Each step u_{i} can be completed in exactly c_{u_{i}} ways and therefore β(w) is given by

β(w) = ∏_{i=0}^{ℓ} c_{u_{i}}.  (31)

We can now provide a new combinatorial interpretation of the following well-known recursive relation

c_{n} = β(1^{n}) = ∑_{i=0}^{n−1} β(1^{i}01^{n−1−i}) = ∑_{i=0}^{n−1} c_{i} · c_{n−1−i}.

The next proposition determines a formula for the computation of T (w) = α(w) · β(w).

Proposition 7. For a node w of Q_{n}(132), with the notation of Table 1, we have

T_{132}(w) = \binom{D + d}{D} · \frac{D − d + 1}{D + 1} · ∏_{i=0}^{ℓ} c_{u_{i}}.  (32)

4.2 Case σ = 123

In the case σ = 123, the value of α(w) — the number of paths from the node w to 1^{n} — can be computed exactly as when σ = 132 (30). What is different is the computation of β(w): the number of paths from 0^{n} to w. In the easiest case, node w ends with an entry equal to 0, and then β(w) = 1. In general, if u denotes the length of the maximal suffix of w containing only entries equal to 1 (Table 1), then, similarly to (29), we have the recursion

β(w) = β_{u,U} = β_{u,U−1} · (1 − δ_{U,u}) + ∑_{i=0}^{u−1} β_{i,U−1},

where β_{0,1} = β_{1,1} = 1 and the parameter U is as in Table 1. The same kind of computation that led from (29) to (30) now gives

β(w) = \binom{U + u}{U} · \frac{U − u + 1}{U + 1}.  (33)

Combining the results together, we obtain a formula for T (w) = α(w) · β(w).

Proposition 8. For a node w of Q_{n}(123), with the notation of Table 1, we have

T_{123}(w) = \binom{D + d}{D} · \frac{D − d + 1}{D + 1} · \binom{U + u}{U} · \frac{U − u + 1}{U + 1}.  (34)

4.3 Expected number of intersections for a random node

Assuming a uniform distribution over the nodes w of Q_{n}(σ), the expected value of T_{σ}(w) coincides in the two cases σ = 132, 123. The expectation can be computed by considering the natural ranking of Q_{n}(σ), where two nodes w_{1}, w_{2} have the same rank r if D(w_{1}) = D(w_{2}) = r. Indeed, summing the value of T_{σ}(w) over all the possible nodes w rank by rank,

∑_{w∈Q_{n}(σ)} T_{σ}(w) = (n + 1)c_{n} = \binom{2n}{n}.

It follows that on average, both in Q_{n}(132) and in Q_{n}(123), we have

E(T_{σ}(w)) = \frac{1}{2^{n}} · \binom{2n}{n}.  (35)

Similarly, we obtain the expectation of T_{σ}(w) at each rank r as

E(T_{σ}(w)|D(w) = r) = c_{n}/\binom{n}{r}.  (36)

The results obtained in (35) and (36) can be rephrased by saying that, removing a random node chosen uniformly from the entire hypercube Q_{n}(σ) or from a given rank {w : D(w) = r}

Figure 2: Picking random nodes from Σ_{i}^{n} (left) and Σ_{−i}^{n} (right) , for n = 15. The x-axis determines the value of i. For each 0 ≤ i ≤ 15 we randomly select 2 · 10^{3} nodes w from Σ_{i}^{n} (resp. Σ_{−i}^{n} ). For each selected node w, we compute Δ_{i,w} = T_{132}(w) − T_{123}(w) and we take Δ_{i} as the average of Δ_{i,w} over all the selected w’s. Δ_{i} is shown on the vertical axis.

of Q_{n}(σ), the number of paths (or permutations) that consequently cease to exist is on average the same in the two scenarios σ = 132 and σ = 123.

This equivalence does not hold in general. Using random simulations, we show that if we remove nodes from certain regions of the hypercube Q_{n}(σ), the number of permutations that remain in the graph can strongly depend on the pattern σ. As an example (Fig. 2), we can indeed consider the two regions

Σ_{i}^{n} = {w ∈ Σ^{n} : w starts with j ≥ i entries 1}
Σ_{−i}^{n} = {w ∈ Σ^{n} : w ends with j ≥ i entries 1}.

In Fig. 2 (left), we pick random nodes from Σ_{i}^{n}, whereas on the right, we take nodes from Σ_{−i}^{n}. In both cases, the vertical axis gives the value of the difference T_{132}(w) − T_{123}(w) averaged over several randomly selected nodes w.

5 Open problem: intersecting permutations

In Section 4, we have studied the number of permutations of Av_{n}(σ) that intersect a given node w ∈ Σ^{n}. Going a step further, one can consider the number of permutations of Av_{n}(σ) that intersect a given permutation π ∈ S_{n}. In other words, it is interesting to address the following general question:

Problem. Given a path p of Q_{n}, say

p = 0^{n} → w_{1} → ⋯ → w_{n−1} → 1^{n},  (37)

how many paths of Q_{n}(σ) intersect p only in the extreme points 0^{n} and 1^{n}?

When

p = p_{id} = 0^{n} → 10^{n−1} → 110^{n−2} → ⋯ → 1^{n}  (38)

is the path associated with the identity permutation π_{id} = (1 2 3 … n), the problem reduces to the computation of the number of indecomposable permutations in Av_{n}(σ). Indeed, a permutation π = (π_{1} ⋯ π_{n}) is indecomposable [3, 7, 10] when there is no index i ∈ [1, n) such that {π_{1}, …, π_{i}} = {1, …, i}.

As introductory examples, we provide the answer to the problem defined above for two instances of the path p. We indeed consider the case p = p_{id} as in (38) and the case

p = ψ(p_{id}) = 0^{n} → 10^{n−1} → 10^{n−2}1 → 10^{n−3}11 → ⋯ → 101^{n−2} → 1^{n},  (39)

where ψ is the bijection that maps paths of Q_{n}(132) onto paths of Q_{n}(123) as defined in Section 2.2.1. Note that the path in (39) corresponds to the permutation π_{ψ(p_{id})} = (1 n n − 1 … 2).

If we denote by j_{n}(p) the number of paths (permutations) of Q_{n}(σ) that intersect p only in the extreme poits 0^{n} and 1^{n}, we have the following result:

Proposition 9. If p_{id} is the path of the identity permutation, then we have

j_{n}(p) = \begin{cases}c_{n} − c_{n−1}, & if p = p_{id} and σ = 132; \\ c_{n} − n + 1, & if p = p_{id} and σ = 123; \\ c_{n} − ∑_{i=1}^{n−1} c_{i−1}, & if p = ψ(p_{id}) and σ = 132; \\ c_{n} − c_{n−1}, & if p = ψ(p_{id}) and σ = 123. \end{cases}

Proof. We have four cases depending on the path p and the pattern σ.

i) Case p = p_{id}. Following the notation of (37), for 1 ≤ i ≤ n−1 we thus have w_{i} = 1^{i}0^{n−i}. Let us first focus on σ = 123. Note that T_{123}(w_{1}) = T_{123}(w_{2}) = ⋯ = T_{123}(w_{n−1}) = 1. At the same time, for all indices i ≠ i′ in [1, n − 1] nodes w_{i} and w_{i′} are incomparable in ⪯_{123} (Proposition 1) and therefore the path intersecting w_{i} does not intersect w_{i′}. Thus, by subtracting one path for each node w_{i} from the total number c_{n} of paths present in Q_{n}(123), we have

j_{n}(p) = c_{n} − n + 1 (σ = 123).  (40)

Take σ = 132. Note that all the paths that intersect w_{i} also pass through w_{i+1}, because w_{i+1} is the only node that covers w_{i} in ⪯_{132} (Proposition 1). Thus

j_{n}(p) = c_{n} − T_{132}(w_{n−1}) = c_{n} − T_{132}(1^{n−1}0) = c_{n} − c_{n−1} (σ = 132),  (41)

and j_{n}(p) gives in this case a new interpretation of sequence \underline{A000245} of [9].

ii) Case p = ψ(p_{id}). We now consider p as in (39). Thus, in the notation of (37), for 1 ≤ i ≤ n − 1 we have w_{i} = 10^{n−i}1^{i−1}. Take first σ = 123. In this case, all the paths through w_{i} also intersect w_{i+1}, because w_{i+1} is the only node that covers w_{i} in ⪯_{123} (Proposition 1). Therefore, as in (41), we have

j_{n}(p) = c_{n} − T_{123}(w_{n−1}) = c_{n} − T_{123}(101^{n−2}) = c_{n} − c_{n−1} (σ = 123).  (42)

When σ = 132, we have T_{132}(w_{i}) = c_{i−1}. Furthermore, for all indices i ≠ i′ in [1, n − 1] nodes w_{i} and w_{i′} are incomparable in ⪯_{132} (Proposition 1) and therefore the paths intersecting w_{i} do not intersect w_{i′}. Thus, by subtracting c_{i} paths for each node w_{i} from the total number c_{n} of paths present in Q_{n}(132), we obtain

j_{n}(p) = c_{n} − ∑_{i=1}^{n−1} c_{i−1} (σ = 132).  (43)

Considering (40), (41), (42), and (43) concludes the proof.

6 Conclusions

We have introduced the oriented graphs Q_{n}(σ) defined over the set of binary words Σ_{n}, where σ is a permutation pattern of length three: σ ∈ {132, 123}. The poset Q_{n}(σ), with its order relation ⪯_{σ}, is obtained from the classical hypercube Q_{n} by requiring edge constraints such that each strictly increasing path in Q_{n}(σ) from 0^{n} to 1^{n} bijectively encodes a permutation of Av_{n}(σ).

We have investigated some of the combinatorial properties of the posets Q_{n}(σ). In particular, we have studied their numbers of intervals, which are independent of the pattern σ. More precisely, Proposition 1 characterizes the order relations ⪯_{σ} induced by the orientation of the edges in Q_{n}(σ). Proposition 3 and Corollary 4 give closed formulas for the number of intervals in Q_{n}(σ) and the associated expectation. Proposition 5 and Corollary 6 refine the result by considering the numbers of intervals of given length. We compared these results with those obtained for the unconstrained hypercube Q_{n} (see (13) and (27)).

To highlight some other differences between the non-isomorphic oriented graphs Q_{n}(123) and Q_{n}(132) and the unconstrained hypercube Q_{n}, in Section 4 we focused on the number of paths/permutations intersecting a given node. Formulas are given according to the simple parameters described in Table 1. Proposition 7 covers the case σ = 132, and Proposition 8 determines the result for σ = 123. Whereas the expected number of paths intersecting a random node is the same in the two scenarios σ = 132, 123, simulations showed that this is not true in general when we pick nodes from particular subsets of Σ^{n}.

Finally, in Section 5, we introduced a new problem related to path intersection in Q_{n}(σ) and solved some preliminary instances.

6.1 Other patterns

It is quite natural to ask whether results similar to those shown here could be obtained for other types of constrained hypercubes, such as Q_{n}(σ) where σ is a permutation-pattern of length greater than 3. If we take any single pattern σ, with |σ| > 3, it is easy to see that the approach used above to define Q_{n}(σ) by removing single edges from the unconstrained Q_{n} does not apply anymore. Indeed, we cannot explicitly characterize those edges of Q_{n} that are responsible for the presence of those paths/permutations containing the pattern σ. For example, if we take σ = 1243, we cannot remove from Q_{4} the edge 1100 → 1101 because, besides 1243, this would cancel also the permutation 2143. In other words, for single patterns |σ| > 3, there is no subset of the edges of Q_{n} that is responsible for the appearance of all and only the permutations containing σ.

Considering sets of patterns things change and, in some special cases, for sets of patterns of length greater than 3, we can still define the associated hypercube. For instance, considering the set of patterns σ = {1243, 2143}, Q_{n}(σ) can be obtained by removing from Q_{n} edges of the form

α 1 β 1 γ 0 δ 0 ϵ → α 1 β 1 γ 0 δ 1 ϵ.

A complete characterization of those sets of patterns σ for which the associated class of permutations Av_{n}(σ) admits an hypercube representation is still missing. It would be of interest to see whether the classes of permutations with an hypercube representation share some common enumerative features that characterize them.

7 Acknowledgment

I thank Doc Edge for helpful discussions.

References

[1] E. Barcucci and M. C. Verri, Some more properties of Catalan numbers, Discrete Math. 102 (1992), 220–237.

[2] A. Claesson and S. Kitaev, Classification of bijections between 321- and 132avoiding permutations, Sém. Lothar. Combin. 60 (2008/09), Art. B60d. Available at

    http://www.emis.de/journals/SLC/wpapers/s60claekit.html.

[3] L. Comtet, Advanced Combinatorics. Reidel, 1974.

[4] E. Deutsch, Dyck path enumeration, Discrete Math. 204 (1999), 167–202.

[5] J. Franke, A. Klözer, J. A. G. M. de Visser, and J. Krug, Evolutionary accessibility of mutational pathways, PLoS Computat. Biol. 7 (2011), Article e1002134.

[6] P. Hegarty and A. Martinsson, On the existence of accessible paths in various models of fitness landscapes, Ann. Appl. Probab. 24 (2014), 1375–1395.

[7] D. E. Knuth, The Art of Computer Programming, Vol. 4, Facsicle 2, Addison-Wesley, 2005.

[8] S. Novak and J. Krug, Accessibility percolation on n-trees, Europhysics Letters 101 (2013), Article 66004.

[9] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electroni-

    cally at http://oeis.org/.

[10] R. P. Stanley, Enumerative Combinatorics, Cambridge University Press, 1999.

2010 Mathematics Subject Classification: Primary 05A15. Keywords: permutations avoiding patterns of length 3, edge-constrained hypercube, number of intervals, number of paths through a node, Catalan number.

(Concerned with sequences \underline{A000079}, \underline{A000108}, \underline{A000245}, \underline{A000295}, \underline{A001793}, \underline{A009766}, \underline{A038207}, \underline{A047520}, and \underline{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.