-3
$\begingroup$

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?

  • 0
    In example 1, aren't $(\{a,a\},\{b\})$ the same as $(\{b\},\{a,a\})$?2011-12-22
  • 0
    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.2011-12-22
  • 1
    @Palio: But then why aren't $(\{a\},\{a\},\{b\})$ and $(\{b\},\{a\},\{a\})$ distinct solutions as well?2011-12-22
  • 0
    Yes, Marc. Also, in example 2, why aren't $(\{a,a\},\{b,b\})$ and (\{b,b\},\{a,a\})$ then? It's so confusing!2011-12-22
  • 0
    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 22011-12-22
  • 0
    This question seems rather badly worded. I presume that what is required is the number of inequivalent _permutations_ of $X$ when two permutations are considered equivalent if they are identical when each maximal run $a_ia_i\dots a_i$ of length $m$ is replaced with $\nu_i^m$. So, with $X=\{a,a,b,b,c\}$, $abbca$ is equivalent to $baacb$ since they both generate $2^12^21^12^1$, but they are not equivalent to $baabc$ which generates $2^12^22^11^1$.2011-12-22
  • 0
    If you want to avoid the down-votes, I suggest you reword the question more precisely.2011-12-23

1 Answers 1