A370507 T(n,k) is the number permutations p of [n] that are k-dist-increasing but not j-dist-increasing for any j<k, where p is j-dist-increasing if j>=0 and p(i)<p(i+j) for all i in [n-j]; triangle T(n,k), n>=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,9

Links

Table of n, a(n) for n=0..65.

Wikipedia, K-sorted sequence

Wikipedia, Permutation

Example

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

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

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.

Sequence in context: A163465 A360380 A370505 * A263230 A364257 A366258

Adjacent sequences: A370504 A370505 A370506 * A370508 A370509 A370510

Keyword

nonn,tabl

Author

Alois P. Heinz, Feb 20 2024

Status

approved