login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001251 Number of permutations of order n with the length of longest run equal to 3.
(Formerly M2031 N0803)
12

%I M2031 N0803 #42 Mar 22 2024 18:49:42

%S 0,0,2,12,70,442,3108,24216,208586,1972904,20373338,228346522,

%T 2763212980,35926266244,499676669254,7405014187564,116511984902094,

%U 1940073930857802,34087525861589564,630296344519286304,12235215845125112122,248789737587365945992

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

%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="/A001251/b001251.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

%H Richard Ehrenborg and JiYoon Jung, <a href="https://arxiv.org/abs/1312.2027">Descent pattern avoidance</a>, arXiv preprint:1312.2027 [math.CO], 6 Dec 2013.

%F a(n) ~ c * d^n * n!, where d = 0.92403585760753647721113386869798700855648617941... is the root of the equation 8 - 2*sin(sqrt(phi)/d) * (2*sqrt(5*(phi-1)) * cosh(sqrt(phi-1)/d) + 2*sinh(sqrt(phi-1)/d)) + 2*cos(sqrt(phi)/d) * (6*cosh(sqrt(phi-1)/d) + 2*sqrt(5*phi) * sinh(sqrt(phi-1)/d)) = 0, phi = A001622 = (1+sqrt(5))/2 is the golden ratio and c = 1.259371257828351725264434486385284120241474052544197367866029465830756911... - _Vaclav Kotesovec_, Sep 06 2014, updated Aug 18 2018

%t length = 3;

%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, A001252, A001253, A010026, A211318.

%K nonn,changed

%O 1,3

%A _N. J. A. Sloane_

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 20:05 EDT 2024. Contains 371254 sequences. (Running on oeis4.)