login
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

%I #17 Dec 30 2015 18:35:51

%S 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,

%T 24,114,420,429,1,1,2,6,24,120,612,2042,1430,1,1,2,6,24,120,696,3600,

%U 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

%N Number of permutations of [n] avoiding the generalized patterns 1(k+2)-(u_1+1)-...-(u_k+1) for all permutations u of [k].

%C The sequence reads the antidiagonals of the table [a(n,k)] (for k >= 0 and n >= 1). See examples below.

%C 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].

%C 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].

%C 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.

%C 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.

%H V. Pilaud, <a href="http://arxiv.org/abs/1505.07665">Brick polytopes, lattice quotients, and Hopf algebras</a>, arXiv:1505.07665 [math.CO], 2015.

%F a(n,0) = 1.

%F a(n,1) = binomial(2n,n)/(n+1) (Catalan number A000108).

%F When n <= k+1, a(n,k) = n! (factorial A000142).

%e Table a(n,k) begins (row index n >= 1, column index k >= 0):

%e 1 1 1 1 1 1 1 1 1 1 ...

%e 1 2 2 2 2 2 2 2 2 2 ...

%e 1 5 6 6 6 6 6 6 6 6 ...

%e 1 14 22 24 24 24 24 24 24 24 ...

%e 1 42 92 114 120 120 120 120 120 120 ...

%e 1 132 420 612 696 720 720 720 720 720 ...

%e 1 429 2042 3600 4512 4920 5040 5040 5040 5040 ...

%e 1 1430 10404 22680 31920 37200 39600 40320 40320 40320 ...

%e 1 4862 54954 150732 242160 305280 341280 357840 362880 362880 ...

%e 1 16796 298648 1045440 1942800 2680800 3175200 3457440 3588480 3628800 ...

%e ..........................................................................

%Y Cf. A000108, A000142.

%K nonn,tabl

%O 1,5

%A _Vincent Pilaud_, Oct 26 2015