OFFSET
0,6
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.
FORMULA
EXAMPLE
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.
PROG
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))
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Nov 19 2020
STATUS
approved