login
A001267
One-half the number of permutations of length n with exactly 3 rising or falling successions.
(Formerly M4550 N1934)
8
0, 0, 0, 0, 1, 8, 60, 444, 3599, 32484, 325322, 3582600, 43029621, 559774736, 7841128936, 117668021988, 1883347579515, 32026067455084, 576605574327174, 10957672400252944, 219190037987444577, 4603645435776504120, 101292568208941883236, 2329975164242735146316
OFFSET
0,6
COMMENTS
(1/2) times number of permutations of 12...n such that exactly 3 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^3 in S[n](t) defined in A002464, divided by 2.
a(n) ~ 2/(3*exp(2)) * n!. - Vaclav Kotesovec, Aug 10 2013
Recurrence: (n-4)*(2*n^6 - 52*n^5 + 557*n^4 - 3136*n^3 + 9740*n^2 - 15727*n + 10242)*a(n) = + (n-4)*(2*n^7 - 50*n^6 + 511*n^5 - 2693*n^4 + 7450*n^3 - 9041*n^2 - 157*n + 6666)*a(n-1) - (2*n^8 - 58*n^7 + 735*n^6 - 5289*n^5 + 23430*n^4 - 64575*n^3 + 106105*n^2 - 92312*n + 30900)*a(n-2) - (2*n^7 - 54*n^6 + 615*n^5 - 3795*n^4 + 13554*n^3 - 27681*n^2 + 29473*n - 12330)*(n-2)*a(n-3) + (2*n^6 - 40*n^5 + 327*n^4 - 1388*n^3 + 3184*n^2 - 3675*n + 1626)*(n-2)^2*a(n-4). - Vaclav Kotesovec, Aug 10 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-> coeff(S(n), t, 3)/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_] := Coefficient[S[n], t, 3]/2; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Mar 11 2014, after Alois P. Heinz *)
CROSSREFS
Cf. A002464, A000130, A086852. Equals A086854/2. A diagonal of A010028.
Sequence in context: A094169 A129325 A285391 * A099156 A245391 A254658
KEYWORD
nonn
STATUS
approved