partition of a multiset

Question

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?

Answer 1

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