# partition of a multiset

Let $X=\{\underbrace{a_1,\cdots ,a_1}_{\nu_1},\cdots,\underbrace{a_k,\cdots ,a_k}_{\nu_k}\}$ be a multiset of cardinality $\sum{\nu_i}=n$ where each $a_i$ repeats $\nu_i$ times. We suppose that when $\nu_i=\nu_j$, $a_i$ and $a_j$ are indistinguishable. What is the number of possible partitions of $X$ such that no $a_i$ is put in the same partition as $a_j$, $i\not = j$.

Example 1. $X=\{a,a,b\}$ we have $3$ possible partitions :

$(\{a,a\},\{b\})$ , $(\{a\},\{b\},\{a\})$, $(\{b\},\{a,a\})$

Example 2. $X=\{a,a,b,b\}$ we have $3$ possible partitions : $(\{a,a\},\{b,b\})$, $(\{a\},\{b,b\},\{a\})$, $(\{a\},\{b\},\{a\},\{b\})$

Added: i think the answer is ${1\over r}*{n!\over \nu_1!\cdots\nu_k!}$ where $r$ is the number of equal $\nu_i$. is this correct?

-
In example 1, aren't $(\{a,a\},\{b\})$ the same as $(\{b\},\{a,a\})$? –  Paul Dec 22 '11 at 9:12
NO they are not the same because $a$ and $b$ are distinguishable since they have distinct multiplicity. and i put parentheses so they are put in distinct order. –  palio Dec 22 '11 at 9:16
@Palio: But then why aren't $(\{a\},\{a\},\{b\})$ and $(\{b\},\{a\},\{a\})$ distinct solutions as well? –  Marc van Leeuwen Dec 22 '11 at 12:21
Yes, Marc. Also, in example 2, why aren't $(\{a,a\},\{b,b\})$ and (\{b,b\},\{a,a\})$then? It's so confusing! – Paul Dec 22 '11 at 12:30 yes you are right.. actually there is no$(\{a\},\{a\},\{b\})$because adjascent sets of the same elements have to be in the same set then$(\{a\},\{a\},\{b\})$is just$(\{a,a\},\{b\})$. I will edit the example 2 – palio Dec 22 '11 at 12:33 ## 1 Answer If I understand this correctly, what is wanted is the number of inequivalent permutations of multiset$X$, when two permutations are considered equivalent if replacing each (maximal) run$a_ i a_i \dots a_i$of length$m$in each permutation with$\nu_i^m$produces identical results. So, with$X=\{a,a,b,b,c\}$,$abbca$(written as$(\{a\},\{b,b\},\{c\},\{a\})$above) is equivalent to$baacb$since they both generate$2^1 2^2 1^1 2^1$, but they are not equivalent to$baabc$which generates$2^1 2^2 2^1 1^1$. Since in general this seems very difficult, I’ll just consider here the simplest possible non-trivial scenario in which$X=\{a,a,b,b,c,\dots \}$with$\nu_1=\nu_2=2$and$\nu_i\neq \nu_j$if$i>2$or$j>2$. Let $$P\;=\;\frac{(n-4)!}{\prod_{i=3}^k\nu_i!}$$ be the number of distinct permutations of$X \setminus \{a,a,b,b\}$. There are three cases: 1. Permutations of the form$\dots aa\dots bb \dots$. There are$\binom{n-2}{2}P$of these. 2. Permutations of the form$\dots a\dots a\dots bb \dots$. There are$(n-3)\binom{n-2}{2}P$of these. 3. Permutations of the form$\dots a\dots a\dots b\dots b \dots$. There are$\binom{n}{4}P$of these. This gives us (after some algebraic manipulation) the number of of inequivalent permutations of$X\$ as $$\left(\frac{1}{6}+\frac{2(n-2)}{n(n-1)}\right)\frac{n!}{\prod_{i=1}^k\nu_i!}.$$

For investigating (the number of) equivalent permutations of specific multisets, the following Mathematica functions can be used:

numEquivPerms[s_] :=
Length @ DeleteDuplicates[Split /@ Permutations[s] /. Rule @@@ Tally[s]]

numEquivPerms[{a, a, b, b, c, d, d, d}]
640


and

equivPerms[s_] := Module[{r = Rule @@@ Tally[s]},
DeleteDuplicates[Split /@ Permutations[s], (#1 /. r) == (#2 /. r) &]]

equivPerms[{a,a,b,b,c}] // TableForm[#, TableDepth -> 1] &
{{a,a},{b,b},{c}}
{{a,a},{b},{c},{b}}
{{a,a},{c},{b,b}}
{{a},{b},{a},{b},{c}}
{{a},{b},{a},{c},{b}}
{{a},{b,b},{a},{c}}
{{a},{b,b},{c},{a}}
{{a},{b},{c},{a},{b}}
{{a},{c},{a},{b,b}}
{{a},{c},{b},{a},{b}}
{{a},{c},{b,b},{a}}
{{c},{a,a},{b,b}}
{{c},{a},{b},{a},{b}}
{{c},{a},{b,b},{a}}

-