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

Author

Joel B. Lewis, May 29 2012

Keywords

• nonn

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.