A350158 The distribution of the distance from the first weak subcedance to 1 on permutations.

1, 2, 0, 5, 1, 0, 17, 5, 2, 0, 75, 23, 16, 6, 0, 407, 119, 104, 66, 24, 0, 2619, 719, 688, 558, 336, 120, 0, 19487, 5039, 4976, 4554, 3504, 2040, 720, 0, 164571, 40319, 40192, 38862, 34176, 25320, 14400, 5040, 0, 1555007, 362879, 362624, 358506, 338304, 287880, 207360, 115920, 40320, 0

Offset: 1

Author

David Callan, Dec 17 2021

Keywords

• nonn
• tabl

Comments

Triangular array read by rows. For 0 <= k <= n-1, T(n,k) is the number of permutations of [n] for which the difference between the position of 1 and the position of the first weak subcedance is k. A weak subcedance of a permutation pi is an entry pi(i) such that pi(i) <= i. See link.

Examples

			Triangle T(n,k) begins:
       1;
       2,     0;
       5,     1,     0;
      17,     5,     2,     0;
      75,    23,    16,     6,     0;
     407,   119,   104,    66,    24,     0;
    2619,   719,   688,   558,   336,   120,     0;
   19487,  5039,  4976,  4554,  3504,  2040,   720,    0;
  164571, 40319, 40192, 38862, 34176, 25320, 14400, 5040, 0;
  ...
		

Links

• David Callan, The distribution of the distance from the first weak subcedance to 1 on permutations

Crossrefs

Cf. A129591 is the first column.

Row sums give A000142.

Programs

Mathematica

a[1, 0] = 1;
a[n_, 0] /; n >= 2 := 2 (n - 1)! + Sum[k^(n - k - 1) k!, {k, 1, n - 2}];
a[n_, k_] /; n > k >= 1 := (n - 1)! - k^(n - k - 1) k!;
Flatten[Table[a[n, k], {n, 10}, {k, 0, n - 1}]]

Formula

T(1,0) = 1, T(n,0) = 2*(n-1)! + Sum_{j=1..n-2} j^(n-j-1)*j! for n >= 2, T(n,k) = (n-1)! - k^(n-k-1)*k! for 1 <= k <= n-1.