A191721 Permutations in S_n avoiding the patterns {4321, 34512, 45123, 35412, 43512, 45132, 45213, 53412, 45312, 45231}.

1, 1, 2, 6, 23, 94, 391, 1633, 6827, 28548, 119384, 499255, 2087854, 8731285, 36513737, 152698377, 638575958, 2670488470, 11167831459, 46703238346, 195310296371, 816776592369, 3415713427499, 14284320005992, 59736216859096, 249813474014875, 1044705792912602

Offset

0,3

Comments

A(n) is also the number of w in S_n for which the number of repeated letters in a reduced decomposition of w equals the number of 321- and 3412-patterns in w.

The generating function can be automatically computed by the Maple package INSENC listed in the links. - Vincent Vatter, Jun 16 2011

Links

Harvey P. Dale, Table of n, a(n) for n = 0..1000

B. E. Tenner, Repetition in reduced decompositions, arXiv:1106.2839 [math.CO]

V. Vatter, Maple package INSENC

Index entries for linear recurrences with constant coefficients, signature (5,-3,-2,1).

Formula

G.f.: (1-4*x+x^3)/((1-x)*(1-4*x-x^2+x^3)). - Vincent Vatter, Jun 16 2011

Example

A(4)=23 because all permutations in S_4 except 4321 avoid these patterns.  Also, all permutations in S_4 except 4321 have repeated letters equaling the number of 321- and 3412-patterns.  (Note that 4321 has 3 repeated letters, but 4 of these patterns.)

Mathematica

LinearRecurrence[{5, -3, -2, 1}, {1, 1, 2, 6}, 30] (* Harvey P. Dale, Apr 03 2022 *)

Crossrefs

Sequence in context: A150290 A150291 A150292 * A150293 A370285 A371827

Adjacent sequences: A191718 A191719 A191720 * A191722 A191723 A191724

Keyword

nonn

Author

Bridget Tenner, Jun 13 2011

Extensions

a(0)=1 prepended and more terms from Alois P. Heinz, Jun 17 2021

Status

approved