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)<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, 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,8

Links

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

Wikipedia, K-sorted sequence

Wikipedia, Permutation

Formula

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

Example

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

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

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.

Sequence in context: A357079 A259790 A246654 * A184182 A085771 A253286

Adjacent sequences: A370503 A370504 A370505 * A370507 A370508 A370509

Keyword

nonn,tabl

Author

Alois P. Heinz, Feb 20 2024

Status

approved