login
Number of cycle types of direct products of two degree-n permutations.
0

%I #24 Dec 21 2021 03:36:02

%S 1,1,2,5,10,27,43,118,183,414,700,1554,2229,5002,7591,14267,22378,

%T 42866,62093,116639,170909,297002,447730,765973,1096141,1861030,

%U 2707679,4356383,6351345,10173716,14425510,22886088

%N Number of cycle types of direct products of two degree-n permutations.

%C If f is a permutation of A and g is a permutation of B, the direct product of f and g is the permutation of AXB that maps (a, b) to (f(a), g(b)). The cycle type of the direct product is determined by the cycle types of f and g. - _David Wasserman_, Mar 01 2002

%e I will use the notation (i, j, k, ...) for a permutation with i 1-cycles, j 2-cycles, k 3-cycles, etc. and * for direct product. There are 3 cycle types of 3-element permutations: (3), (1, 1) and (0, 0, 1). (3)*(3) has cycle type (9); (3)*(1, 1) has cycle type (3, 3); (3)*(0, 0, 1) has cycle type (0, 0, 3); (1, 1)*(1, 1) has cycle type (4, 1); (1, 1)*(0, 0, 1) has cycle type (0, 0, 1, 0, 0, 1); (0, 0, 1)*(0, 0, 1) has cycle type (0, 0, 3). Since there are 5 distinct answers, a(3) = 5. - _David Wasserman_, Mar 01 2002

%o (PARI)

%o PartProdPoly(p,q)={sum(i=1,#p, sum(j=1, #q, my(g=gcd(p[i], q[j])); g*'x^(p[i]*q[j]/g)))}

%o a(n)={my(M=Map()); forpart(p=n, forpart(q=n, mapput(M,PartProdPoly(p,q),1) )); #M} \\ _Andrew Howroyd_, Mar 20 2018

%Y A000041 gives the number of cycle types of an n-element permutation.

%K more,nonn

%O 0,3

%A _Vladeta Jovovic_, Mar 06 2000

%E More terms from _David Wasserman_, Mar 01 2002

%E a(18)-a(25) from _Andrew Howroyd_, Mar 20 2018

%E a(0)=1 prepended by _Alois P. Heinz_, Mar 20 2018

%E a(26)-a(31) from _Sean A. Irvine_, Dec 21 2021