|
|
A053391
|
|
Number of cycle types of direct products of two degree-n 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 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
|
|
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 n-element permutation.
|
|
KEYWORD
|
more,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|