login
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.
14

%I #28 Feb 29 2024 10:20:32

%S 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,

%T 0,1,34,189,480,788,1315,2233,0,1,69,526,2187,3500,5987,10409,17641,0,

%U 1,125,1625,6811,18273,30568,53791,92917,158769,0,1,251,4111,23507,101424,167480,299769,528253,925337,1578667

%N 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.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/K-sorted_sequence">K-sorted sequence</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>

%e T(4,1) = 1: 1234.

%e T(4,2) = 5: 1243, 1324, 2134, 2143, 3142.

%e T(4,3) = 7: 1342, 1423, 1432, 2314, 2413, 3124, 3214.

%e T(4,4) = 11: 2341, 2431, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321.

%e Triangle T(n,k) begins:

%e 1;

%e 0, 1;

%e 0, 1, 1;

%e 0, 1, 2, 3;

%e 0, 1, 5, 7, 11;

%e 0, 1, 9, 22, 33, 55;

%e 0, 1, 19, 77, 112, 192, 319;

%e 0, 1, 34, 189, 480, 788, 1315, 2233;

%e 0, 1, 69, 526, 2187, 3500, 5987, 10409, 17641;

%e 0, 1, 125, 1625, 6811, 18273, 30568, 53791, 92917, 158769;

%e ...

%p q:= proc(l, k) local i; for i from 1 to nops(l)-k do

%p if l[i]>=l[i+k] then return 0 fi od; 1

%p end:

%p m:= proc(l) local k;

%p for k from 0 to nops(l) do if q(l, k)>0 then return k fi od

%p end:

%p b:= proc(n) b(n):= add(x^m(l), l=combinat[permute](n)) end:

%p T:= (n, k)-> coeff(b(n), x, k):

%p seq(seq(T(n, k), k=0..n), n=0..8);

%t q[l_, k_] := Module[{i}, For[i = 1, i <= Length[l] - k, i++, If[l[[i]] >= l[[i + k]], Return [0]]]; 1];

%t m[l_] := Module[{k}, For[k = 0, k <= Length[l], k++, If[q[l, k] > 0, Return[k]]]];

%t b[n_] := Sum[x^m[l], {l, Permutations[Range@n]}];

%t T[n_, k_] := Coefficient[b[n], x, k];

%t Table[Table[T[n, k], {k, 0, n}], {n, 0, 8}] // Flatten (* _Jean-François Alcover_, Feb 29 2024, after _Alois P. Heinz_ *)

%Y Columns k=0-2 give: A000007, A057427, A014495.

%Y Main diagonal gives A370514, also A370506(n,1) for n>=1.

%Y Row sums give A000142.

%Y Cf. A370505.

%K nonn,tabl

%O 0,9

%A _Alois P. Heinz_, Feb 20 2024