A349106 Irregular triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} with cycle descent number equal to k.

1, 1, 2, 5, 1, 15, 8, 1, 52, 51, 16, 1, 203, 312, 172, 32, 1, 877, 1926, 1611, 561, 64, 1, 4140, 12224, 14289, 7744, 1794, 128, 1, 21147, 80401, 124410, 95255, 35755, 5655, 256, 1, 115975, 549776, 1083148, 1103280, 597908, 160576, 17624, 512, 1, 678570, 3911865, 9528751, 12386837, 9044652, 3604756, 705915, 54429, 1024, 1

Offset

0,3

Comments

The cycle descent number of a permutation is computed by writing each cycle with its smallest element first, and then counting up the number of pairs (x,y) where x is the element before y in its cycle and x > y.

Conjecture: T(n,n-3) = 2^(n-1) for n >= 4.

Conjecture: T(n,0) = A000110(n).

Links

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

FindStat, St000317: The cycle descent number of a permutation.

Formula

Conjecture: T(n,k) = [z^k] Sum_{i=0..n} Stirling2(n,i)*(1 - z)^(n - i) Product_{j=0..i-1} (j*z + 1). - Mikhail Kurkov, Jun 13 2023

From Alois P. Heinz, Jun 13 2023: (Start)

Sum_{k=0..max(0,n-2)} k * T(n,k) = A321853(n-1) for n>=2.

Sum_{k=0..max(0,n-2)} (-1)^k * T(n,k) = A011782(n). (End)

Example

Table begins:
n\k |     0      1       2      3      4     5    6  7
----+---------------------------------------------------
  0 |     1;
  1 |     1;
  2 |     2;
  3 |     5,     1;
  4 |    15,     8,      1;
  5 |    52,    51,     16,     1;
  6 |   203,   312,    172,    32,     1;
  7 |   877,  1926,   1611,   561,    64,    1;
  8 |  4140, 12224,  14289,  7744,  1794,  128,   1;
  9 | 21147, 80401, 124410, 95255, 35755, 5655, 256, 1;
      ...
For example, the permutation (1)(2735)(4986) has a cycle descent number of 3 because 7 > 3, 9 > 8, and 8 > 6.
The T(9,7) = 1 permutation in S_9 with cycle descent number 7 is (198765432).

Crossrefs

Column k=0 gives A000110.

Row sums give A000142.

Cf. A011782, A321853.

Sequence in context: A260670 A260665 A110220 * A119518 A216962 A186756

Adjacent sequences: A349103 A349104 A349105 * A349107 A349108 A349109

Keyword

nonn,tabf

Author

Peter Kagey, Dec 30 2021

Extensions

T(0,0)=1 prepended by Alois P. Heinz, Jun 13 2023

Status

approved