A086856 -id:A086856 - cp's OEIS frontend

A001100 Triangle read by rows: T(n,k) = number of permutations of length n with exactly k rising or falling successions, for n >= 1, 0 <= k <= n-1.

1, 0, 2, 0, 4, 2, 2, 10, 10, 2, 14, 40, 48, 16, 2, 90, 230, 256, 120, 22, 2, 646, 1580, 1670, 888, 226, 28, 2, 5242, 12434, 12846, 7198, 2198, 366, 34, 2, 47622, 110320, 112820, 64968, 22120, 4448, 540, 40, 2, 479306, 1090270, 1108612, 650644, 236968, 54304, 7900, 748, 46, 2

Offset: 1

N. J. A. Sloane, Aug 19 2003

Number of permutations of 12...n such that exactly k of the following occur: 12, 23, ..., (n-1)n, 21, 32, ..., n(n-1).

			Triangle T(n,k) begins (n >= 1, k = 0..n-1):
    1;
    0,    2;
    0,    4,    2;
    2,   10,   10,   2;
   14,   40,   48,  16,   2;
   90,  230,  256, 120,  22,  2;
  646, 1580, 1670, 888, 226, 28, 2;
  ...

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263.
J. Riordan, A recurrence for permutations without rising or falling successions. Ann. Math. Statist. 36 (1965), 708-710.
David Sankoff and Lani Haque, Power Boosts for Cluster Tests, in Comparative Genomics, Lecture Notes in Computer Science, Volume 3678/2005, Springer-Verlag.

Alois P. Heinz, Rows n = 1..141, flattened
D. P. Robbins, The probability that neighbors remain neighbors after random rearrangements, Amer. Math. Monthly 87 (1980), 122-124.

Columns give A002464, A086852, A086853, A086854, A086955.
Triangle in A086856 multiplied by 2. Cf. A010028.
Cf. A322294, A322295, A322296.

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:
T:= (n, k)-> coeff(S(n), t, k):
seq(seq(T(n, k), k=0..n-1), n=1..10);  # Alois P. Heinz, Jan 11 2013

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]]]; t[n_, k_] := Ceiling[Coefficient[s[n], t, k]]; Flatten[ Table[ Table[t[n, k], {k, 0, n - 1}], {n, 1, 10}]] (* Jean-François Alcover, Jan 25 2013, translated from Alois P. Heinz's Maple program *)

Let T{n, k} = number of permutations of 12...n with exactly k rising or falling successions. Let S[n](t) = Sum_{k >= 0} T{n, k}*t^k. Then S[0] = 1; S[1] = 1; S[2] = 2*t; S[3] = 4*t+2*t^2; for n >= 4, S[n] = (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].

T(n, 0) = n! + Sum_{i=1..m-1} (-1)^i*(n-i)!*Sum_{j=1..i} 2^j*binomial(i-1, j-1)*binomial(n-i, j), and T(n, k) = Sum_{i=1..m-1} (-1)^(i-k)*binomial(i, k)*(n-i)!*Sum_{j=1..i} 2^j*binomial(i-1, j-1)*binomial(n-i, j), for k >= 1, and n >= 1. See the D. P.Robbins link for A(n, k) = T(n, k), and his comment concerning the case k = i = 0 . - Wolfdieter Lang, May 17 2025

A010028 Triangle read by rows: T(n,k) is one-half the number of permutations of length n with exactly n-k rising or falling successions, for n >= 1, 1 <= k <= n. T(1,1) = 1 by convention.

Original entry on oeis.org

1, 1, 0, 1, 2, 0, 1, 5, 5, 1, 1, 8, 24, 20, 7, 1, 11, 60, 128, 115, 45, 1, 14, 113, 444, 835, 790, 323, 1, 17, 183, 1099, 3599, 6423, 6217, 2621, 1, 20, 270, 2224, 11060, 32484, 56410, 55160, 23811, 1, 23, 374, 3950, 27152, 118484, 325322, 554306, 545135, 239653

Offset: 1

N. J. A. Sloane

(1/2) times number of permutations of 12...n such that exactly n-k of the following occur: 12, 23, ..., (n-1)n, 21, 32, ..., n(n-1).

			Triangle T(n,k) begins:
  1;
  1,  0;
  1,  2,   0;
  1,  5,   5,    1;
  1,  8,  24,   20,    7;
  1, 11,  60,  128,  115,   45;
  1, 14, 113,  444,  835,  790,  323;
  1, 17, 183, 1099, 3599, 6423, 6217, 2621;
  ...

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263.

Alois P. Heinz, Rows n = 1..141, flattened
J. Riordan, A recurrence for permutations without rising or falling successions, Ann. Math. Statist. 36 (1965), 708-710.

Diagonals give A001266 (and A002464), A000130, A000349, A001267, A001268.
Triangle in A086856 transposed. Cf. A001100.
Row sums give A001710.

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:
T:= (n, k)-> ceil(coeff(S(n), t, n-k)/2):
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Dec 21 2012

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]]]; T[n_, k_] := Ceiling[Coefficient[S[n], t, n-k]/2]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Jan 14 2014, translated from Alois P. Heinz's Maple code *)

For n>1, coefficient of t^(n-k) in S[n](t) defined in A002464, divided by 2.

A001266 One-half the number of permutations of length n without rising or falling successions.

Original entry on oeis.org

0, 0, 1, 7, 45, 323, 2621, 23811, 239653, 2648395, 31889517, 415641779, 5830753109, 87601592187, 1403439027805, 23883728565283, 430284458893701, 8181419271349931, 163730286973255373, 3440164703027845395, 75718273707281368117, 1742211593431076483419

Offset: 2

N. J. A. Sloane

nonn

(1/2) times number of permutations of 1, 2..., n such that none of the following occur: 12, 23, ..., (n-1)n, 21, 32, ..., n(n-1).

a(n) is also the number of Hamiltonian paths in the n-path complement graph. - Eric W. Weisstein, Apr 11 2018

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

Seiichi Manyama, Table of n, a(n) for n = 2..450 (first 199 terms from Alois P. Heinz)
J. Riordan, A recurrence for permutations without rising or falling successions, Ann. Math. Statist. 36 (1965), 708-710.
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Path Complement Graph

Sequence A002464 divided by 2 for n >= 2. A diagonal of A010028. A086856.

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, 0)/2:
seq(a(n), n=2..25);  # Alois P. Heinz, Jan 11 2013

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, 0]/2; Table[a[n], {n, 2, 25}] (* Jean-François Alcover, Mar 24 2014, after Alois P. Heinz *)
CoefficientList[Series[((Exp[(1 + x)/((-1 + x) x)] (1 + x) Gamma[0, (1 + x)/((-1 + x) x)])/((-1 + x) x) - x - 1)/(2 x), {x, 0, 20}], x] (* Eric W. Weisstein, Apr 11 2018 *)
RecurrenceTable[{a[n] == (n + 1) a[n - 1] - (n - 2) a[n - 2] - (n - 5) a[n - 3] + (n - 3) a[n - 4], a[0] == a[1] == 1/2,
a[2] == a[3] == 0}, a, {n, 2, 20}] (* Eric W. Weisstein, Apr 11 2018 *)

a(n) = A002464(n)/2 = A086856(n, 0).

(1/2) times coefficient of t^0 in S[n](t) defined in A002464.

More terms from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Feb 16 2001

A383857 Number of permutations of [n] such that precisely one rising or falling succession occurs, but without either n(n-1) or (n-1)n.

Original entry on oeis.org

0, 0, 2, 8, 34, 196, 1366, 10928, 98330, 983036, 10811134, 129714184, 1686103522, 23603603540, 354033474374, 5664286296416, 96289603698346, 1733166940314028, 32929480177913230, 658578501071986616, 13829959293448920434, 304255691156335505924

Offset: 1

Wolfdieter Lang, May 19 2025

See A086852 or 2*A000130 for the counting including the successions n(n-1) and (n-1)n. See also the k = 1 columns of the triangles A001100 and 2*A086856.

For the number of permutations of length n without rising or falling successions see A002464(n).

			a(3) = 2*1 from the permutations 213 and the reverted 312.
a(4) = 2*4 from 1324, 1423, 2314, 3124 and the reverted 4231, 3241, 4132, 4213.
a(5) = 2*17 from the permutations corresponding to A086852(5) = 2*20, without 13542, 24513, 25413, and the reverted 24531, 31542, 31452.

Cf. A000130, A001100, A002464, A086852, A086856.

a(n) = A002464(n+1) - (n-1) * A002464(n).

cp's OEIS Frontend

A001100 Triangle read by rows: T(n,k) = number of permutations of length n with exactly k rising or falling successions, for n >= 1, 0 <= k <= n-1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A010028 Triangle read by rows: T(n,k) is one-half the number of permutations of length n with exactly n-k rising or falling successions, for n >= 1, 1 <= k <= n. T(1,1) = 1 by convention.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A001266 One-half the number of permutations of length n without rising or falling successions.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A383857 Number of permutations of [n] such that precisely one rising or falling succession occurs, but without either n(n-1) or (n-1)n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula