A370390 -id:A370390 - cp's OEIS frontend

A184182 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} whose longest block is of length k (0<=k<=n).

1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 11, 10, 2, 1, 0, 53, 53, 11, 2, 1, 0, 309, 334, 63, 11, 2, 1, 0, 2119, 2428, 415, 64, 11, 2, 1, 0, 16687, 20009, 3121, 425, 64, 11, 2, 1, 0, 148329, 184440, 26402, 3205, 426, 64, 11, 2, 1, 0, 1468457, 1881050, 248429, 27145, 3215, 426, 64, 11, 2, 1

Offset: 0

Emeric Deutsch, Feb 13 2011

A block of a permutation is a maximal sequence of consecutive integers which appear in consecutive positions. For example, the permutation 5412367 has 4 blocks: 5, 4, 123, and 67. Its longest block has length 3.

			T(3,1) = 3 because we have 132, 213, and 321.
T(4,3) = 2 because we have 4123 and 2341.
Triangle starts:
  1;
  0,   1;
  0,   1,   1;
  0,   3,   2,  1;
  0,  11,  10,  2,  1;
  0,  53,  53, 11,  2, 1;
  0, 309, 334, 63, 11, 2, 1;
  ...

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0..3 give A000007, A000255(n-1), A370390, A370392.
Cf. A000166, A184180.
Row sums are A000142.

d[-1]:= 0: d[0] := 1: for n to 40 do d[n] := n*d[n-1]+(-1)^n end do: b := proc (n, m, k) options operator, arrow: coeff(add(t^j, j = 1 .. k)^m, t, n) end proc: T := proc (n, k) options operator, arrow: add(b(n, m, k)*(d[m]+d[m-1]), m = 0 .. n)-add(b(n, m, k-1)*(d[m]+d[m-1]), m = 1 .. n) end proc: for n from 0 to 11 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form

b[n_, m_, k_] := Module[{t}, Coefficient[Total[t^Range[k]]^m, t, n]];
T[n_, k_] := If[n == 0, 1, Module[{d = Subfactorial}, Sum[(b[n, m, k] - b[n, m, k-1])*(d[m]+d[m-1]), {m, 1, n}]]];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Aug 06 2024 *)

T(n,k) = Sum_{m=1..n} (b(n,m,k)-b(n,m,k-1))*(d(m)+d(m-1)), where b(n,m,k) = coefficient of t^n in (t+t^2+...+t^k)^m and d(j) = A000166(j) are the derangement numbers.
T(n,1) = A000255(n-1) for n>=1.
Sum_{k=1..n} T(n,k) = n! (row sums).

Row n=0 and column k=0 added by Alois P. Heinz, Feb 17 2024

A370485 Number of permutations of [n] with the property that no subsequence k(k+1)(k+2) or (k+2)(k+1)k occurs but k(k+1) or (k+1)k occurs.

Original entry on oeis.org

0, 0, 2, 4, 16, 78, 480, 3436, 28050, 256868, 2607584, 29061022, 352747696, 4632195548, 65432845858, 989341728564, 15942876295728, 272777484786062, 4938657746907200, 94332342088674252, 1895781452461383986, 39987981759263286340, 883322358371147863168

Offset: 0

Seiichi Manyama, Feb 19 2024

nonn

			123 contains 3 consecutive number and 321 contains 3 consecutive number in reverse order. So a(3) = 6-2 = 4.

Seiichi Manyama, Table of n, a(n) for n = 0..449

Cf. A002464, A095816, A370390.

my(N=30, x='x+O('x^N)); concat([0, 0], Vec(sum(k=0, N, k!*x^k*(((1-2*x^2+x^3)/(1-x^3))^k-((1-2*x+x^2)/(1-x^2))^k))))

a(n) = A095816(n) - A002464(n).

G.f.: Sum_{k>=0} k! * x^k * ( ((1-2*x^2+x^3)/(1-x^3))^k - ((1-2*x+x^2)/(1-x^2))^k ).

cp's OEIS Frontend

A184182 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} whose longest block is of length k (0<=k<=n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions