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

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


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[18]= 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[7]]] 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