A339016 A classification of permutations based on their cycle length and the size of the centralizer of their cycle type. Triangle read by rows, T(n, k) for 0 <= k <= n.

1, 0, 1, 0, 0, 2, 0, 0, 0, 6, 0, 0, 0, 3, 21, 0, 0, 0, 0, 35, 85, 0, 0, 0, 0, 55, 255, 410, 0, 0, 0, 0, 0, 1015, 1659, 2366, 0, 0, 0, 0, 0, 2485, 10528, 11242, 16065, 0, 0, 0, 0, 0, 2240, 58149, 92064, 84762, 125665, 0, 0, 0, 0, 0, 0, 228221, 760725, 805530, 722250, 1112074

Offset: 0

Author

Peter Luschny, Nov 19 2020

Keywords

• nonn
• tabl

Comments

The size of the centralizer of a partition p is aut(p) = Product_{j = 1..k} m(j)!*j^m(j), where m(j) is the multiplicity of j as a part of p. (For instance p = [2, 2, 2] -> aut(p) = 3!*2^3.)

Let M be the matrix with M(k, r) = Sum_{p in P(n, k)} n! / aut(p) where P(n, k) are the partitions of n with largest part k and length(p) = r. Then T(n, k) = Sum_{j=0..k} M(j, k-j+1), which are the antidiagonal sums of the upper triangular part of the matrix M.

In the example section below it is explained how the matrix M leads to a two-dimensional classification of the permutations of [n] which project to the unsigned Stirling cycle numbers and the number of permutations with longest cycle length.

Examples

			Triangle starts:
0:  [1]
1:  [0, 1]
2:  [0, 0, 2]
3:  [0, 0, 0, 6]
4:  [0, 0, 0, 3,  21]
5:  [0, 0, 0, 0,  35,   85]
6:  [0, 0, 0, 0,  55,  255,     410]
7:  [0, 0, 0, 0,   0, 1015,    1659,  2366]
8:  [0, 0, 0, 0,   0, 2485,   10528, 11242, 16065]
9:  [0, 0, 0, 0,   0, 2240,   58149, 92064, 84762, 125665]
----------------------------------------------------------
Sum  1, 1, 2, 9, 111, 6080, 2331767, ...
.
Examples for the basic two-dimensional classification of permutations (dots indicate zeros):
.
* Case n = 6:
   |   1     2     3    4    5    6  | Sum
-------------------------------------|----
1  |   .     .     .    .    .   [1] |   1
2  |   .     .   [ 15] [45] [15]     |  75
3  |   .   [ 40] [120] [40]          | 200
4  |   .   [ 90] [ 90]               | 180
5  |   .   [144]                     | 144
6  | [120]                           | 120
-------------------------------------|----
Sum| 120,  274,   225,  85,  15,  1  | 720
.
Antidiagonals: [40 + 15, 90 + 120 + 45, 120 + 144 + 90 + 40 + 15 + 1]
Leads to row 6 (disregarding leading zeros): 55 + 255 + 410 = 720.
.
* Case n = 7:
   |  1      2     3     4     5    6    7  | Sum
--------------------------------------------|-----
1  |  .      .     .     .     .    .   [1] |    1
2  |  .      .     .   [105] [105] [21]     |  231
3  |  .      .   [490] [420] [ 70]          |  980
4  |  .    [420] [630] [210]                | 1260
5  |  .    [504] [504]                      | 1008
6  |  .    [840]                            |  840
7  | [720]                                  |  720
--------------------------------------------|-----
Sum| 720,  1764,  1624, 735,  175,  21,  1  | 5040
.
Antidiagonals: [420+490+105, 504+630+420+105, 720+840+504+210+70+21+1]
Leads to row 7 (disregarding leading zeros): 1015 + 1659 + 2366 = 5040
.
* Column sums of the matrix give the unsigned Stirling cycle numbers, A132393.
* Row sums of the matrix give the number of permutations of n elements whose longest cycle have length k, A126074.
* The main antidiagonal of the matrix gives the number of n-permutations that are pure cycles of length n - k, A092271.
* The entries of the matrix sum to n!. In particular the sum over all row sums, the sum over all column sums, and the sum over all antidiagonal sums is n!.
* The columns of the triangle are finite in the sense that their entries become ultimately zero. Column sums of the triangle are A339015.
		

Crossrefs

Cf. A000142 (row sums), A339015 (column sums), A132393, A126074, A092271, A121726, A339033, A006231, A002104.

Programs

SageMath

# For illustration computes also A132393 and A126074 (remove the #).
def A339016Row(n):
    f = factorial(n); M = matrix(n + 2)
    for k in (0..n):
        for p in Partitions(n, max_part=k, inner=[k]):
            M[k, len(p)] += (f // p.aut())
    # print("max cyc len", [sum(M[k, j] for j in (0..n+1)) for k in (0..n)])
    # print("Stirling 1 ", [sum(M[j, k] for j in (0..n+1)) for k in (0..n)])
    if n == 0: return [1]
    return [sum(M[j, k-j+1] for j in srange(k, 0, -1)) for k in (0..n)]
for n in (0..9): print(A339016Row(n))

Formula

T(n, n) = A006231(n) + 1 = A002104(n) - (n-1) (after Franklin T. Adams-Watters in A121726).