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)<p(i+k) for all i in [n-k]; 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, 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,9

Links

Alois P. Heinz, Rows n = 0..150, flattened

Wikipedia, K-sorted sequence

Wikipedia, Permutation

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.

Example

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

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

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.

Sequence in context: A292628 A163465 A360380 * A370507 A263230 A364257

Adjacent sequences: A370502 A370503 A370504 * A370506 A370507 A370508

Keyword

nonn,tabl

Author

Alois P. Heinz, Feb 20 2024

Status

approved