A212884 Number of permutations in S_n whose Rothe diagram can be rearranged to give the complement of a skew shape.

1, 1, 2, 6, 24, 112, 572, 3116, 17871, 106959, 663526, 4243490, 27856087, 187029655, 1280660596, 8921737864, 63108620169, 452503644985, 3284213633684, 24098433889312, 178583179551488, 1335346240984360

Offset

0,3

Comments

Equivalent definitions:

(1) Permutations that have the form (a_1, a_2, ..., a_k, b_1, b_2, ..., b_(n - k)), where the subsequences (a_1, a_2, ..., a_k) and (b_1, b_2, ..., b_(n - k)) avoid the permutation pattern 2143 and a_i < b_j for all i, j.

(2) Permutations that avoid the nine permutation patterns 24153, 25143, 31524, 31542, 32514, 32541, 42153, 52143, and 214365.

Links

Joel B. Lewis, Table of n, a(n) for n = 0..50

A. J. Klein, J. B. Lewis and A. H. Morales, Counting matrices over finite fields with support on skew Young diagrams and complements of Rothe diagrams.

R. J. Mathar, D-finite recurrence

Formula

Ordinary g.f. is (1 - x)*V(x)^2 - V(x) + 1/(1 - x), where V(x) is the (ordinary) g.f. for A005802.

Crossrefs

Sequence in context: A308726 A168490 A118376 * A085486 A152318 A152328

Adjacent sequences: A212881 A212882 A212883 * A212885 A212886 A212887

Keyword

nonn

Author

Joel B. Lewis, May 29 2012

Status

approved