A370505 T(n,k) is the difference between the number of k-dist-increasing and (k-1)-dist-increasing permutations of [n], where p is k-dist-increasing if k>=0 and p(i)=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 1, 2, 3, 0, 1, 5, 6, 12, 0, 1, 9, 20, 30, 60, 0, 1, 19, 70, 90, 180, 360, 0, 1, 34, 175, 420, 630, 1260, 2520, 0, 1, 69, 490, 1960, 2520, 5040, 10080, 20160, 0, 1, 125, 1554, 5880, 15120, 22680, 45360, 90720, 181440, 0, 1, 251, 3948, 21000, 88200, 113400, 226800, 453600, 907200, 1814400

Offset: 0

Author

Alois P. Heinz, Feb 20 2024

Keywords

• nonn
• tabl

Examples

			T(0,0) = 1: (only) the empty permutation is 0-dist-increasing.
T(4,2) = 5 = 6 - 1 = |{1234, 1243, 1324, 2134, 2143, 3142}| - |{1234}|.
Permutation 3142 is 2-dist-increasing and 4-dist-increasing but not 3-dist-increasing.
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,   1;
  0, 1,   2,    3;
  0, 1,   5,    6,   12;
  0, 1,   9,   20,   30,    60;
  0, 1,  19,   70,   90,   180,   360;
  0, 1,  34,  175,  420,   630,  1260,  2520;
  0, 1,  69,  490, 1960,  2520,  5040, 10080, 20160;
  0, 1, 125, 1554, 5880, 15120, 22680, 45360, 90720, 181440;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..150, flattened
• Wikipedia, K-sorted sequence
• Wikipedia, Permutation

Crossrefs

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

Row sums give A000142.

Main diagonal gives A001710.

T(2n,n+1) gives A000680 for n>=1.

T(2n,n) gives A370576.

Cf. A248686, A248687, A370506, A370507.

Programs

Maple

b:= proc(n, k) option remember; `if`(k<1,
     `if`(n=k, 1, 0), n!/mul(iquo(n+i, k)!, i=0..k-1))
    end:
T:= (n, k)-> b(n, k)-b(n, k-1):
seq(seq(T(n, k), k=0..n), n=0..10);

Formula

T(n,k) = A248686(n,k) - A248686(n,k-1) for k>=2.

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