Subsequence Containment by Involutions
Subsequence Containment by Involutions
复制标题
通过对合进行后续遏制
DOI：
10.37236/1911
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
A. D. Jaggard
中科院分区：
文献类型：
--
作者：
A. D. Jaggard
受McKay、莫尔斯和Wilf工作的启发，我们给出了S_n中包含S_k中给定置换\tau作为子序列的对合的精确计数;这个数目取决于\tau的前j个值的模式，其中1<=j<=k。然后，我们使用这个定义S_k的划分，类似于模式避免研究中的Wilf类，并检查这种等价的性质。在这个过程中，我们证明了一个置换\tau_1.\τ_k是分层的当且仅当，对于1<=j<=k，\τ_1.\τ_j是一个对合。我们还得到了一个结果，萨根和斯坦利计数的标准杨tableaux的大小$n$，其中包含一个固定的tableau大小$k$作为一个subtableau。
Inspired by work of McKay, Morse, and Wilf, we give an exact count of the involutions in S_n which contain a given permutation \tau in S_k as a subsequence; this number depends on the patterns of the first j values of \tau for 1<=j<=k. We then use this to define a partition of S_k, analogous to Wilf-classes in the study of pattern avoidance, and examine properties of this equivalence. In the process, we show that a permutation \tau_1...\tau_k is layered iff, for 1<=j<=k, the pattern of \tau_1...\tau_j is an involution. We also obtain a result of Sagan and Stanley counting the standard Young tableaux of size $n$ which contain a fixed tableau of size $k$ as a subtableau.