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