Voozh

A000303

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

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

(list; graph; refs; listen; history; text; internal format)

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