Counting the permuted forms of a list with repeated members under a permutation group

Question

DeleteDuplicates[Permute[{g, g, g, g, g, e, r}, AlternatingGroup[7]]]

How to count number of lists automatically?

Answer 1

Let's define your function and my proposal:

f1[l_, gr_] := Length@DeleteDuplicates@Permute[l, gr@Length@l]
f2[l_, gr_] := GroupOrder@gr@Length@l /
               GroupOrder@GroupSetwiseStabilizer[gr@Length@l, {l}, Permute]

f2 isn't always faster than f1,but can calculate things where f1 fails due to memory constraints. For example:

Timing@f1[{a, a, a, a, a, a, a, a, b, b, c, c}, AlternatingGroup]

Permute::nomem: The current computation was aborted because there was insufficient memory available to complete the computation.

While:

Timing@f2[{a, a, a, a, a, a, a, a, b, b, c, c}, AlternatingGroup]
(*
 {2.265625, 2970}
*)

Answer 2

If it's the number of permutations you want, wouldn't it be easier to just use factorials? Please let me know if I'm missing something, but I think you could compute it as follows:

Suppose you have a list $\ell$ of $m$ entries containing $k\leq m$ distinct elements and let $n_k$ be the number of occurrences of the $k$-th element. For instance, suppose our list is $$ \ell\ =\ (a_1, a_2, a_2, a_3, a_3, a_3, a_3, a_3) $$ In this case, $m=8$, $k=3$, $n_1=1$, $n_2=2$, $n_3=5$.

The number of permutations is computed from $m$ and the $n_i$'s as: $$ \#\text{perms}\ =\ \frac{m!}{n_1!\ \cdots\ n_k!} $$ This is implemented in Mathematica by the Multinomial function. For instance, the above example is written as:

perms[list_]:= Multinomial @@ Tally[list][[All,2]]

Correct me if I'm wrong, but doesn't this improve performance immensely?