A370506 - OEIS

%I #33 Feb 24 2024 09:45:02

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

%T 0,2233,1574,775,322,115,20,1,0,17641,12524,6216,2611,1033,261,33,1,0,

%U 158769,112084,55692,23585,9103,3006,586,54,1,0,1578667,1119496,556754,238425,91764,33929,8372,1304,88,1

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

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

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

%e T(4,2) = 8: 1342, 1423, 1432, 2314, 2413, 3124, 3142, 3214.

%e T(4,3) = 4: 1243, 1324, 2134, 2143.

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

%e Triangle T(n,k) begins:

%e   1;

%e   0,      1;

%e   0,      1,      1;

%e   0,      3,      2,     1;

%e   0,     11,      8,     4,     1;

%e   0,     55,     38,    19,     7,    1;

%e   0,    319,    228,   110,    50,   12,    1;

%e   0,   2233,   1574,   775,   322,  115,   20,   1;

%e   0,  17641,  12524,  6216,  2611, 1033,  261,  33,  1;

%e   0, 158769, 112084, 55692, 23585, 9103, 3006, 586, 54, 1;

%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 b:= proc(n) option remember; add(x^add(

%p       q(l, j), j=1..n), l=combinat[permute](n))

%p     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++,

%t     If[l[[i]] >= l[[i+k]], Return@0]]; 1];

%t b[n_] := b[n] = Sum[x^Sum[q[l, j], {j, 1, n}], {l, Permutations[Range[n]]}];

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

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

%Y Column k=0 gives A000007.

%Y Column k=1 gives A370514 or A370507(n,n) for n>=1.

%Y Row sums give A000142.

%Y T(n,n-1) gives A000071(n+1).

%Y Cf. A248687, A370505.

%K nonn,tabl

%O 0,8

%A _Alois P. Heinz_, Feb 20 2024