|
| |
|
|
A263791
|
|
Number of permutations of [n] avoiding the generalized patterns 1(k+2)-(u_1+1)-...-(u_k+1) for all permutations u of [k].
|
|
0
|
|
|
|
1, 1, 1, 1, 2, 1, 1, 2, 5, 1, 1, 2, 6, 14, 1, 1, 2, 6, 22, 42, 1, 1, 2, 6, 24, 92, 132, 1, 1, 2, 6, 24, 114, 420, 429, 1, 1, 2, 6, 24, 120, 612, 2042, 1430, 1, 1, 2, 6, 24, 120, 696, 3600, 10404, 4862, 1, 1, 2, 6, 24, 120, 720, 4512, 22680, 54954, 16796, 1, 1, 2, 6, 24, 120, 720, 4920, 31920, 150732, 298648, 58786, 1, 1, 2, 6, 24, 120, 720, 5040, 37200, 242160, 1045440
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
The sequence reads the antidiagonals of the table [a(n,k)] (for k >= 0 and n >= 1). See examples below.
a(n,k) is the number of permutations of [n] avoiding the generalized patterns 1(k+2)-(u_1+1)-...-(u_k+1) for all permutations u of [k].
a(n,k) is the number of classes of the k-twist congruence on S_n, defined as the transitive closure of the rewriting rule UacV_1b_1...V_kb_kW = UcaV_1b_1...V_kb_kW for a < b_1, ..., b_k < c in [n] and U, V_1, ..., V_k, W some (possibly empty) words on [n].
a(n,k) is the number of (k,n)-twists whose contact graph is acyclic. A (k,n)-twist is a reduced pipe dream for the permutation (1, ..., k, n+k, ..., k+1, n+k+1, ..., n+2k). The contact graph of a (k,n)-twist is the graph with a node for each pipe and an oriented arc for each elbow from the pipe passing southeast of the elbow to the pipe passing northwest of the elbow.
a(n,k) is the number of vertices of the brick polytope for the word c^k w_o(c) where c = 1 2 ... n-1 is the linear Coxeter element in type A.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n,0) = 1.
a(n,1) = binomial(2n,n)/(n+1) (Catalan number A000108).
When n <= k+1, a(n,k) = n! (factorial A000142).
|
|
|
EXAMPLE
|
Table a(n,k) begins (row index n >= 1, column index k >= 0):
1 1 1 1 1 1 1 1 1 1 ...
1 2 2 2 2 2 2 2 2 2 ...
1 5 6 6 6 6 6 6 6 6 ...
1 14 22 24 24 24 24 24 24 24 ...
1 42 92 114 120 120 120 120 120 120 ...
1 132 420 612 696 720 720 720 720 720 ...
1 429 2042 3600 4512 4920 5040 5040 5040 5040 ...
1 1430 10404 22680 31920 37200 39600 40320 40320 40320 ...
1 4862 54954 150732 242160 305280 341280 357840 362880 362880 ...
1 16796 298648 1045440 1942800 2680800 3175200 3457440 3588480 3628800 ...
..........................................................................
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
