|
| |
|
|
A327791
|
|
Number of ways, up to order, of decomposing (Z/nZ)* as the internal direct product of r cyclic subgroups, where r = rank((Z/nZ)*).
|
|
2
|
|
|
|
1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 4, 4, 1, 1, 1, 4, 6, 1, 1, 28, 1, 1, 1, 6, 1, 4, 1, 4, 6, 1, 8, 6, 1, 1, 8, 48, 1, 6, 1, 6, 8, 1, 1, 48, 1, 1, 4, 8, 1, 1, 8, 84, 6, 1, 1, 48, 1, 1, 36, 4, 24, 6, 1, 4, 6, 8, 1, 84, 1, 1, 8, 6, 12, 8, 1, 192, 1, 1, 1, 84, 16, 1, 8, 84, 1, 8
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,8
|
|
|
COMMENTS
|
In general, let G be a finite abelian group and r = rank(G), let s be the number of arrays (k_1, k_2, ..., k_r) such that G = C_(k_1) X C_(k_2) X ... X C_(k_r). We can see from A302257 that:
(a) Given (k'_1, k'_2, ..., k'_r) such that G = C_(k'_1) X C_(k'_2) X ... X C_(k'_r), the number of arrays (a_1, a_2, ..., a_r) such that G = <a_1> X <a_2> X ... <a_r> and that ord(a_i) = k'_i is |Aut(G)|, where <a> is the subgroup of G generated by a. This is because if one group of such (a_1, a_2, ..., a_r) is found, all the others can be found by group automorphism. As a result, the number of sets {a_1, a_2, ..., a_r} such that G = <a_1> X <a_2> X ... <a_r> is |Aut(G)|*s/r!. As (k'_1, k'_2, ..., k'_r) runs through all the s possible choices, each array (a_1, a_2, ..., a_r) such that G = <a_1> X <a_2> X ... <a_r> occurs exactly once, giving a total of |Aut(G)|*s arrays. But the elements in a set are unordered, so the number of sets is |Aut(G)|*s/r!;
(b) Let M = Product_{i=1..r} phi(k_i), then the number of sets {H_1, H_2, ..., H_r} such that G = H_1 X H_2 X ... X H_r is (|Aut(G)|*s/r!)/M. Given {H_1, H_2, ..., H_r} such that G = H_1 X H_2 X ... X H_r, there are phi(|H_i|) ways to choose a generator of H_i, that is, there are Product_{i=1..r} phi(|H_i|) sets {a_1, a_2, ..., a_r} such that <a_i> = H_i. From (a), the total number of sets {a_1, a_2, ..., a_r} as {H_1, H_2, ..., H_r} runs through all possible choices is |Aut(G)|*s/r!. Note that Product_{i=1..r} phi(|H_i|) is always equal to M regardless of the choice of {H_1, H_2, ..., H_r}. That is to say, each set of cyclic subgroups {H_1, H_2, ..., H_r} corresponds to M sets of generators {a_1, a_2, ..., a_r}. Thus, the number of sets {H_1, H_2, ..., H_r} is (|Aut(G)|*s/r!)/M.
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
n = 8: (Z/8Z)* = {1, 3} X {1, 5} = {1, 3} X {1, 7} = {1, 5} X {1, 7}, so a(8) = 3;
n = 16: (Z/16Z)* = {1, 3, 9, 11} X {1, 7} = {1, 3, 9, 11} X {1, 15} = {1, 5, 9, 13} X {1, 7} = {1, 5, 9, 13} X {1, 15}, so a(16) = 4;
n = 35: (Z/35Z)* = {1, 2, 4, 8, 9, 11, 16, 18, 22, 23, 29, 32} X {1, 6} = {1, 2, 4, 8, 9, 11, 16, 18, 22, 23, 29, 32} X {1, 34} = {1, 3, 4, 9, 11, 12, 13, 16, 17, 27, 29, 33} X {1, 6} = {1, 3, 4, 9, 11, 12, 13, 16, 17, 27, 29, 33} X {1, 34} = {1, 8, 22, 29} X {1, 11, 16, 19, 24, 34} = {1, 8, 22, 29} X {1, 6, 11, 16, 26, 31} = {1, 13, 27, 29} X {1, 11, 16, 19, 24, 34} = {1, 13, 27, 29} X {1, 6, 11, 16, 26, 31}, so a(35) = 8.
|
|
|
PROG
|
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
