login
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.
3
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,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
T(n, n) = A006231(n) + 1 = A002104(n) - (n-1) (after Franklin T. Adams-Watters in A121726).
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
(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))
CROSSREFS
Cf. A000142 (row sums), A339015 (column sums), A132393, A126074, A092271, A121726, A339033, A006231, A002104.
Sequence in context: A376202 A132792 A136572 * A262679 A326390 A053203
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Nov 19 2020
STATUS
approved