VOOZH about

URL: https://oeis.org/A349106

⇱ A349106 - OEIS

login
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, 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.
T(n,n-3) = 2^(n-1) for n >= 4.
T(n,0) = A000110(n).
LINKS
Notamathematician et al., Closed form for A349106, MathOverflow, 2025.
FORMULA
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)
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)
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
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.
Sequence in context: A260670 A260665 A110220 * A119518 A216962 A186756
KEYWORD
nonn,tabf
AUTHOR
Peter Kagey, Dec 30 2021
EXTENSIONS
T(0,0)=1 prepended by Alois P. Heinz, Jun 13 2023
STATUS
approved