cp's OEIS Frontend

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.

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