主题
Search

排列模式


F(n,sigma) 表示在 对称群 S_n 上避免 sigma in S_k 作为子模式的排列的数量,其中 “tau 包含 sigma 作为子模式” 被解释为存在 1<=x_1<=x_2<=...<=x_k<=n 使得对于 1<=i,j<=k,

 tau(x_i)<tau(x_j)

当且仅当 sigma(i)<sigma(j)

例如,一个排列包含模式 (123) 当且仅当 它有一个长度为三的递增子序列。 这里,请注意成员不必实际是连续的, 仅仅是递增的 (Wilf 1997)。 因此,在 3!=6{1,2,3} 的排列中,除了 {3,2,1} 之外的所有排列 (即,{1,2,3}{1,3,2}{2,1,3}{2,3,1}{3,1,2}) 都包含模式 (12) (即,长度为二的递增子序列)。

下表给出了对于各种长度为 k 的模式 (a_1...a_k)k, k+1, ..., n 个数字的模式匹配排列的数量。

模式OEIS模式匹配排列的数量
1A0001421, 2, 6, 24, 120, 720, 5040, ...
12A0333121, 5, 23, 119, 719, 5039, 40319, ...
alpha_3A0569861, 10, 78, 588, 4611, 38890, ...
1234A1580051, 17, 207, 2279, 24553, ...
1324A1580091, 17, 207, 2278, 24527, ...
1342A1580061, 17, 208, 2300, 24835, ...

下表给出了对于各种模式集合,{1,...,n} 的模式避免排列的数量。

Wilf 类OEIS模式避免排列的数量
alpha_3A0001081, 2, 5, 14, 42, 132, ...
123, 132, 213A0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
132, 231, 321A0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
123, 132, 3214A0000731, 2, 4, 7, 13, 24, 44, 81, 149, ...
123, 132, 3241A0000711, 2, 7, 12, 20, 33, 54, 88, 143, ...
123, 132, 3412A0001241, 2, 4, 7, 11, 16, 22, 29, 37, 46, ...
123, 231, alpha_4^((1))A0042751, 2, 4, 6, 8, 10, 12, 14, 16, 18, ...
123, 231, alpha_4^((2))A0001241, 2, 4, 7, 11, 16, 22, 29, 37, 46, ...
123, 231, 43211, 2, 4, 6, 3, 1, 0, ...
132, 213, 1234A0000731, 2, 4, 7, 13, 24, 44, 81, 149, ...
213, 231, alpha_4^((3))A0001241, 2, 4, 7, 11, 16, 22, 29, 37, 46, ...

上表使用的缩写总结如下。

缩写类中的模式
alpha_3123, 132, 213, 232, 312, 321
alpha_4^((1))1432, 2143, 3214, 4132, 4213, 4312
alpha_4^((2))1234, 1243, 1324, 1342, 1423, 2134, 2314, 2341, 2413, 2431, 3124, 3142, 3241, 3412, 3421, 4123, 4231
alpha_4^((3))1234, 1243, 1423, 1432

参见

包含模式, 顺序同构, 排列, Stanley-Wilf 猜想, Wilf 类, Wilf 等价

使用 Wolfram|Alpha 探索

参考文献

Arratia, R. "关于避免给定模式的排列数量的 Stanley-Wilf 猜想。" Electronic J. Combinatorics 6, No. 1, N1, 1-4, 1999. http://www.combinatorics.org/Volume_6/Abstracts/v6i1n1.html.Billey, S.; Jockusch, W.; 和 Stanley, R. P. "Schubert 多项式的一些组合性质。" J. Alg. Combin. 2, 345-374, 1993.Guibert, O. "没有禁止子序列的排列。" Mémoire de Diplô me d'Etudes Approfondies de L'Université Bordeaux I. 1992.Mansour, T. "避免来自 S_k 的一个模式和来自 S_3 的至少两个模式的排列。" 2000 年 7 月 31 日。 http://arxiv.org/abs/math.CO/0007194.Simon, R. 和 Schmidt, F. W. "受限排列。" Europ. J. Combin. 6, 383-406, 1985.Sloane, N. J. A. 序列 A000027/M0472, A000071/M1056, A000073/M1074, A000108/M1459, A000124/M1041, A000142/M1675, A004275, A033312, 和 A056986, A158005, 和 A158006 在 "整数序列在线百科全书" 中。Stankova, Z. E. "禁止子序列。" Disc. Math. 132, 291-316, 1994.West, J. "生成树和禁止子序列。" Disc. Math. 157, 363-372, 1996.Wilf, H. "关于交叉数和一些未解决的问题。" 在 组合数学、几何学和概率:向 Paul Erdős 致敬。1993 年 3 月在剑桥三一学院举行的纪念 Erdős 80 岁生日的会议论文集 (Ed. B. Bollobás 和 A. Thomason)。 英国剑桥:剑桥大学出版社,pp. 557-562, 1997.

在 Wolfram|Alpha 中引用

排列模式

以此引用

Weisstein, Eric W. "排列模式。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/PermutationPattern.html

学科分类