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

Author

Alois P. Heinz, Feb 20 2024

Keywords

• nonn
• tabl

Examples

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

Links

• Wikipedia, K-sorted sequence
• Wikipedia, Permutation

Crossrefs

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.

Programs

Maple

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

Mathematica

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