cp's OEIS Frontend

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.

%I A349106 #51 Mar 12 2025 13:19:28
%S A349106 1,1,2,5,1,15,8,1,52,51,16,1,203,312,172,32,1,877,1926,1611,561,64,1,
%T A349106 4140,12224,14289,7744,1794,128,1,21147,80401,124410,95255,35755,5655,
%U A349106 256,1,115975,549776,1083148,1103280,597908,160576,17624,512,1,678570,3911865,9528751,12386837,9044652,3604756,705915,54429,1024,1
%N 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.
%C A349106 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 A349106 T(n,n-3) = 2^(n-1) for n >= 4.
%C A349106 T(n,0) = A000110(n).
%H A349106 Alois P. Heinz, <a href="/A349106/b349106.txt">Rows n = 0..150, flattened</a>
%H A349106 FindStat, <a href="http://www.findstat.org/StatisticsDatabase/St000317">St000317: The cycle descent number of a permutation.</a>
%H A349106 Notamathematician et al., <a href="https://mathoverflow.net/q/489261">Closed form for A349106</a>, MathOverflow, 2025.
%F A349106 T(n,k) = [z^k] Sum_{i=0..n} Stirling2(n,i)*(1 - z)^(n - i) Product_{j=0..i-1} (j*z + 1). - Conjectured by _Mikhail Kurkov_, Jun 13 2023; proved by _Max Alekseyev_, Mar 12 2025 (see MO link)
%F A349106 From _Alois P. Heinz_, Jun 13 2023: (Start)
%F A349106 Sum_{k=0..max(0,n-2)} k * T(n,k) = A321853(n-1) for n>=2.
%F A349106 Sum_{k=0..max(0,n-2)} (-1)^k * T(n,k) = A011782(n). (End)
%F A349106 G.f. for the n-th row: Sum_{k=0..n} T(n,k) * x^k = B_n(A_0(x),...,A_{n-1}(x)), where B_n is exponential Bell polynomial, A_j(x) are Eulerian polynomials. Correspondingly, the bivariate g.f. is Sum_{n >= k >= 0} T(n,k) * x^k * y^n/n! = (1-x/(1-x)*(exp(y*(1-x))-1))^(-1/x). - _Max Alekseyev_, Mar 12 2025
%e A349106 Table begins:
%e A349106 n\k |     0      1       2      3      4     5    6  7
%e A349106 ----+---------------------------------------------------
%e A349106   0 |     1;
%e A349106   1 |     1;
%e A349106   2 |     2;
%e A349106   3 |     5,     1;
%e A349106   4 |    15,     8,      1;
%e A349106   5 |    52,    51,     16,     1;
%e A349106   6 |   203,   312,    172,    32,     1;
%e A349106   7 |   877,  1926,   1611,   561,    64,    1;
%e A349106   8 |  4140, 12224,  14289,  7744,  1794,  128,   1;
%e A349106   9 | 21147, 80401, 124410, 95255, 35755, 5655, 256, 1;
%e A349106       ...
%e A349106 For example, the permutation (1)(2735)(4986) has a cycle descent number of 3 because 7 > 3, 9 > 8, and 8 > 6.
%e A349106 The T(9,7) = 1 permutation in S_9 with cycle descent number 7 is (198765432).
%Y A349106 Column k=0 gives A000110.
%Y A349106 Row sums give A000142.
%Y A349106 Cf. A011782, A321853.
%K A349106 nonn,tabf
%O A349106 0,3
%A A349106 _Peter Kagey_, Dec 30 2021
%E A349106 T(0,0)=1 prepended by _Alois P. Heinz_, Jun 13 2023