设 表示在 对称群
上避免
作为子模式的排列的数量,其中 “
包含
作为子模式” 被解释为存在
使得对于
,
当且仅当 。
例如,一个排列包含模式 (123) 当且仅当 它有一个长度为三的递增子序列。 这里,请注意成员不必实际是连续的, 仅仅是递增的 (Wilf 1997)。 因此,在 个
的排列中,除了
之外的所有排列 (即,
、
、
、
和
) 都包含模式 (12) (即,长度为二的递增子序列)。
下表给出了对于各种长度为 的模式
,
,
, ...,
个数字的模式匹配排列的数量。
模式 | OEIS | 模式匹配排列的数量 |
1 | A000142 | 1, 2, 6, 24, 120, 720, 5040, ... |
12 | A033312 | 1, 5, 23, 119, 719, 5039, 40319, ... |
A056986 | 1, 10, 78, 588, 4611, 38890, ... | |
1234 | A158005 | 1, 17, 207, 2279, 24553, ... |
1324 | A158009 | 1, 17, 207, 2278, 24527, ... |
1342 | A158006 | 1, 17, 208, 2300, 24835, ... |
下表给出了对于各种模式集合, 的模式避免排列的数量。
Wilf 类 | OEIS | 模式避免排列的数量 |
A000108 | 1, 2, 5, 14, 42, 132, ... | |
123, 132, 213 | A000027 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... |
132, 231, 321 | A000027 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... |
123, 132, 3214 | A000073 | 1, 2, 4, 7, 13, 24, 44, 81, 149, ... |
123, 132, 3241 | A000071 | 1, 2, 7, 12, 20, 33, 54, 88, 143, ... |
123, 132, 3412 | A000124 | 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, ... |
123,
231, | A004275 | 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, ... |
123, 231,
| A000124 | 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, ... |
123, 231, 4321 | 1, 2, 4, 6, 3, 1, 0, ... | |
132, 213, 1234 | A000073 | 1, 2, 4, 7, 13, 24, 44, 81, 149, ... |
213,
231, | A000124 | 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, ... |
上表使用的缩写总结如下。
缩写 | 类中的模式 |
123, 132, 213, 232, 312, 321 | |
1432, 2143, 3214, 4132, 4213, 4312 | |
1234, 1243, 1324, 1342, 1423, 2134, 2314, 2341, 2413, 2431, 3124, 3142, 3241, 3412, 3421, 4123, 4231 | |
1234, 1243, 1423, 1432 |