

A053391


Number of cycle types of direct products of two degreen permutations.


0



1, 1, 2, 5, 10, 27, 43, 118, 183, 414, 700, 1554, 2229, 5002, 7591, 14267, 22378, 42866, 62093, 116639, 170909, 297002, 447730, 765973, 1096141, 1861030, 2707679, 4356383, 6351345, 10173716, 14425510, 22886088
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

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


LINKS



EXAMPLE

I will use the notation (i, j, k, ...) for a permutation with i 1cycles, j 2cycles, k 3cycles, etc. and * for direct product. There are 3 cycle types of 3element 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


PROG

(PARI)
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)))}
a(n)={my(M=Map()); forpart(p=n, forpart(q=n, mapput(M, PartProdPoly(p, q), 1) )); #M} \\ Andrew Howroyd, Mar 20 2018


CROSSREFS

A000041 gives the number of cycle types of an nelement permutation.


KEYWORD

more,nonn


AUTHOR



EXTENSIONS



STATUS

approved



