|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
LINKS
|
|
|
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);
|
|
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)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|