Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #27 Jan 19 2022 22:39:43
%S 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,
%T 0,0,0,1015,1659,2366,0,0,0,0,0,2485,10528,11242,16065,0,0,0,0,0,2240,
%U 58149,92064,84762,125665,0,0,0,0,0,0,228221,760725,805530,722250,1112074
%N 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.
%C 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.)
%C 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.
%C 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.
%F T(n, n) = A006231(n) + 1 = A002104(n) - (n-1) (after _Franklin T. Adams-Watters_ in A121726).
%e Triangle starts:
%e 0: [1]
%e 1: [0, 1]
%e 2: [0, 0, 2]
%e 3: [0, 0, 0, 6]
%e 4: [0, 0, 0, 3, 21]
%e 5: [0, 0, 0, 0, 35, 85]
%e 6: [0, 0, 0, 0, 55, 255, 410]
%e 7: [0, 0, 0, 0, 0, 1015, 1659, 2366]
%e 8: [0, 0, 0, 0, 0, 2485, 10528, 11242, 16065]
%e 9: [0, 0, 0, 0, 0, 2240, 58149, 92064, 84762, 125665]
%e ----------------------------------------------------------
%e Sum 1, 1, 2, 9, 111, 6080, 2331767, ...
%e .
%e Examples for the basic two-dimensional classification of permutations (dots indicate zeros):
%e .
%e * Case n = 6:
%e | 1 2 3 4 5 6 | Sum
%e -------------------------------------|----
%e 1 | . . . . . [1] | 1
%e 2 | . . [ 15] [45] [15] | 75
%e 3 | . [ 40] [120] [40] | 200
%e 4 | . [ 90] [ 90] | 180
%e 5 | . [144] | 144
%e 6 | [120] | 120
%e -------------------------------------|----
%e Sum| 120, 274, 225, 85, 15, 1 | 720
%e .
%e Antidiagonals: [40 + 15, 90 + 120 + 45, 120 + 144 + 90 + 40 + 15 + 1]
%e Leads to row 6 (disregarding leading zeros): 55 + 255 + 410 = 720.
%e .
%e * Case n = 7:
%e | 1 2 3 4 5 6 7 | Sum
%e --------------------------------------------|-----
%e 1 | . . . . . . [1] | 1
%e 2 | . . . [105] [105] [21] | 231
%e 3 | . . [490] [420] [ 70] | 980
%e 4 | . [420] [630] [210] | 1260
%e 5 | . [504] [504] | 1008
%e 6 | . [840] | 840
%e 7 | [720] | 720
%e --------------------------------------------|-----
%e Sum| 720, 1764, 1624, 735, 175, 21, 1 | 5040
%e .
%e Antidiagonals: [420+490+105, 504+630+420+105, 720+840+504+210+70+21+1]
%e Leads to row 7 (disregarding leading zeros): 1015 + 1659 + 2366 = 5040
%e .
%e * Column sums of the matrix give the unsigned Stirling cycle numbers, A132393.
%e * Row sums of the matrix give the number of permutations of n elements whose longest cycle have length k, A126074.
%e * The main antidiagonal of the matrix gives the number of n-permutations that are pure cycles of length n - k, A092271.
%e * 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!.
%e * The columns of the triangle are finite in the sense that their entries become ultimately zero. Column sums of the triangle are A339015.
%o (SageMath) # For illustration computes also A132393 and A126074 (remove the #).
%o def A339016Row(n):
%o f = factorial(n); M = matrix(n + 2)
%o for k in (0..n):
%o for p in Partitions(n, max_part=k, inner=[k]):
%o M[k, len(p)] += (f // p.aut())
%o # print("max cyc len", [sum(M[k, j] for j in (0..n+1)) for k in (0..n)])
%o # print("Stirling 1 ", [sum(M[j, k] for j in (0..n+1)) for k in (0..n)])
%o if n == 0: return [1]
%o return [sum(M[j, k-j+1] for j in srange(k, 0, -1)) for k in (0..n)]
%o for n in (0..9): print(A339016Row(n))
%Y Cf. A000142 (row sums), A339015 (column sums), A132393, A126074, A092271, A121726, A339033, A006231, A002104.
%K nonn,tabl
%O 0,6
%A _Peter Luschny_, Nov 19 2020