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

%I M3522 N1430 #38 Feb 22 2020 22:27:18

%S 0,1,4,16,69,348,2016,13357,99376,822040,7477161,74207208,797771520,

%T 9236662345,114579019468,1516103040832,21314681315997,317288088082404,

%U 4985505271920096,82459612672301845,1432064398910663704,26054771465540507272

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

%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261, Table 7.4.1.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A000303/b000303.txt">Table of n, a(n) for n = 1..464</a> (first 100 terms from Max Alekseyev)

%H Max A. Alekseyev, <a href="http://arxiv.org/abs/1205.4581">On the number of permutations with bounded runs length</a>, arXiv preprint arXiv:1205.4581 [math.CO], 2012-2013. - From _N. J. A. Sloane_, Oct 23 2012

%e a(3)=4 because we have (13)2, 2(13), (23)1, 3(12), where the parentheses surround increasing runs of length 2.

%t 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 T[n_, k_] := b[0, n, 0, k] - b[0, n, 0, k + 1];

%t a[n_] := T[n, 2];

%t Array[a, 30] (* _Jean-François Alcover_, Jul 19 2018, after _Alois P. Heinz_ *)

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

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

%Y Equals 1 less than A049774. - _Greg Dresden_, Feb 22 2020

%K nonn

%O 1,3

%A _N. J. A. Sloane_

%E Better description from _Emeric Deutsch_, May 08 2004

%E Edited and extended by _Max Alekseyev_, May 20 2012