A000303 Number of permutations of [n] in which the longest increasing run has length 2. (Formerly M3522 N1430)

0, 1, 4, 16, 69, 348, 2016, 13357, 99376, 822040, 7477161, 74207208, 797771520, 9236662345, 114579019468, 1516103040832, 21314681315997, 317288088082404, 4985505271920096, 82459612672301845, 1432064398910663704, 26054771465540507272

Offset

1,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.

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..464 (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(3)=4 because we have (13)2, 2(13), (23)1, 3(12), where the parentheses surround increasing runs of length 2.

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

Crossrefs

Column 2 of A008304. Other columns: A000402, A000434, A000456, A000467, A230055.

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

Equals 1 less than A049774. - Greg Dresden, Feb 22 2020

Sequence in context: A339045 A341255 A231358 * A351186 A298048 A344267

Adjacent sequences: A000300 A000301 A000302 * A000304 A000305 A000306

Keyword

nonn

Author

N. J. A. Sloane

Extensions

Better description from Emeric Deutsch, May 08 2004

Edited and extended by Max Alekseyev, May 20 2012

Status

approved