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.

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

Author

Alois P. Heinz, Feb 20 2024

Keywords

• nonn
• tabl

Examples

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

Links

• Wikipedia, K-sorted sequence
• Wikipedia, Permutation

Crossrefs

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.

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

Mathematica

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

Formula

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