Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
@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 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}}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.