A086955 -id:A086955 - 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

A086970 Fix 1, then exchange the subsequent odd numbers in pairs.

Original entry on oeis.org

1, 5, 3, 9, 7, 13, 11, 17, 15, 21, 19, 25, 23, 29, 27, 33, 31, 37, 35, 41, 39, 45, 43, 49, 47, 53, 51, 57, 55, 61, 59, 65, 63, 69, 67, 73, 71, 77, 75, 81, 79, 85, 83, 89, 87, 93, 91, 97, 95, 101, 99, 105, 103, 109, 107, 113, 111, 117, 115, 121, 119

Offset: 0

Paul Barry, Jul 26 2003

Partial sums are A086955.

Vincenzo Librandi, Table of n, a(n) for n = 0..2000
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Cf. A004442, A014681, A065190.

[1] cat [2*n+1-2*(-1)^n: n in [1..70]]; // Vincenzo Librandi, Jun 21 2017

Join[{1}, LinearRecurrence[{1, 1, -1}, {5, 3, 9}, 60]] (* Vincenzo Librandi, Jun 21 2017 *)

Vec((1+4*x-3*x^2+2*x^3)/((1+x)*(1-x)^2) + O(x^100)) \\ Michel Marcus, Jun 21 2017

G.f.: (1+4*x-3*x^2+2*x^3)/((1+x)*(1-x)^2).
a(n) = n + abs(2 - (n + 1)*(-1)^n). - Lechoslaw Ratajczak, Dec 09 2016
a(n) = 2*A065190(n+1)-1 and a(n) = 2*A014681(n)+1. - Michel Marcus, Dec 10 2016
From Guenther Schrack, Jun 09 2017: (Start)
a(n) = 2*n + 1 - 2*(-1)^n for n > 0.
a(n) = 2*n + 1 - 2*cos(n*Pi) for n > 0.
a(n) = 4*n - a(n-1) for n > 1.
Linear recurrence: a(n) = a(n-1) + a(n-2) - a(n-3) for n > 3.
First differences: 2 - 4*(-1)^n for n > 1; -(-1)^n*A010696(n) for n > 1.
a(n) = A065164(n+1) + n for n > 0.
a(A014681(n)) = A005408(n) for n >= 0.
a(A005408(A014681(n)) for n >= 0.
a(n) = A005408(A103889(n)) for n >= 0.
A103889(a(n)) = 2*A065190(n+1) for n >= 0.
a(2*n-1) = A004766(n) for n > 0.
a(2*n+2) = A004767(n) for n >= 0. (End)

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