A086852 Number of permutations of length n with exactly 1 rising or falling succession.

0, 0, 2, 4, 10, 40, 230, 1580, 12434, 110320, 1090270, 11876980, 141373610, 1825321016, 25405388150, 379158271420, 6039817462210, 102278890975360, 1834691141852174, 34752142215026180, 693126840194499290, 14519428780464454600, 318705819455462421670

Offset

0,3

Comments

Permutations of 12...n such that exactly one 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.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..200

Sergey Kitaev, Jeffrey Remmel, (a,b)-rectangle patterns in permutations and words, arXiv:1304.4286 [math.CO], 2013.

J. Riordan, A recurrence for permutations without rising or falling successions, Ann. Math. Statist. 36 (1965), 708-710.

Formula

Coefficient of t^1 in S[n](t) defined in A002464.

(3-n)*a(n) +(n+1)*(n-3)*a(n-1) -(n^2-4*n+5)*a(n-2) -(n-1)*(n-5)*a(n-3) +(n-1)*(n-2)*a(n-4)=0. - R. J. Mathar, Jun 06 2013

a(n) ~ 2*sqrt(2*Pi)*n!/exp(2) = 0.678470495... * n!. - 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, 1):
seq(a(n), n=0..30);  # Alois P. Heinz, Dec 21 2012

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, 1]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 11 2014, after Alois P. Heinz *)

Crossrefs

Cf. A002464, A086853, A086854, A000349, A001267.

Twice A000130. A diagonal of A001100.

Sequence in context: A193675 A326904 A111022 * A084737 A322698 A153757

Adjacent sequences: A086849 A086850 A086851 * A086853 A086854 A086855

Keyword

nonn

Author

N. J. A. Sloane, Aug 19 2003

Status

approved