login
A001268
One-half the number of permutations of length n with exactly 4 rising or falling successions.
(Formerly M4805 N2053)
5
0, 0, 0, 0, 0, 1, 11, 113, 1099, 11060, 118484, 1366134, 16970322, 226574211, 3240161105, 49453685911, 802790789101, 13815657556958, 251309386257874, 4818622686395380, 97145520138758844, 2054507019515346789, 45484006970415223287, 1052036480881734378541
OFFSET
0,7
COMMENTS
(1/2) times number of permutations of 12...n such that exactly 4 of the following occur: 12, 23, ..., (n-1)n, 21, 32, ..., n(n-1).
REFERENCES
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263.
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
J. Riordan, A recurrence for permutations without rising or falling successions, Ann. Math. Statist. 36 (1965), 708-710.
FORMULA
Coefficient of t^4 in S[n](t) defined in A002464, divided by 2.
Recurrence (for n>5): (n-5)*(n^8 - 41*n^7 + 730*n^6 - 7358*n^5 + 45799*n^4 - 179702*n^3 + 432498*n^2 - 581244*n + 332100)*a(n) = (n^10 - 45*n^9 + 895*n^8 - 10301*n^7 + 75340*n^6 - 361190*n^5 + 1124682*n^4 - 2150033*n^3 + 2147364*n^2 - 499899*n - 544266)*a(n-1) - (n^10 - 44*n^9 + 869*n^8 - 10112*n^7 + 76390*n^6 - 388742*n^5 + 1336932*n^4 - 3028095*n^3 + 4237931*n^2 - 3198426*n + 917988)*a(n-2) - (n^10 - 43*n^9 + 823*n^8 - 9195*n^7 + 66108*n^6 - 318138*n^5 + 1033118*n^4 - 2224673*n^3 + 3023402*n^2 - 2325285*n + 761190)*a(n-3) + (n^8 - 33*n^7 + 471*n^6 - 3783*n^5 + 18594*n^4 - 56865*n^3 + 104723*n^2 - 104847*n + 42783)*(n-2)^2*a(n-4). - Vaclav Kotesovec, Aug 11 2013
a(n) ~ n!*exp(-2)/3. - Vaclav Kotesovec, Aug 11 2013
MAPLE
S:= proc(n) option remember; `if`(n<4, [1, 1, 2*t, 4*t+2*t^2]
[n+1], expand((n+1-t)*S(n-1) -(1-t)*(n-2+3*t)*S(n-2)
-(1-t)^2*(n-5+t)*S(n-3) +(1-t)^3*(n-3)*S(n-4)))
end:
a:= n-> ceil(coeff(S(n), t, 4)/2):
seq(a(n), n=0..25); # Alois P. Heinz, Jan 11 2013
MATHEMATICA
S[n_] := S[n] = If[n<4, {1, 1, 2*t, 4*t + 2*t^2}[[n+1]], Expand[(n+1-t)*S[n-1] - (1-t)*(n-2+3*t)*S[n-2] - (1-t)^2*(n-5+t)*S[n-3] + (1-t)^3*(n-3)*S[n-4]]]; a[n_] := Ceiling[Coefficient[S[n], t, 4]/2]; Table [a[n], {n, 0, 25}] (* Jean-François Alcover, Mar 24 2014, after Alois P. Heinz *)
CROSSREFS
Cf. A002464, A000130, A086852. Equals A086855/2. A diagonal of A010028.
Sequence in context: A166572 A111463 A142483 * A065538 A287837 A276200
KEYWORD
nonn
STATUS
approved