|
|
A000402
|
|
Number of permutations of [n] in which the longest increasing run has length 3.
(Formerly M4239 N1771)
|
|
6
|
|
|
0, 0, 1, 6, 41, 293, 2309, 19975, 189524, 1960041, 21993884, 266361634, 3465832370, 48245601976, 715756932697, 11277786883720, 188135296651083, 3313338641692957, 61444453534759589, 1196988740015236617, 24442368179977776766, 522124104504306695929
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
REFERENCES
|
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261, Table 7.4.1. (Values for n>=16 are incorrect.)
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
EXAMPLE
|
a(4)=6 because we have (124)3, (134)2, (234)1, 4(123), 3(124) and 2(134), where the parentheses surround increasing runs of length 3.
|
|
MATHEMATICA
|
b[u_, o_, t_, k_] := b[u, o, t, k] = If[t == k, (u + o)!, If[Max[t, u] + o < k, 0, Sum[b[u + j - 1, o - j, t + 1, k], {j, 1, o}] + Sum[b[u - j, o + j - 1, 1, k], {j, 1, u}]]];
T[n_, k_] := b[0, n, 0, k] - b[0, n, 0, k + 1];
a[n_] := T[n, 3];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Terms a(16), a(17) are corrected and further terms added by Max Alekseyev, May 20 2012
|
|
STATUS
|
approved
|
|
|
|