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

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


How to count number of lists automatically?

• Would you explain more? – DavidC May 7 '14 at 21:59
• There is nothing built-in to count restricted permutations of this type. – ciao May 7 '14 at 23:48
• If all you want is the count, use Multinomial. Multinomial[5,1,1] Out= 42 – Daniel Lichtblau Oct 19 '14 at 18:50

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}
*)

• I think ... Length@DeleteDuplicates[Permute[{g, g, g, g, g, e, r}, AlternatingGroup]] is fine to get it. – santosh May 8 '14 at 14:28
• @santosh Sorry.What do you mean? – Dr. belisarius May 8 '14 at 14:37
• I just want to count the number of permutations. – santosh May 8 '14 at 14:41
• @santosh f1 (your way) and f2 (my function) both count that. But f2 works for a larger set of lists (and larger lists). Also, it's faster in many cases. – Dr. belisarius May 8 '14 at 14:44
• ok thanks...I got it. – santosh May 8 '14 at 14:47

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?

• Hi! I think you missed an important part of the question. The title says "under a permutation group" :) – Dr. belisarius Oct 19 '14 at 11:14
• Ah, I see.. thanks! – Kris Oct 19 '14 at 13:29