A000402 Number of permutations of [n] in which the longest increasing run has length 3.

0, 0, 1, 6, 41, 293, 2309, 19975, 189524, 1960041, 21993884, 266361634, 3465832370, 48245601976, 715756932697, 11277786883720, 188135296651083, 3313338641692957, 61444453534759589, 1196988740015236617, 24442368179977776766, 522124104504306695929

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Examples

			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.
		

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

• Alois P. Heinz, Table of n, a(n) for n = 1..452 (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

Crossrefs

Column 3 of A008304. Other columns: A000303, A000434, A000456, A000467.

Cf. A001250, A001251, A001252, A001253, A010026, A211318.

Programs

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];
Array[a, 30] (* Jean-François Alcover, Jul 19 2018, after Alois P. Heinz *)

Extensions

Better description from Emeric Deutsch, May 08 2004

Terms a(16), a(17) are corrected and further terms added by Max Alekseyev, May 20 2012