Determining the basis for strings with cyclic and permutation symmetry I'd like to determine a basis set of strings for strings of length m composed of n letters that are compatible with cyclic symmetry of the string and permutation symmetry of the letters.
It's relatively straightforward to do this by hand in individual cases. For example $m=5, n=3$ with the letters labelled $1,2,3$, then the minimal number of strings I believe are
$$ {00000}, {00001},{00011},{00101},{00012},{00112},{00102}, {00121}, {01012}$$
where I can generated all the other strings by cyclically permuting the indices of the strings above, or by permuting the letters {1,2,3} amongst themselves.
Is there are a way of determining the number of basis strings for each $m,n$? Or at least the number of basis strings constructed in this way.
 A: The problem  of counting the basis  strings is an instance  of Power
Group  Enumeration as  defined  by  Harary and  Palmer  in the  text
Graphical Enumeration. We have the  cyclic group acting on the slots
with cycle index
$$Z(C_m) = \frac{1}{m} \sum_{d|m} \varphi(d) a_d^{m/d}.$$
The  group acting  on the  colors is  the symmetric  group $S_n$  with
recurrence by Lovasz for the cycle index $Z(S_n):$
$$Z(S_n) = \frac{1}{n} \sum_{l=1}^n a_l Z(S_{n-l})
\quad\text{where}\quad
Z(S_0) = 1.$$
With these two cycle indices it  suffices to run the PGE algorithm
as      documented      e.g.      at      the      following      MSE
link.
This yields e.g. for four colors and $m$ slots the sequence
$$1, 2, 3, 7, 11, 39, 103, 367, 1235, 4439, 
\\ 15935, 58509, 215251, 799697, \ldots$$
which points  us to  OEIS A056292  where we
find  confirmation of  these data.  Similarly for  six colors  and $m$
slots we obtain
$$1, 2, 3, 7, 12, 43, 126, 539, 2304, 11023, 
\\ 54682, 284071, 1509852, 8195029, \ldots$$
which  points to  OEIS  A056294, again  for
confirmation.
 The algorithm is shown below.

with(numtheory);

pet_cycleind_cyclic :=
proc(n)
option remember;

    1/n*add(phi(d)*a[d]^(n/d), d in divisors(n));
end;


pet_cycleind_symm :=
proc(n)
option remember;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

neckl_pg :=
proc(m, n)
option remember;
local idx_slots, idx_colors, res, term_a, term_b,
    v_a, v_b, inst_a, inst_b, len_a, len_b, p, q;

    if m = 1 or n = 1 then return 1 fi;

    idx_slots := pet_cycleind_cyclic(m);
    idx_colors := pet_cycleind_symm(n);

    res := 0;

    for term_a in idx_slots do
        for term_b in idx_colors do
            p := 1;

            for v_a in indets(term_a) do
                len_a := op(1, v_a);
                inst_a := degree(term_a, v_a);

                q := 0;

                for v_b in indets(term_b) do
                    len_b := op(1, v_b);
                    inst_b := degree(term_b, v_b);

                    if len_a mod len_b = 0 then
                        q := q + len_b*inst_b;
                    fi;
                od;

                p := p*q^inst_a;
            od;

            res := res +
            lcoeff(term_a)*lcoeff(term_b)*p;
        od;
    od;

    res;
end;

A: The problem described here seems to be identical to the problem of finding the number of equivalence classes of base-m necklaces of length n, where necklaces are considered equivalent under both rotations as well as permutations of the symbols.
The solution is given in N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302. 
