login
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

%I #48 Apr 25 2024 11:03:26

%S 1,1,2,5,1,15,8,1,52,51,16,1,203,312,172,32,1,877,1926,1611,561,64,1,

%T 4140,12224,14289,7744,1794,128,1,21147,80401,124410,95255,35755,5655,

%U 256,1,115975,549776,1083148,1103280,597908,160576,17624,512,1,678570,3911865,9528751,12386837,9044652,3604756,705915,54429,1024,1

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

%C 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.

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

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

%H Alois P. Heinz, <a href="/A349106/b349106.txt">Rows n = 0..150, flattened</a>

%H FindStat, <a href="http://www.findstat.org/StatisticsDatabase/St000317">St000317: The cycle descent number of a permutation.</a>

%F 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

%F From _Alois P. Heinz_, Jun 13 2023: (Start)

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

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

%e Table begins:

%e n\k | 0 1 2 3 4 5 6 7

%e ----+---------------------------------------------------

%e 0 | 1;

%e 1 | 1;

%e 2 | 2;

%e 3 | 5, 1;

%e 4 | 15, 8, 1;

%e 5 | 52, 51, 16, 1;

%e 6 | 203, 312, 172, 32, 1;

%e 7 | 877, 1926, 1611, 561, 64, 1;

%e 8 | 4140, 12224, 14289, 7744, 1794, 128, 1;

%e 9 | 21147, 80401, 124410, 95255, 35755, 5655, 256, 1;

%e ...

%e For example, the permutation (1)(2735)(4986) has a cycle descent number of 3 because 7 > 3, 9 > 8, and 8 > 6.

%e The T(9,7) = 1 permutation in S_9 with cycle descent number 7 is (198765432).

%Y Column k=0 gives A000110.

%Y Row sums give A000142.

%Y Cf. A011782, A321853.

%K nonn,tabf

%O 0,3

%A _Peter Kagey_, Dec 30 2021

%E T(0,0)=1 prepended by _Alois P. Heinz_, Jun 13 2023