login
Number of permutations of order n with the length of longest run equal to 5.
(Formerly M2123 N0840)
12

%I M2123 N0840 #41 Mar 22 2024 19:18:35

%S 0,0,0,0,2,20,198,2048,22468,264538,3340962,45173518,652209564,

%T 10024669626,163546399460,2823941647390,51468705947590,

%U 987671243816650,19909066390361346,420650676776338140,9297308938203169622,214562999510569012168

%N Number of permutations of order n with the length of longest run equal to 5.

%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 262. (Terms for n>=13 are incorrect.)

%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="/A001253/b001253.txt">Table of n, a(n) for n = 1..450</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

%t length = 5;

%t g[u_, o_, t_] := g[u, o, t] = If[u+o == 0, 1, Sum[g[o + j - 1, u - j, 2], {j, 1, u}] + If[t<length, Sum[g[u + j - 1, o - j, t+1], {j, 1, o}], 0]];

%t b[u_, o_, t_] := b[u, o, t] = If[t == length, g[u, o, t], Sum[b[o + j - 1, u - j, 2], {j, 1, u}] + Sum[b[u + j - 1, o - j, t + 1], {j, 1, o}]];

%t a[n_] := Sum[b[j - 1, n - j, 1], {j, 1, n}];

%t Table[a[n], {n, 1, 30}] (* _Jean-François Alcover_, Aug 18 2018, after _Alois P. Heinz_ *)

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

%K nonn

%O 1,5

%A _N. J. A. Sloane_

%E Corrected and extended by _Max Alekseyev_ at the suggestion of _Sean A. Irvine_, May 04 2012