|
|
A000434
|
|
Number of permutations of [n] in which the longest increasing run has length 4.
(Formerly M4556 N1938)
|
|
6
|
|
|
0, 0, 0, 1, 8, 67, 602, 5811, 60875, 690729, 8457285, 111323149, 1569068565, 23592426102, 377105857043, 6387313185576, 114303481217657, 2155348564847332, 42719058006864690, 887953677898186108, 19316200230609433690, 438920223893512987430
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
REFERENCES
|
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261. (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
|
Alois P. Heinz, Table of n, a(n) for n = 1..450 (first 100 terms from Max Alekseyev)
Max A. Alekseyev, On the number of permutations with bounded runs length, arXiv preprint arXiv:1205.4581 [math.CO], 2012-2013. - From N. J. A. Sloane, Oct 23 2012
|
|
EXAMPLE
|
a(5)=8 because we have (1235)4, (1245)3, (1345)2, (2345)1, 5(1234), 4(1235), 3(1245) and 2(1345), where the parentheses surround increasing runs of length 4.
|
|
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, 4];
Array[a, 30] (* Jean-François Alcover, Jul 19 2018, after Alois P. Heinz *)
|
|
CROSSREFS
|
Column 4 of A008304. Other columns: A000303, A000402, A000456, A000467.
Cf. A001250, A001251, A001252, A001253, A010026, A211318.
Sequence in context: A091645 A015574 A152055 * A304073 A250258 A192091
Adjacent sequences: A000431 A000432 A000433 * A000435 A000436 A000437
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
EXTENSIONS
|
Better description from Emeric Deutsch, May 08 2004
Terms a(16)-a(18) corrected and further terms added by Max Alekseyev, May 20 2012
|
|
STATUS
|
approved
|
|
|
|