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).

For the number of such permutations without (n-1)n or n(n-1) see A383857(n), for n >= 1. - Wolfdieter Lang, May 22 2025

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.

D. P. Robbins, The probability that neighbors remain neighbors after random rearrangements, Amer. Math. Monthly 87 (1980), 122-124.

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

From Wolfdieter Lang, May 31 2025: (Start)

a(n) = Sum_{i=1..n-1} (-1)^(i-1)*i*(n-i)!*Sum_{j=1..i} 2^j*binomial(i-1, j-1)*binomial(n-i, j), for n >= 0. See the D. P. Robbins link, p. 123, eq. (7), A(n, 1).

a(n+2) = Sum_{k=0..n} 2*R(n, k)*B(n, k), with B(n, k) = A384494(n, k) = (-1)^k*(k+1)*(n+1-k)!, and R(n, k) = A104698(n, k), for n >= 0. This equals (2*MR*MB^t)_{n,n}, with the (infinite) square matrices with vanishing upper diagonals corresponding to R and B, and t indicates transposition. (End)

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, A383857.

Twice A000130. A diagonal of A001100.

Cf. A104698, A384494.

Sequence in context: A193675 A326904 A111022 * A084737 A322698 A153757

Adjacent sequences: A086849 A086850 A086851 * A086853 A086854 A086855

Keyword

nonn,easy

Author

N. J. A. Sloane, Aug 19 2003

Status

approved