login
A166298
Number of simsun permutations of {1,2,...,n} having at least one 321 pattern. A permutation p in S_n is said to be simsun if it has no double descents and with the hereditary property that when n, n-1, ..., 2, 1 are deleted in succession, the property of not having double descents is preserved after each deletion.
0
0, 0, 0, 0, 2, 19, 140, 956, 6506, 45659, 336996, 2643979, 22160244, 198618081, 1901082872, 19381817300, 209829985306, 2404750030651, 29088407474132, 370369420974335, 4951491489003676, 69348849926870881, 1015423795024288712
OFFSET
0,5
FORMULA
a(n) = E(n+1) - C(n), where E(k) are the Euler (or up-down numbers; A000111(k)) and C(k) are the Catalan numbers (A000108(k)).
EXAMPLE
a(4)=2 because we have 4132 and 4231 (the other C(4)=14 simsun permutations of {1,2,3,4} have no 321 patterns at all).
MAPLE
f := sec(x)+tan(x): fser := series(f, x = 0, 52): E := proc (n) options operator, arrow: factorial(n)*coeff(fser, x, n) end proc: C := proc (n) options operator, arrow: binomial(2*n, n)/(n+1) end proc: seq(E(n+1)-C(n), n = 0 .. 23);
MATHEMATICA
A000111[n_] := If[EvenQ[n], Abs[EulerE[n]], Abs[(2^(n+1)*(2^(n+1)-1)* BernoulliB[n+1])/(n+1)]];
a[n_] := A000111[n+1] - CatalanNumber[n];
Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Aug 12 2024 *)
PROG
(Python)
from itertools import count, islice, accumulate
def A166298_gen(): # generator of terms
yield 0
blist, c = (0, 1), 1
for n in count(1):
yield (blist := tuple(accumulate(reversed(blist), initial=0)))[-1] - c
c = c*(4*n+2)//(n+2)
A166298_list = list(islice(A166298_gen(), 20)) # Chai Wah Wu, Jun 10-11 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Oct 29 2009
STATUS
approved