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

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

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

Table of n, a(n) for n=0..31.

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.

Sequence in context: A305577 A196630 A079572 * A183956 A221843 A368834

Adjacent sequences: A053388 A053389 A053390 * A053392 A053393 A053394

Keyword

more,nonn

Author

Vladeta Jovovic, Mar 06 2000

Extensions

More terms from David Wasserman, Mar 01 2002

a(18)-a(25) from Andrew Howroyd, Mar 20 2018

a(0)=1 prepended by Alois P. Heinz, Mar 20 2018

a(26)-a(31) from Sean A. Irvine, Dec 21 2021

Status

approved