\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \usepackage{array} \newcolumntype{I}{!{\vrule width 2pt}} \newlength\savewidth \newcommand\whline{\noalign{\global\savewidth\arrayrulewidth \global\arrayrulewidth 2pt}% \hline \noalign{\global\arrayrulewidth\savewidth}} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Some Statistics on the Hypercubes \\ \vskip .11in of Catalan Permutations } \vskip 1cm \large Filippo Disanto \\ Department of Biology\\ Stanford University\\ Stanford, CA 94305 \\ USA\\ \href{mailto:fdisanto@stanford.edu}{\tt fdisanto@stanford.edu} \\ \end{center} \vskip .2 in \begin{abstract} For a permutation $\sigma$ of length $3$, we define the oriented graph $Q_n(\sigma)$. The graph $Q_n(\sigma)$ 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(\sigma)$ bijectively encodes a permutation of size $n$ avoiding the pattern $\sigma$. The orientation of the edges in $Q_n(\sigma)$ naturally induces an order relation $\preceq_{\sigma}$ among its nodes. First, we characterize $\preceq_{\sigma}$. Next, we study several enumerative statistics on $Q_n(\sigma)$, including the number of intervals, the number of intervals of fixed length $k$, and the number of paths (or permutations) intersecting a given node. \end{abstract} \section{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 $\Sigma^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 $\pi_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 (\ref{buon}) and (\ref{giorno}). Taking only those permutations that avoid a pattern $\sigma$ 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(\sigma)$, can be defined, where, as in $Q_n$, the partial order in $Q_n(\sigma)$ is naturally induced by the orientation of the edges (Fig.~\ref{B132}). According to the classical definition of pattern avoidance, the set of permutations of size $n$ that avoid a pattern $\sigma$ is denoted by $Av_n(\sigma)$ and, when $|\sigma|=3$, the cardinality of $Av_n(\sigma)$ is given by the well-known \cite{stan} sequence of \emph{Catalan} numbers \begin{equation} c_n = |Av_n(\sigma)| = \frac{1}{n+1} {{2n}\choose{n}}; \end{equation} see sequence \seqnum{A000108} of \cite{sloane}. Several authors (see \cite{clae} 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. \subsection{Motivation} Our general aim is to introduce --- and hopefully motivate further studies of --- certain subgraphs $Q_n(\sigma)$ of the oriented hypercube $Q_n$ that can be defined for particular sets of permutation patterns $\sigma$. As a case study, we investigate patterns of length three for which $Q_n(\sigma)$ relates to the $c_n$ permutations of $Av_n(\sigma)$. 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$. %With this aim, here we focus our attention on basic features of partially ordered sets (posets) and oriented graphs. In this spirit, we study the number of intervals (Section~\ref{inter}) and number of paths intersecting a given node (Section~\ref{stab}) in the oriented graphs $Q_n(\sigma)$. We consider the number of intervals in order to investigate the underlying poset structure of $Q_n(\sigma)$ 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(\sigma)$. 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(\sigma)$ 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! \big/ {{n}\choose{D}}$ of paths, other parameters (Table~\ref{pio}) become important when pattern avoidance is considered. Section~\ref{stab} is indeed dedicated to the computation, for $\sigma \in \{ 123,132 \}$, of the number of paths/permutations that intersect a node $w$ in $Q_n(\sigma)$. This value does not only depend on the rank of the node and it is strongly affected by the choice of the pattern~$\sigma$. 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 \emph{fitness landscapes} \cite{franco, hegarty}: 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 (\emph{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., \cite{novak}). 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(\sigma)$. Finally, it is worth mentioning that the approach presented here to define $Q_n(\sigma)$ for patterns $\sigma$ of length $3$ can be extended to include other permutation patterns (Section~\ref{ebasta}). \subsection{Summary of the results} In this study, we focus on patterns $\sigma = 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 $\sigma$, in Section~\ref{hypcat} we define the oriented (sub)graph $Q_n(\sigma)$, which is obtained by removing particular edges from the classic oriented hypercube $Q_n$. For both $\sigma=132, 123$ the number of nodes in the graph $Q_n(\sigma)$ 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(\sigma)$ encodes a permutation of $Av_n(\sigma)$. 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 \emph{not} isomorphic graphs. We conclude the section by characterizing the order relation $\preceq_{\sigma}$ induced on the nodes of $Q_n(\sigma)$ by the orientation of the edges. In Section~\ref{inter}, 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(\sigma),\preceq_{\sigma})$. These statistics are independent of the pattern $\sigma$ 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}$ (\ref{scemi}). For instance, if $0 \leq k \leq 5$, we find \begin{eqnarray}\nonumber e_{n,0} &=& 1 \cdot 2^n \\\nonumber e_{n,1} &=& 2 \cdot 2^{n}-n-2 \\\nonumber e_{n,2} &=& 3 \cdot 2^n -n^2 -2n -3 \\\nonumber e_{n,3} &=& 4 \cdot 2^n -\frac{1}{2}n^3 - \frac{1}{2}n^2 - 3n - 4 \\\nonumber e_{n,4} &=& 5 \cdot 2^n -\frac{1}{6}n^4 + \frac{1}{6}n^3 - \frac{11}{6}n^2 -\frac{19}{6}n -5 \\\nonumber e_{n,5} &=& 6 \cdot 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. \\\nonumber \end{eqnarray} In general, we show that for every $k$ $$e_{n,k} = (k+1)\cdot 2^n + \mathcal{O}(n^k).$$ In Section~\ref{stab}, we find closed formulas to compute $T_{\sigma}(w)$, the number of paths (or permutations) intersecting a given node $w \in Q_n(\sigma)$. In the notation of Table~\ref{pio}, we find \begin{eqnarray}\nonumber T_{132}(w) &=& {{D+d}\choose{D}} \cdot \frac{D-d+1}{D+1} \cdot \prod_{i=0}^{\ell} c_{u_i}, \\ \nonumber T_{123}(w) &=& {{D+d}\choose{D}} \cdot \frac{D-d+1}{D+1} \cdot {{U+u}\choose{U}} \cdot \frac{U-u+1}{U+1}.\\ \end{eqnarray} In general, $T_{132}(w) \neq 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~\ref{marino} by introducing a new problem related to path intersection in $Q_n(\sigma)$ and solving some preliminary instances. \section{Constrained hypercubes}\label{hypcat} \subsection{Hypercube and permutations} We let $Q_n$ denote the classic oriented hypercube on the set of binary words $\Sigma^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 \in \Sigma^n$, their \emph{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 \in \Sigma^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 $\preceq$ among the nodes of $Q_n$. We thus consider $Q_n$ as a poset in what follows. With respect to the strict order relation $\prec$, 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 $\pi_p \in S_n$ is sketched in the following example given for size $n=5$: \begin{eqnarray}\label{buon} p &=& 00000\rightarrow 00010\rightarrow 01010\rightarrow 01011\rightarrow 11011\rightarrow 11111 \\\label{giorno} \pi_p &=& 00000\rightarrow 00010\rightarrow 02010\rightarrow 02013\rightarrow 42013\rightarrow 42513. \end{eqnarray} The rule that leads from $p$ to $\pi_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. \subsubsection{Edge constraints of the hypercube} For each pattern $\sigma \in \{132, 123 \}$, we define the oriented graph $Q_n(\sigma)$ as a constrained version of $Q_n$ such that the previously described bijection $p \mapsto \pi_p$ maps paths of $Q_n(\sigma)$ onto permutations of $Av_n(\sigma)$. For $\sigma=132$ and $\sigma=123$ the definition of $Q_n(\sigma)$ is given as follows: \begin{itemize} \item[(i)] The constrained hypercube $Q_n(132)$ (Fig.~\ref{B132} (right)) is obtained by removing from $Q_n$ those edges $w_1 \rightarrow w_2$ connecting two words $w_1 \prec 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 = \alpha \, 1 \, \beta \, 0 \, \gamma \, 0 \, \delta \nrightarrow \alpha \, 1 \, \beta \, 0 \, \gamma \, 1 \, \delta = w_2.$$ \item[(ii)] The constrained hypercube $Q_n(123)$ (Fig.~\ref{B132} (left)) is obtained by removing from $Q_n$ those edges of type $$w_1 = \alpha \, 1 \, \beta \, 0 \, \gamma \, 0 \, \delta \nrightarrow \alpha \, 1 \, \beta \, 1 \, \gamma \, 0 \, \delta = w_2.$$ \end{itemize} Note that, in both cases (i) and (ii), all the nodes in $\Sigma^n \setminus \{0^n, 1^n \}$ have outdegree and indegree greater than or equal to one in $Q_n(\sigma)$. Therefore, for any fixed $\sigma \in \{ 132,123 \}$, each node of $\Sigma^n$ has at least one path of $Q_n(\sigma)$ that intersects it. In particular, the set of nodes of $Q_n(\sigma)$ corresponds to the entire set of binary words $\Sigma^n$ as it is in $Q_n$. \begin{figure} \begin{center} \includegraphics*[scale=.7,trim=0 0 0 0]{B123ori.eps} \end{center} \caption{{\small 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~\ref{puccino}).}}\label{B132} \end{figure} \subsection{Structural properties of the constrained hypercubes}\label{puccino} Inspection of Fig.~\ref{B132} (circled nodes) shows that the two depicted graphs are not isomorphic. Indeed, suppose there exists an isomorphism $\phi: Q_4(123) \mapsto Q_4(132)$. The isomorphism $\phi$ would give $\phi(0000)=0000$ and $\phi(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 $1000$ in $Q_4(123)$ (resp., $Q_4(132)$), we would have $\phi(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 \begin{equation}\label{latta} \phi(0001)=0100. \end{equation} At the same time, equality (\ref{latta}) is not compatible with an isomorphism $\phi$ because node $0001$ of $Q_4(123)$ has outdegree $3$, whereas node $0100$ of $Q_4(132)$ has outdgree $2$. %Indeed, observe that both in $Q_4(132)$ and $Q_4(123)$ there is only one node of outdegree $1$ which covers $0000$, that is $1000$. This node is covered by $1100$ in $Q_4(132)$ and by $1001$ in $Q_4(123)$. Both $1100$ and $1001$ cover two nodes: $1000$ and also $0100$ in $Q_4(132)$ as well as $0001$ in $Q_4(123)$. Finally, observe that $0100$ has outdegree $2$ in $Q_4(132)$ while $0001$ has outdegree $3$ in $Q_4(123)$. It follows that the two graphs $Q_n(132)$ and $Q_n(123)$ are \emph{not} in general isomorphic. \begin{table} \caption{{\small Key parameters defined over the words in $\Sigma^n$. For instance, if $w = 00101110$, then $d = 2, u = 0, \ell = 2, u_1 = 1$, and $u_2 = 3$, whereas, setting $w = 1101011$, we obtain $d = 0, u = 2, \ell = 3, u_1 = 2, u_2 = 1$, and $u_3 = 2$.}} \fontsize{10}{12}\selectfont \label{pio} \vspace{-.2cm} \begin{center} \begin{tabular}{Ic I c I} \whline & \\ $D(w)$ & number of $0$'s in $w$ \\ & \\ \hline & \\ $d(w)$ & length of the maximal \emph{prefix} of $w$ containing only $0$'s \\ & \\\hline & \\ $U(w)$ & number of $1$'s in $w$ \\ & \\ \hline & \\ $u(w)$ & length of the maximal \emph{suffix} of $w$ containing only $1$'s \\ & \\ \hline & \\ $u_i(w)$ & length of the $i$-th (from left to right) block of $1$'s in $w$ \\ & \\ \hline & \\ $\ell(w)$ & number of blocks of consecutive $1$'s in $w$ \\ & \\ \whline %& \\ % $e_{n,k}$ & number of ntervals of length $k$ in $Q_n(\sigma)$ \\ %& \\ \hline %& \\ % $T_{\sigma}(w)$ & number of paths/permutations intersecting node $w$ in $Q_n(\sigma)$ \\ %& \\ \hline \end{tabular} \end{center} \end{table} \subsubsection{Order relation in $Q_n(132)$ and $Q_n(123)$}\label{uggiaa} As for the classic hypercube $Q_n$, when $\sigma \in \{132, 123 \}$, the orientation of the edges in $Q_n(\sigma)$ determines an order relation $\preceq_{\sigma}$ among the $2^n$ nodes of $Q_n(\sigma)$. By the definition of $Q_n(\sigma)$, the order relation $\preceq_{\sigma} $ is clearly a restriction of $\preceq$. It is interesting to note that, even if the two graphs $Q_n(132)$ and $Q_n(123)$ are not in general isomorphic (Fig.~\ref{B132}), there is a duality holding between the order relations $\preceq_{132}$ and $\preceq_{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) \leq D$ the length of the maximal (left) prefix of $w$ containing only $0$'s (Table~\ref{pio}). We define the word $w^{(i)}$ ($D \geq i \geq 0$) as the word obtained by replacing the \emph{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\leq 0$ as follows: if $D \geq j \geq 0$, then $w^{(-j)}$ is the word obtained by replacing the \emph{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$. With this notation, the next result describes the order relation $\preceq_{\sigma}$ existing among the nodes of $Q_n(\sigma)$ as it is induced by the orientation of the edges of $Q_n(\sigma)$. \begin{proposition}\label{pergoletta} We have the following: \begin{itemize} \item[(i)] If $w_1, w_2 \in \Sigma^n$ and $d = d(w_1)$, then $w_1 \preceq_{132} w_2$ if and only if \begin{equation}\label{micio} w_2=w \cdot \big( w_1(d+1)w_1(d+2)\cdots w_1(n) \big)^{(i)}, \end{equation} where $i \geq 0$, $w$ is any word of length $d$, and $w_1(m)$ denotes the $m$-th letter of $w_1$. \item[(ii)] If $w_1, w_2 \in \Sigma^n$ and $d = d(w_1)$, then $w_1 \preceq_{123} w_2$ if and only if \begin{equation}\label{mao} w_2=w \cdot \big( w_1(d+1)w_1(d+2)\cdots w_1(n) \big)^{(-j)}, \end{equation} where $j \geq 0$, $w$ is any word of length $d$, and $w_1(m)$ denotes the $m$-th letter of $w_1$. \end{itemize} \end{proposition} \begin{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$ \emph{covers} a node $v_1$ if and only if $v_2$ can be obtained from $v_1$ either by replacing \emph{any} $0$ belonging to the maximal prefix of $0$'s in $v_1$ with an entry $1$ or by replacing the \emph{first} $0$ (resp., \emph{last} $0$) to the right of the leftmost $1$ in $v_1$ with an entry $1$. \end{proof} \smallskip \begin{remark} As a corollary, Proposition~\ref{pergoletta} allows to define an inductive procedure $\psi$ that, given a path $p$ of $Q_n(132)$, creates a dual path $\psi(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 \rightarrow w_1 \rightarrow \cdots \rightarrow w_n,$$ we define $$\psi(p) = w'_0 \rightarrow w'_1 \rightarrow \cdots \rightarrow w'_n $$ inductively as follows. Set $w'_0 = 0^n$ and assume that we have already defined $w'_i$ for each $0 \leq i \leq j$. According to Proposition~\ref{pergoletta} (i), the word $w_{j+1}$ that covers $w_j$ is obtained from $w_j$ as \begin{equation}\label{vom} w_{j+1} = w \cdot \big( w_j(d+1)w_j(d+2)\cdots w_j(n) \big)^{(+i)}, \end{equation} where $d = d(w_j)$, $w$ is a word of length $d$ such that $h(w,0^d) \leq 1$, and $i = 1 - h(w,0^d) \in \{ 0,1 \}$. Given (\ref{vom}), we set \begin{equation} \label{ener} w'_{j+1} = w \cdot \big( w'_j(d+1) \, w'_j(d+2) \, \cdots \, w'_j(n) \big)^{(-i)}, \end{equation} where $w$ is as in (\ref{vom}). 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 \leq j \leq 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~\ref{pergoletta}. The bijection $\psi$ 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 $(\psi(p_1),\psi(p_2))$. For instance, $(2341,1234)$ do not intersect in $Q_4(132)$, but both $\psi(2341) = 2431$ and $\psi(1234) = 1432$ pass through the node $1011$ in $Q_4(123)$. \end{remark} \section{Number of intervals}\label{inter} In this section, we study the number of intervals of $Q_n(\sigma)$. We are thus interested in those pairs $(w_1,w_2) \in \Sigma^n \times \Sigma^n$ with $w_1 \preceq_{\sigma} w_2$. By Proposition~\ref{pergoletta}, the statistic number of intervals does not depend on the pattern $\sigma$ and we denote by $e_n$ the number of intervals in $Q_n(\sigma)$ for each $\sigma \in \{ 132,123 \}$ . \subsection{Enumeration of $e_n$} Fix a word $w_1$. By Proposition~\ref{pergoletta}, the number of words $w_2$ greater than or equal to $w_1$ in $Q_n(\sigma)$ is given by \begin{equation} 2^d (D-d+1), \end{equation} where $D = D(w_1)$ and $d = d(w_1)$. Summing over all possible words $w_1$, $e_n$ can be computed as \begin{equation}\label{goletta} e_n = 2^n + \sum_{D=0}^{n-1} \sum_{d=0}^{D} 2^{d} (D-d+1) {{n-d-1}\choose{n-D-1}}. \end{equation} The sequence $(e_n)_{n \geq 1}$ starts as $$3,9,26,72,192,496,1248,3072,7424,17664.$$ Furthermore, observe that \begin{equation}\label{gola} \tilde{e}_n = e_n -2^n = \sum_{D=0}^{n-1} \sum_{d=0}^{D} 2^{d} (D-d+1) {{n-d-1}\choose{n-D-1}} \end{equation} counts the number of \emph{strict} intervals of $Q_n(\sigma)$. Strict intervals are those pairs $(w_1,w_2)$ with $w_1 \prec_{\sigma} w_2$. The next proposition gives a closed formula for $\tilde{e}_n$ (and thus for $e_n$). \begin{proposition}\label{ermellino} For all $n \geq 1$, we have $$\tilde{e}_n=\sum_{D=0}^{n-1} \sum_{d=0}^{D} 2^{d} (D-d+1) {{n-d-1}\choose{n-D-1}}=2^{n-3} (n^2 + 3n).$$ \end{proposition} \begin{proof} Observe that by performing the substitution $A=n-d$ and $B=n-D$, we obtain $$\tilde{e}_n= 2^n \sum_{B=1}^{n} \sum_{A=B}^{n}\left( \frac{1}{2} \right)^A (A-B+1) {{A-1}\choose{B-1}}.$$ By induction on $n$, we have \begin{eqnarray}\nonumber \tilde{e}_n &=& \, 2^n\left[ \sum_{B=1}^{n-1} \left[ \sum_{A=B}^{n-1} \left( \frac{1}{2} \right)^A (A-B+1) {{A-1}\choose{B-1}} \right] + \left( \frac{1}{2} \right)^n (n-B+1) {{n-1}\choose{B-1}} \right] + 1\\\nonumber &=& \, 2 \tilde{e}_{n-1} + 2^n \left[\sum_{B=1}^{n-1} \left( \frac{1}{2} \right)^n (n-B+1) {{n-1}\choose{B-1}}\right] + 1\\\nonumber &=& \, 2 \tilde{e}_{n-1} + 2^n \left( \frac{1}{4} -2^{-n} +\frac{n}{4} \right) +1 \\\nonumber &=& \, 2 \tilde{e}_{n-1} + 2^{n-2}(n+1)\\\nonumber &=& \, 2 \cdot 2^{n-4} ((n-1)^2 + 3(n-1)) + 2^{n-2}(n+1) = 2^{n-3} (n^2 + 3n). \nonumber \end{eqnarray} This concludes the proof. \end{proof} \bigskip Proposition~\ref{ermellino} shows that $(\tilde{e}_n)_n$ provides a new interpretation of sequence \seqnum{A001793} of \cite{sloane}. Furthermore, we have the following corollary. \begin{corollary}\label{marmotta} A node of $Q_n(\sigma)$ has on average $$\frac{\tilde{e}_n}{2^n} = \frac{n^2+3n}{8}$$ nodes strictly above it. \end{corollary} It is interesting to observe that, in the unconstrained hypercube $Q_n$, the number of intervals $w_1 \preceq w_2$ is given by \begin{equation}\label{bianco} \sum_{D=0}^n 2^D {{n}\choose{D}} = 3^n. \end{equation} Thus, on average, a random node of $Q_n$ has an exponential \begin{equation} \frac{3^n -2^n}{2^n} \sim (3/2)^n \end{equation} number of nodes strictly above it. \subsection{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 \preceq_{\sigma} 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 = \sum_{k=0}^{n} e_{n,k}$. Note that Proposition~\ref{pergoletta} ensures, also in this case, that the statistic $e_{n,k}$ does not depend on the pattern $\sigma \in \{ 132, 123 \}$. By (\ref{micio}) and (\ref{mao}), for a given word $w_1$, the number of words $w_2$ greater than or equal to $w_1$ in $Q_n(\sigma)$ and such that $h(w_1,w_2)=k$ is given by \begin{equation}\label{sole} \sum_{i=0}^{D-d} {{d}\choose{k-i}}, \end{equation} where $D = D(w_1)$ and $d = d(w_1)$. Indeed, in the notation of Proposition~\ref{pergoletta}, if $w_2$ is obtained from $w_1$ as \begin{equation}\label{rocchio} w_2 = w \cdot \big( w_1(d+1)w_1(d+2)\cdots w_1(n) \big)^{(i)}, \end{equation} 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 (\ref{rocchio}) we have $$k = h(w_1,w_2) = i + U(w)$$ and (\ref{sole}) easily follows. Note that if $Dd$. Summing over all possible nodes $w_1$ of $Q_n(\sigma)$, we thus obtain \begin{equation}\label{golona} e_{n,k}= {{n}\choose{k}} + \sum_{D=0}^{n-1} \sum_{d=0}^{D} {{n-d-1}\choose{n-D-1}} \sum_{i=0}^{D-d} {{d}\choose{k-i}}. \end{equation} Using the sum in (\ref{golona}), we can compute the first terms of the sequences $((e_{n,k})_n)_k$. These terms are shown in the table~\ref{tavolozza} for $1\leq n \leq 10$ and $0 \leq k \leq 10$. Note that the first column corresponds to entry \seqnum{A000079} of \cite{sloane} while the second and the third appear respectively as sequences \seqnum{A000295} (\emph{Eulerian} numbers) and \seqnum{A047520}. \begin{table} \caption{{\small Values of $e_{n,k}$ for $1\leq n \leq 10$ and $0 \leq k \leq 10$.}} \fontsize{10}{12}\selectfont \label{tavolozza} \vspace{-.2cm} \begin{center} \begin{tabular}{|c | c c c c c c c c c c c|}\hline $e_{n,k}$ & \multicolumn{11}{c|}{$k$} \\ \cline{2-12} & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ &$9$ & $10$ \\ \hline $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 \\ \hline \end{tabular} \end{center} \end{table} \smallskip Using (\ref{golona}), we can write that $\forall k \geq 0$ and $\forall n \geq k+1$ \begin{eqnarray} \nonumber e_{n,k+1} - e_{n,k} &=& {{n}\choose{k+1}} - {{n}\choose{k}} + \sum_{D=0}^{n-1} \sum_{d=0}^{D} {{n-d-1}\choose{n-D-1}} \left[{{d}\choose{k+1}} - {{d}\choose{k-(D-d)}} \right] \\\label{pimpa} &=& {{n}\choose{k+1}} - {{n}\choose{k}} + a_{n,k} -b_{n,k}, \end{eqnarray} where, with $1 \leq k+1 \leq n$, \begin{eqnarray}\label{ozio} a_{n,k} & \equiv & \sum_{D=0}^{n-1} \sum_{d=0}^{D} {{n-d-1}\choose{n-D-1}} {{d}\choose{k+1}} = 2^n - \sum_{i=0}^{k+1} {{n}\choose{i}} \,\,\,\,\, \mathrm{and} \\\label{ozia} b_{n,k} & \equiv & \sum_{D=0}^{n-1} \sum_{d=0}^{D} {{n-d-1}\choose{n-D-1}} {{d}\choose{k-(D-d)}} = (n-k){{n}\choose{k}}. \end{eqnarray} To prove the equality in (\ref{ozio}), observe that \begin{eqnarray}\nonumber a_{n,k} &=& \sum_{D=0}^{n-1} \sum_{d=0}^{n-1} {{n-d-1}\choose{n-D-1}} {{d}\choose{k+1}} = \sum_{d=0}^{n-1} {{d}\choose{k+1}} \sum_{D=0}^{n-1} {{n-d-1}\choose{n-D-1}} \\\nonumber &=& \sum_{d=0}^{n-1} {{d}\choose{k+1}} \sum_{D=d}^{n-1} {{n-d-1}\choose{n-D-1}} = \sum_{d=0}^{n-1} {{d}\choose{k+1}} 2^{n-d-1} \\\label{norcia} &=& 2^{n-1} \sum_{d=k+1}^{n-1} {{d}\choose{k+1}} \left(\frac{1}{2}\right)^{d} \end{eqnarray} Thus, from (\ref{norcia}), the recursion \begin{equation}\label{inno} a_{n,k} = 2 a_{n-1,k} + {{n-1}\choose{k+1}}. \end{equation} Now, by induction on $n$, assuming that (\ref{ozio}) holds for $a_{n-1,k}$, by substituting in (\ref{inno}) we have \begin{eqnarray}\nonumber a_{n,k} &=& 2 a_{n-1,k} + {{n-1}\choose{k+1}} = 2\left( 2^{n-1} - \sum_{i=0}^{k+1} {{n-1}\choose{i}} \right) + {{n-1}\choose{k+1}} \\\nonumber &=& 2^n - \sum_{i=0}^{k+1} {{n-1}\choose{i}} - \sum_{i=0}^{k} {{n-1}\choose{i}} = 2^n - \left[\sum_{i=0}^{k+1} {{n}\choose{i}} - {{n-1}\choose{i-1}} \right]- \sum_{i=0}^{k} {{n-1}\choose{i}} \\\nonumber &=& 2^n - \sum_{i=0}^{k+1} {{n}\choose{i}} - \left[ \sum_{i=0}^{k} {{n-1}\choose{i}} - \sum_{i=0}^{k+1} {{n-1}\choose{i-1}} \right] = 2^n - \sum_{i=0}^{k+1} {{n}\choose{i}} \end{eqnarray} Checking (\ref{ozio}) for $a_{k+1,k}$ completes the proof. \smallskip To prove the equality in (\ref{ozia}), note that $$b_{n,k}= \sum_{D=k}^{n-1} \sum_{d=0}^{D} {{n-d-1}\choose{n-D-1}} {{d}\choose{k-(D-d)}}.$$ Thus, setting $A=n-d$ and $B=n-D$, we have the recursion \begin{eqnarray}\nonumber b_{n+1,k} &=& \sum_{B=1}^{n+1-k} \sum_{A=B}^{n+1} {{A-1}\choose{B-1}}{{n+1-A}\choose{k-A+B}} \\\nonumber &=& \left[ \sum_{B=1}^{n-k} \sum_{A=B}^{n+1} {{A-1}\choose{B-1}}{{n+1-A}\choose{k-A+B}} \right] + \sum_{A=B=n+1-k}^{n+1} {{A-1}\choose{n-k}} \cdot 1 \\\nonumber &=& {{n+1}\choose{k}} + \sum_{B=1}^{n-k} \sum_{A=B}^{n+1} {{A-1}\choose{B-1}}{{n+1-A}\choose{k-A+B}} \\\nonumber &=& {{n+1}\choose{k}} + \left[ \sum_{B=1}^{n-k} \sum_{A=B}^{n} {{A-1}\choose{B-1}}{{n+1-A}\choose{k-A+B}} \right] + \sum_{B=1}^{n-k} {{n}\choose{B-1}} {{0}\choose{k-n-1+B}} \\\nonumber &=& {{n+1}\choose{k}} + \sum_{B=1}^{n-k} \sum_{A=B}^{n} {{A-1}\choose{B-1}}\left[ {{n-A}\choose{k-A+B}} + {{n-A}\choose{k-1-A+B}} \right] \\\nonumber &=& {{n+1}\choose{k}} + b_{n,k} + \sum_{B=1}^{n-k} \sum_{A=B}^{n} {{A-1}\choose{B-1}} {{n-A}\choose{k-1-A+B}} \\\nonumber &=& {{n+1}\choose{k}} + b_{n,k} + \left[\sum_{B=1}^{n-(k-1)} \sum_{A=B}^{n} {{A-1}\choose{B-1}} {{n-A}\choose{k-1-A+B}} \right] - \sum_{A=B=n+1-k}^{n} {{A-1}\choose{n-k}} \cdot 1 \\\label{mammamia} &=& {{n+1}\choose{k}} + b_{n,k} + b_{n,k-1} - {{n}\choose{k-1}} = b_{n,k} + b_{n,k-1} + {{n}\choose{k}}. \end{eqnarray} Now, by induction on $n$ and $k$, assuming that (\ref{ozia}) holds for $b_{n,k}$ and $b_{n,k-1}$, by substituting in (\ref{mammamia}), \begin{eqnarray}\nonumber b_{n+1,k} &=& (n-k){{n}\choose{k}} + (n-k+1){{n}\choose{k-1}} + {{n}\choose{k}} \\\nonumber &=& (n-k)\left[ {{n}\choose{k}} + {{n}\choose{k-1}}\right] + {{n+1}\choose{k}} \\\nonumber &=& (n+1-k){{n+1}\choose{k}}. \end{eqnarray} Checking (\ref{ozia}) for $b_{n,0}$ ($\forall n \geq 1$) and $b_{k+1,k}$ ($\forall k \geq 0$) completes the proof. \bigskip Finally, plugging (\ref{ozio}) and (\ref{ozia}) in (\ref{pimpa}) we obtain a recursion for the number of intervals of a given length. \begin{proposition}\label{pecora} Starting with $e_{n,0} = 2^n$, for every $k \geq 0$ and for every $n \geq k+1$, we have \begin{equation} \label{scemi} e_{n,k+1} = e_{n,k} + 2^n - \sum_{i=0}^k {{n}\choose{i}} -(n-k+1){{n}\choose{k}}. \end{equation} \end{proposition} For $0 \leq k \leq 5$ and $n \geq k$, formulas for $e_{n,k}$ are shown below \begin{eqnarray}\nonumber e_{n,0} &=& 1 \cdot 2^n \\\nonumber e_{n,1} &=& 2 \cdot 2^{n}-n-2 \\\nonumber e_{n,2} &=& 3 \cdot 2^n -n^2 -2n -3 \\\nonumber e_{n,3} &=& 4 \cdot 2^n -\frac{1}{2}n^3 - \frac{1}{2}n^2 - 3n - 4 \\\nonumber e_{n,4} &=& 5 \cdot 2^n -\frac{1}{6}n^4 + \frac{1}{6}n^3 - \frac{11}{6}n^2 -\frac{19}{6}n -5 \\\nonumber e_{n,5} &=& 6 \cdot 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. \\\nonumber \end{eqnarray} \smallskip By iterating (\ref{scemi}), we obtain the next corollary. \begin{corollary}\label{montone} For a fixed $k \geq 0$, when $n \geq k$, we have \begin{equation}\label{malaccio} e_{n,k} = (k+1)\cdot 2^n + \mathrm{Pol}_k(n), \end{equation} where $\mathrm{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 \begin{equation}\label{asinello} \frac{e_{n,k}}{2^n} = k+1 + \mathcal{O}\left( \frac{n^k}{2^n} \right) \quad (n \rightarrow \infty). \end{equation} \end{corollary} Formula (\ref{asinello}) says that, if $n$ is large enough, each node of $Q_n(\sigma)$ 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 \begin{equation}\label{nero} \sum_{D=0}^n {{D}\choose{k}} {{n}\choose{D}} = 2^{n-k} {{n}\choose{k}}; \end{equation} also see sequences \seqnum{A038207} and \seqnum{A065109} of \cite{sloane}. Thus, on average, a random node of $Q_n$ has \begin{equation} {{n}\choose{k}} \bigg/ 2^k \end{equation} nodes above at distance $k$. This value strongly depends on $n$ (and $k$), whereas in $Q_n(\sigma)$, for $n$ sufficiently large, the only parameter is $k$ (\ref{asinello}). \section{Number of permutations intersecting a node}\label{stab} In this section, we compute the number of permutations belonging to $Av_n(\sigma)$ that intersect a given node $w$ of $Q_n(\sigma)$. This number is denoted by $T_{\sigma}(w)$ or simply by $T(w)$. For a fixed node $w$, in general $T_{132}(w) \neq T_{123}(w)$. The statistic $T_{\sigma}(w)$ thus depends on the pattern $\sigma$. To start, let us focus on $\sigma=132$. \subsection{Case $\sigma = 132$} For a node $w$, we define $\alpha(w)$ as the number of paths in $Q_n(132)$ going from $w$ to $1^n$. Similarly, $\beta(w)$ counts those paths from $0^n$ to $w$. Then $T(w) = \alpha(w) \cdot \beta(w)$. Let us start by computing $\alpha(w)$. Using the notation of Table~\ref{pio}, we have recursion (\ref{ciocco}), which is obtained by summing $\alpha(w')$ over the nodes $w'$ that cover $w$: \begin{equation}\label{ciocco} \alpha(w)=\alpha_{d,D}= \alpha_{d,D-1} \cdot (1-\delta_{d,D}) + \left(\sum_{i=0}^{d-1} \alpha_{i,D-1} \right), \end{equation} where $\alpha_{0,1} = \alpha_{1,1} = 1$. Formula (\ref{ciocco}) allows the calculation of the terms $\alpha_{d,D}$, for the first values of $d$ and $D$. Results are collected in Table~\ref{tabbola}. \begin{table} \caption{{\small Values of $\alpha_{d,D}$ for $0\leq d \leq 10$ and $1 \leq D \leq 10$.}} \fontsize{10}{12}\selectfont \label{tabbola} \vspace{-.2cm} \begin{center} \begin{tabular}{|c | c c c c c c c c c c c |}\hline $\alpha_{d,D}$ & \multicolumn{11}{c|}{$d$} \\ \cline{2-12} & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ \\ \hline $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 \\ \hline \end{tabular} \end{center} \end{table} As it easily follows from (\ref{ciocco}), each entry of Table~\ref{tabbola} above is computed by summing the entries in the previous row with a lesser or equal $d$-value. This results in the equivalent recursion $$\alpha_{d,D}=\alpha_{d-1,D} + \alpha_{d,D-1},$$ where $\alpha_{0,1} = \alpha_{1,1} = 1$ and $\alpha_{d,D}=0$ if $d>D$ . Table~\ref{tabbola} thus corresponds to a well-known~\cite{barcu} Catalan triangle \seqnum{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 \cite{deu} in Dyck paths. Defining the generating function $$A(x,y)=\sum_{D \geq 1} \sum_{d=0}^{D} \alpha_{d,D} x^d y^D,$$ then \begin{eqnarray} \nonumber A(x,y) &=& \frac{1}{1-y} - 1 + xy + + y \sum_{D \geq 1} \sum_{d=1}^{D} \alpha_{d,D} x^d y^D + x \sum_{D \geq 2} \sum_{d=0}^{D-1} \alpha_{d,D} x^d y^D \\\nonumber &=& \frac{1}{1-y} - 1 + xy + y \left( A(x,y) - \frac{1}{1-y} +1 \right)\\\nonumber && + x \left[ A(x,y) -y -xy - \left( \frac{1-\sqrt{1-4xy}}{2xy} -1 -xy \right) \right]. \nonumber \end{eqnarray} Solving gives \begin{equation}\nonumber A(x,y) = \frac{1-2xy-2y^2-\sqrt{1-4xy}}{2y(x+y-1)} \end{equation} and coefficients $\alpha_{d,D}$ are therefore \begin{equation}\label{pinco} \alpha(w) = {{D+d}\choose{D}} \cdot \frac{D-d+1}{D+1}. \end{equation} \smallskip To compute the number of paths going from $0^n$ to a node $w$, we consider, as in Table~\ref{pio}, the parameters $u_1, u_2, \ldots, u_{\ell}$, where $\ell = \ell(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,\ldots,u_{\ell})$ first creates the sequence of $1$'s corresponding to $u_{\ell}$, followed by the sequence corresponding to $u_{\ell - 1}$, and so on up to $u_1$. Each step $u_i$ can be completed in exactly $c_{u_i}$ ways and therefore $\beta(w)$ is given by \begin{equation}\label{nonni} \beta(w) = \prod _{i=0}^{\ell} c_{u_i}. \end{equation} We can now provide a new combinatorial interpretation of the following well-known recursive relation \begin{equation}\nonumber c_n = \beta(1^n) = \sum_{i=0}^{n-1} \beta(1^i01^{n-1-i}) = \sum_{i=0}^{n-1} c_i \cdot c_{n-1-i}. \end{equation} The next proposition determines a formula for the computation of $T(w) = \alpha(w) \cdot \beta(w)$. \begin{proposition}\label{gassi} For a node $w$ of $Q_n(132)$, with the notation of Table~\ref{pio}, %$D$ entries $0$, $d \leq D$ entries $0$ placed to the left of the leftmost $1$ (if any) and where $u_1, u_2, \ldots , u_{\ell}$ are the lengths of the $\ell$ blocks of $1$'s in $w$, we have \begin{equation}\label{primula} T_{132}(w) = {{D+d}\choose{D}} \cdot \frac{D-d+1}{D+1} \cdot \prod_{i=0}^{\ell} c_{u_i}. \end{equation} \end{proposition} \subsection{Case $\sigma = 123$} In the case $\sigma=123$, the value of $\alpha(w)$ --- the number of paths from the node $w$ to $1^n$ --- can be computed exactly as when $\sigma = 132$ (\ref{pinco}). What is different is the computation of $\beta(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 $\beta(w)=1$. In general, if $u$ denotes the length of the maximal suffix of $w$ containing only entries equal to $1$ (Table~\ref{pio}), then, similarly to (\ref{ciocco}), we have the recursion %When $w$ ends with $1$ and $u$ is the length of the rightmost block of $1$'s in $w$ we have the recursion $$\beta(w)=\beta_{u,U} = \beta_{u,U-1} \cdot (1-\delta_{U,u}) + \beta_{u-1,U-1}+ \beta_{u-2,U-1} + \cdots + \beta_{1,U-1} + 1.$$ %The two cases together give $$\beta(w)=\beta_{u,U} = \beta_{u,U-1} \cdot (1-\delta_{U,u}) + \sum_{i=0}^{u-1} \beta_{i,U-1},$$ where $\beta_{0,1} = \beta_{1,1} = 1$ and the parameter $U$ is as in Table~\ref{pio}. %Note that, according to our definition, $\beta_{0,U} = 1$ refers to a node $w$ ending with $0$. The same kind of computation that led from (\ref{ciocco}) to (\ref{pinco}) now gives \begin{equation} \beta(w)={{U+u}\choose{U}} \cdot \frac{U-u+1}{U+1}. \end{equation} Combining the results together, we obtain a formula for $T(w)=\alpha(w) \cdot \beta(w)$. \begin{proposition}\label{principina} For a node $w$ of $Q_n(123)$, with the notation of Table~\ref{pio}, %with $D$ entries $0$, $d \leq D$ entries $0$ placed to the left of the leftmost $1$ (if any), $U=n-D$ entries $1$ and $u \leq U$ entries $1$ placed at the end of $k$ ($u=0$ if $k$ ends with $0$), we have \begin{equation} T_{123}(w) = {{D+d}\choose{D}} \cdot \frac{D-d+1}{D+1} \cdot {{U+u}\choose{U}} \cdot \frac{U-u+1}{U+1}. \end{equation} \end{proposition} \subsection{Expected number of intersections for a random node} Assuming a uniform distribution over the nodes $w$ of $Q_n(\sigma)$, the expected value of $T_{\sigma}(w)$ coincides in the two cases $\sigma=132,123$. The expectation can be computed by considering the natural ranking of $Q_n(\sigma)$, 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_{\sigma}(w)$ over all the possible nodes $w$ rank by rank, $$\sum_{w \in Q_n(\sigma)} T_{\sigma}(w) = (n+1) c_n = {{2n}\choose{n}}.$$ It follows that on average, both in $Q_n(132)$ and in $Q_n(123)$, we have \begin{equation}\label{armadillo} \text{E}\big(T_{\sigma}(w)\big) = \frac{1}{2^n} \cdot {{2n}\choose{n}}. \end{equation} Similarly, we obtain the expectation of $T_{\sigma}(w)$ at each rank $r$ as \begin{equation}\label{buzzurro} \text{E}\big(T_{\sigma}(w) \big| D(w) = r \big) = c_n \bigg/ {{n}\choose{r}}. \end{equation} The results obtained in (\ref{armadillo}) and (\ref{buzzurro}) can be rephrased by saying that, removing a random node chosen uniformly from the entire hypercube $Q_n(\sigma)$ or from a given rank $\{w:D(w)=r\}$ of $Q_n(\sigma)$, the number of paths (or permutations) that consequently cease to exist is on average the same in the two scenarios $\sigma = 132$ and $\sigma = 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(\sigma)$, the number of permutations that remain in the graph can strongly depend on the pattern $\sigma$. As an example (Fig.~\ref{uccellino}), we can indeed consider the two regions \begin{eqnarray}\nonumber \Sigma^n_{i} &=& \{ w \in \Sigma^n : w \mathrm{\,\, starts \,\, with \,\,} j \geq i \mathrm{\,\, entries \,\,} 1 \} \\\nonumber \Sigma^n_{-i} &=& \{ w \in \Sigma^n : w \mathrm{\,\, ends \,\, with \,\,} j \geq i \mathrm{\,\, entries \,\,} 1 \}. \end{eqnarray} In Fig.~\ref{uccellino}~(left), we pick random nodes from $\Sigma^n_{i}$, whereas on the right, we take nodes from $\Sigma^n_{-i}$. 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$. \begin{figure} \begin{center}\label{ma} \begin{tabular}{|c|c|}\hline \includegraphics*[scale=.7,trim=0 0 0 0]{uccellino.eps} & \includegraphics*[scale=.7,trim=0 0 0 0]{altra.eps} \\ \hline \end{tabular} \end{center} \caption{\small{Picking random nodes from $\Sigma^n_{i}$ (left) and $\Sigma^n_{-i}$ (right) , for $n=15$. The $x$-axis determines the value of $i$. For each $0\leq i \leq 15$ we randomly select $2\cdot 10^3$ nodes $w$ from $\Sigma^n_{i}$ (resp. $\Sigma^n_{-i}$ ). For each selected node $w$, we compute $\Delta_{i,w} = T_{132}(w) - T_{123}(w)$ and we take $\Delta_i$ as the average of $\Delta_{i,w}$ over all the selected $w$'s. $\Delta_i$ is shown on the vertical axis.}}\label{uccellino} \end{figure} \section{Open problem: intersecting permutations}\label{marino} In Section~\ref{stab}, we have studied the number of permutations of $Av_n(\sigma)$ that intersect a given node $w \in \Sigma^n$. Going a step further, one can consider the number of permutations of $Av_n(\sigma)$ that intersect a given permutation $\pi \in S_n$. In other words, it is interesting to address the following general question: \smallskip \emph{Problem.} Given a path $p$ of $Q_n$, say \begin{equation}\label{score} p = 0^n \rightarrow w_1 \rightarrow \cdots \rightarrow w_{n-1} \rightarrow 1^n, \end{equation} how many paths of $Q_n(\sigma)$ intersect $p$ only in the extreme points $0^n$ and $1^n$? \bigskip When \begin{equation}\label{pid} p = p_{id} = 0^n \rightarrow 10^{n-1} \rightarrow 110^{n-2}\rightarrow \cdots \rightarrow 1^n \end{equation} is the path associated with the identity permutation $\pi_{id} = ( 1 \, 2 \, 3 \, \ldots \, n ),$ the problem reduces to the computation of the number of \emph{indecomposable} permutations in $Av_n(\sigma)$. Indeed, a permutation $\pi = (\pi_1 \, \cdots \, \pi_n)$ is indecomposable \cite{com,knu,stan} when there is no index $i \in [1,n)$ such that $\{ \pi_1, \ldots, \pi_i \} = \{1, \ldots, 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 (\ref{pid}) and the case \begin{equation}\label{ppsi} p=\psi(p_{id})= 0^n \rightarrow 10^{n-1} \rightarrow 10^{n-2}1 \rightarrow 10^{n-3}11 \rightarrow \cdots \rightarrow 101^{n-2} \rightarrow 1^n, \end{equation} where $\psi$ is the bijection that maps paths of $Q_n(132)$ onto paths of $Q_n(123)$ as defined in Section~\ref{uggiaa}. Note that the path in (\ref{ppsi}) corresponds to the permutation $\pi _{\psi(p_{id})} = ( 1 \, n \, n-1 \, \ldots \, 2 ).$ If we denote by $j_n(p)$ the number of paths (permutations) of $Q_n(\sigma)$ that intersect $p$ only in the extreme poits $0^n$ and $1^n$, we have the following result: \begin{proposition} If $p_{id}$ is the path of the identity permutation, then we have \[ j_n(p) = \begin{cases} c_n - c_{n-1}, & \text{if } p=p_{id} \text{ and } \sigma = 132; \\ c_n - n + 1, & \text{if } p=p_{id} \text{ and } \sigma = 123; \\ c_n - \sum_{i=1}^{n-1} c_{i-1}, & \text{if } p=\psi(p_{id}) \text{ and } \sigma = 132; \\ c_n - c_{n-1}, & \text{if } p=\psi(p_{id}) \text{ and } \sigma = 123. \end{cases} \] %\begin{eqnarray}\nonumber %j_{n,132}(p_{id}) & = & c_n - c_{n-1}, \\\nonumber %j_{n,123}(p_{id}) & = & c_n -n+1, \\ \nonumber %j_{n,132}(\psi(p_{id})) & = & c_n - \sum_{i=1}^{n-1} c_{i-1}, \\ \nonumber %j_{n,123}(\psi(p_{id})) & = & c_n - c_{n-1}. %\end{eqnarray} \end{proposition} \begin{proof} We have four cases depending on the path $p$ and the pattern~$\sigma$. $i)$ Case $p=p_{id}$. Following the notation of (\ref{score}), for $1 \leq i \leq n-1$ we thus have $w_i = 1^i0^{n-i}$. Let us first focus on $\sigma=123$. Note that $T_{123}(w_1)=T_{123}(w_2)= \cdots =T_{123}(w_{n-1})=1$. At the same time, for all indices $i \neq i'$ in $[ 1, n-1 ]$ nodes $w_i$ and $w_{i'}$ are incomparable in $\preceq_{123}$ (Proposition~\ref{pergoletta}) and therefore the path intersecting $w_i$ does not intersect $w_{i'}$. %the path intersecting $w_x$ does not intersect $w_y$ $\forall x \neq y$ in $[ 1, n-1 ]$. %In other words, nodes $w_i$ and $w_{i'}$ are incomparable in $\preceq_{123}$ as it follows from Proposition~\ref{pergoletta}. 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 \begin{equation}\label{uno} j_{n}(p) = c_n - n+1 \quad (\sigma = 123). \end{equation} Take $\sigma=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 $\preceq_{132}$ (Proposition~\ref{pergoletta}). Thus %$T(k_i) \subset T(k_{i+1})$ and thus \begin{equation}\label{due} j_{n}(p) = c_n - T_{132}(w_{n-1}) = c_n - T_{132}(1^{n-1}0) = c_n - c_{n-1} \quad (\sigma = 132), \end{equation} and $j_n(p)$ gives in this case a new interpretation of sequence \seqnum{A000245} of \cite{sloane}. \smallskip $ii)$ Case $p=\psi(p_{id})$. %Applying the bijection $\psi$, We now consider $p$ as in (\ref{ppsi}). %= 0^n \rightarrow 10^{n-1} \rightarrow 10^{n-2}1 \rightarrow 10^{n-3}11 \rightarrow \cdots \rightarrow 101^{n-2} \rightarrow 1^n,$$ Thus, in the notation of (\ref{score}), for $1 \leq i \leq n-1$ we have $w_i = 10^{n-i}1^{i-1}$. Take first $\sigma = 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 $\preceq_{123}$ (Proposition~\ref{pergoletta}). Therefore, as in (\ref{due}), we have \begin{equation}\label{tre} j_{n}(p) = c_n - T_{123}(w_{n-1}) = c_n - T_{123}(101^{n-2}) = c_n - c_{n-1} \quad (\sigma = 123). \end{equation} When $\sigma=132$, we have $T_{132}(w_i)=c_{i-1}$. Furthermore, for all indices $i \neq i'$ in $[ 1, n-1 ]$ nodes $w_i$ and $w_{i'}$ are incomparable in $\preceq_{132}$ (Proposition~\ref{pergoletta}) and therefore the paths intersecting $w_i$ do not intersect $w_{i'}$. %the paths passing through $w_x$ do not pass through $w_y$ $\forall x \neq y$ in $[ 1, n-1 ]$. Indeed, according to Proposition~\ref{pergoletta}, $w_x$ and $w_y$ are incomparable in $\preceq_{132}$. %$T(k_i) \bigcap T(k_j) = \emptyset$. 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 \begin{equation}\label{quattro} j_{n}(p) = c_n - \sum_{i=1}^{n-1} c_{i-1} \quad (\sigma = 132). \end{equation} Considering (\ref{uno}), (\ref{due}), (\ref{tre}), and (\ref{quattro}) concludes the proof. \end{proof} \section{Conclusions}\label{ebasta} We have introduced the oriented graphs $Q_n(\sigma)$ defined over the set of binary words $\Sigma_n$, where $\sigma$ is a permutation pattern of length three: $\sigma \in \{132,123 \}$. The poset $Q_n(\sigma)$, with its order relation $\preceq_{\sigma}$, is obtained from the classical hypercube $Q_n$ by requiring edge constraints such that each strictly increasing path in $Q_n(\sigma)$ from $0^n$ to $1^n$ bijectively encodes a permutation of $Av_n(\sigma)$. We have investigated some of the combinatorial properties of the posets $Q_n(\sigma)$. In particular, we have studied their numbers of intervals, which are independent of the pattern $\sigma$. More precisely, Proposition~\ref{pergoletta} characterizes the order relations $\preceq_{\sigma}$ induced by the orientation of the edges in $Q_n(\sigma)$. Proposition~\ref{ermellino} and Corollary~\ref{marmotta} give closed formulas for the number of intervals in $Q_n(\sigma)$ and the associated expectation. Proposition~\ref{pecora} and Corollary~\ref{montone} 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 (\ref{bianco}) and (\ref{nero})). 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~\ref{stab} we focused on the number of paths/permutations intersecting a given node. Formulas are given according to the simple parameters described in Table~\ref{pio}. Proposition~\ref{gassi} covers the case $\sigma = 132$, and Proposition~\ref{principina} determines the result for $\sigma = 123$. Whereas the expected number of paths intersecting a random node is the same in the two scenarios $\sigma = 132, 123$, simulations showed that this is not true in general when we pick nodes from particular subsets of $\Sigma^n$. Finally, in Section~\ref{marino}, we introduced a new problem related to path intersection in $Q_n(\sigma)$ and solved some preliminary instances. \subsection{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(\sigma)$ where $\sigma$ is a permutation-pattern of length greater than $3$. If we take any \emph{single} pattern $\sigma$, with $|\sigma| > 3$, it is easy to see that the approach used above to define $Q_n(\sigma)$ 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 $\sigma$. For example, if we take $\sigma = 1243$, we cannot remove from $Q_4$ the edge $1100 \rightarrow 1101$ because, besides $1243$, this would cancel also the permutation $2143$. In other words, for single patterns $|\sigma| > 3$, there is no subset of the edges of $Q_n$ that is responsible for the appearance of all and \emph{only} the permutations containing $\sigma$. Considering \emph{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 $\sigma = \{ 1243, 2143 \} $, $Q_n(\sigma)$ can be obtained by removing from $Q_n$ edges of the form $$ \alpha \, 1 \, \beta \, 1 \, \gamma \, 0 \, \delta \, 0 \, \epsilon \rightarrow \alpha \, 1 \, \beta \, 1 \, \gamma \, 0 \, \delta \, 1 \, \epsilon.$$ A complete characterization of those sets of patterns $\sigma$ for which the associated class of permutations $Av_n(\sigma)$ 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. \section{Acknowledgment} I thank Doc Edge for helpful discussions. \begin{thebibliography}{10} \bibitem{barcu} E.~Barcucci and M.~C.~Verri, Some more properties of Catalan numbers, \emph{Discrete Math.} {\bf 102} (1992), 220--237. \bibitem{clae} A.~Claesson and S.~Kitaev, Classification of bijections between 321- and 132-avoiding permutations, \emph{ S\'em. Lothar. Combin.} {\bf 60} (2008/09), Art.~B60d. Available at \url{http://www.emis.de/journals/SLC/wpapers/s60claekit.html}. \bibitem{com} L.~Comtet, \emph{Advanced Combinatorics}. Reidel, 1974. \bibitem{deu} E.~Deutsch, Dyck path enumeration, \emph{Discrete Math.} {\bf 204} (1999), 167--202. \bibitem{franco} J.~Franke, A.~Kl\"ozer, J.~A.~G.~M.~de Visser, and J.~Krug, Evolutionary accessibility of mutational pathways, \emph{PLoS Computat. Biol.} {\bf 7} (2011), Article e1002134. \bibitem{hegarty} P.~Hegarty and A.~Martinsson, On the existence of accessible paths in various models of fitness landscapes, \emph{Ann. Appl. Probab.} {\bf 24} (2014), 1375--1395. \bibitem{knu} D.~E.~Knuth, \emph{The Art of Computer Programming}, Vol.~4, Facsicle 2, Addison-Wesley, 2005. \bibitem{novak} S.~Novak and J.~Krug, Accessibility percolation on $n$-trees, \emph{Europhysics Letters} {\bf 101} (2013), Article 66004. \bibitem{sloane} N.~J.~A.~Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at \url{http://oeis.org/}. \bibitem{stan} R.~P.~Stanley, \emph{Enumerative Combinatorics,} Cambridge University Press, 1999. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05A15. \noindent \emph{Keywords: } permutations avoiding patterns of length 3, edge-constrained hypercube, number of intervals, number of paths through a node, Catalan number. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000079}, \seqnum{A000108}, \seqnum{A000245}, \seqnum{A000295}, \seqnum{A001793}, \seqnum{A009766}, \seqnum{A038207}, \seqnum{A047520}, and \seqnum{A065109}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received April 16 2014; revised version received November 11 2014; December 17 2014. Published in {\it Journal of Integer Sequences}, January 24 2015. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}