A370514 -id:A370514 - cp's OEIS frontend

A370507 T(n,k) is the number permutations p of [n] that are k-dist-increasing but not j-dist-increasing for any j=0 and p(i)=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 1, 2, 3, 0, 1, 5, 7, 11, 0, 1, 9, 22, 33, 55, 0, 1, 19, 77, 112, 192, 319, 0, 1, 34, 189, 480, 788, 1315, 2233, 0, 1, 69, 526, 2187, 3500, 5987, 10409, 17641, 0, 1, 125, 1625, 6811, 18273, 30568, 53791, 92917, 158769, 0, 1, 251, 4111, 23507, 101424, 167480, 299769, 528253, 925337, 1578667

Offset: 0

Alois P. Heinz, Feb 20 2024

			T(4,1) = 1: 1234.
T(4,2) = 5: 1243, 1324, 2134, 2143, 3142.
T(4,3) = 7: 1342, 1423, 1432, 2314, 2413, 3124, 3214.
T(4,4) = 11: 2341, 2431, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321.
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,   1;
  0, 1,   2,    3;
  0, 1,   5,    7,   11;
  0, 1,   9,   22,   33,    55;
  0, 1,  19,   77,  112,   192,   319;
  0, 1,  34,  189,  480,   788,  1315,  2233;
  0, 1,  69,  526, 2187,  3500,  5987, 10409, 17641;
  0, 1, 125, 1625, 6811, 18273, 30568, 53791, 92917, 158769;
  ...

Wikipedia, K-sorted sequence
Wikipedia, Permutation

Columns k=0-2 give: A000007, A057427, A014495.
Main diagonal gives A370514, also A370506(n,1) for n>=1.
Row sums give A000142.
Cf. A370505.

q:= proc(l, k) local i; for i from 1 to nops(l)-k do
      if l[i]>=l[i+k] then return 0 fi od; 1
    end:
m:= proc(l) local k;
      for k from 0 to nops(l) do if q(l, k)>0 then return k fi od
    end:
b:= proc(n) b(n):= add(x^m(l), l=combinat[permute](n)) end:
T:= (n, k)-> coeff(b(n), x, k):
seq(seq(T(n, k), k=0..n), n=0..8);

q[l_, k_] := Module[{i}, For[i = 1, i <= Length[l] - k, i++, If[l[[i]] >= l[[i + k]], Return [0]]]; 1];
m[l_] := Module[{k}, For[k = 0, k <= Length[l], k++, If[q[l, k] > 0, Return[k]]]];
b[n_] := Sum[x^m[l], {l, Permutations[Range@n]}];
T[n_, k_] := Coefficient[b[n], x, k];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 8}] // Flatten (* Jean-François Alcover, Feb 29 2024, after Alois P. Heinz *)

A370506 T(n,k) is the number permutations p of [n] that are j-dist-increasing for exactly k distinct values j in [n], where p is j-dist-increasing if j>=0 and p(i)=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 11, 8, 4, 1, 0, 55, 38, 19, 7, 1, 0, 319, 228, 110, 50, 12, 1, 0, 2233, 1574, 775, 322, 115, 20, 1, 0, 17641, 12524, 6216, 2611, 1033, 261, 33, 1, 0, 158769, 112084, 55692, 23585, 9103, 3006, 586, 54, 1, 0, 1578667, 1119496, 556754, 238425, 91764, 33929, 8372, 1304, 88, 1

Offset: 0

Alois P. Heinz, Feb 20 2024

			T(4,1) = 11: 2341, 2431, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321.
T(4,2) = 8: 1342, 1423, 1432, 2314, 2413, 3124, 3142, 3214.
T(4,3) = 4: 1243, 1324, 2134, 2143.
T(4,4) = 1: 1234.
Triangle T(n,k) begins:
  1;
  0,      1;
  0,      1,      1;
  0,      3,      2,     1;
  0,     11,      8,     4,     1;
  0,     55,     38,    19,     7,    1;
  0,    319,    228,   110,    50,   12,    1;
  0,   2233,   1574,   775,   322,  115,   20,   1;
  0,  17641,  12524,  6216,  2611, 1033,  261,  33,  1;
  0, 158769, 112084, 55692, 23585, 9103, 3006, 586, 54, 1;
  ...

Wikipedia, K-sorted sequence
Wikipedia, Permutation

Column k=0 gives A000007.
Column k=1 gives A370514 or A370507(n,n) for n>=1.
Row sums give A000142.
T(n,n-1) gives A000071(n+1).
Cf. A248687, A370505.

q:= proc(l, k) local i; for i from 1 to nops(l)-k do
      if l[i]>=l[i+k] then return 0 fi od; 1
    end:
b:= proc(n) option remember; add(x^add(
      q(l, j), j=1..n), l=combinat[permute](n))
    end:
T:= (n, k)-> coeff(b(n), x, k):
seq(seq(T(n,k), k=0..n), n=0..8);

q[l_, k_] := Module[{i}, For[i = 1, i <= Length[l]-k, i++,
    If[l[[i]] >= l[[i+k]], Return@0]]; 1];
b[n_] := b[n] = Sum[x^Sum[q[l, j], {j, 1, n}], {l, Permutations[Range[n]]}];
T[n_, k_] := Coefficient[b[n], x, k];
Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 24 2024, after Alois P. Heinz *)

Sum_{k=0..n} k * T(n,k) = A248687(n) for n>=1.

cp's OEIS Frontend

A370507 T(n,k) is the number permutations p of [n] that are k-dist-increasing but not j-dist-increasing for any j=0 and p(i)=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica