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
Examples
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).
Links
- Alois P. Heinz, Rows n = 0..150, flattened
- FindStat, St000317: The cycle descent number of a permutation.
- 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
Extensions
T(0,0)=1 prepended by Alois P. Heinz, Jun 13 2023
Comments