Some Statistics on the Hypercubes of Catalan Permutations
Some Statistics on the Hypercubes of Catalan Permutations
复制标题
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
F. Disanto
中科院分区：
文献类型：
--
作者：
F. Disanto
对于长度为 3 的排列 σ，我们定义有向图 Qn(σ)。图 Qn(σ) 是通过对经典定向超立方体 Qn 施加边缘约束而获得的，使得 Qn(σ) 中从 0 到 1 的每条路径双射编码大小为 n 的排列，避免模式 σ。 Qn(σ) 中边的方向自然会导致其节点之间存在顺序关系 σ。首先，我们表征 σ。接下来，我们研究 Qn(σ) 的几个枚举统计量，包括区间数、固定长度 k 的区间数以及与给定节点相交的路径（或排列）数。
For a permutation σ of length 3, we define the oriented graph Qn(σ). The graph Qn(σ) is obtained by imposing edge constraints on the classical oriented hypercube Qn, such that each path going from 0 to 1 in Qn(σ) bijectively encodes a permutation of size n avoiding the pattern σ. The orientation of the edges in Qn(σ) naturally induces an order relation σ among its nodes. First, we characterize σ. Next, we study several enumerative statistics on Qn(σ), including the number of intervals, the number of intervals of fixed length k, and the number of paths (or permutations) intersecting a given node.