3
$\begingroup$

I'm trying to count this using the principle if inclusion-exclusion. I've done the following:

  • Counting the number of permutations of $aabbbccdd$.
  1. $9!$
  • Counting the number of permutations of $aabbbccdd$ without repetitions.
  1. $\displaystyle\frac{9!}{2!3!2!2!}$
  • Now I guess I need need to count the number of permutations in which all letters are together which is $4!$.
  1. $\displaystyle\frac{9!}{2!3!2!2!}-4!$
  • Now counting the number of permutations in which $a,c,d$ are adjacent, I guess that this number is $\displaystyle \frac{3\cdot 7!}{3!2!2!}$.
  1. $\displaystyle\frac{9!}{2!3!2!2!}-4!-\frac{3\cdot 7!}{3!2!2!}$
  • Now counting the number of permutations in which we have permutations of 2 $b$'s together and then the number of permutations which have $3$ $b$'s together, I have $3\cdot 2/2!$, then $\displaystyle\frac{3 \cdot 7!}{2!2!2!}+\frac{6!}{2!2!2!}$
  1. $\displaystyle\frac{9!}{2!3!2!2!}-4!-\frac{3\cdot 7!}{3!2!2!}-\frac{3 \cdot 7!}{2!2!2!}-\frac{6!}{2!2!2!}$
  • Now I know that are intersections in there. But I'm unable to think about something to count them, I guess that I should add the number of intersections to the result:
  1. $\displaystyle \frac{9!}{2!3!2!2!}-\left( 4!-\frac{3\cdot 7!}{3!2!2!}-\frac{3 \cdot 7!}{2!2!2!}-\frac{6!}{2!2!2!}+ \cap_n \right)$

Is this correct? If so, how can I count the intersections? I guess that the actual formula would be expressed as:

$$\displaystyle \frac{9!}{2!3!2!2!} \cap (4! \cup \frac{3\cdot 7!}{3!2!2!} \cup \frac{3 \cdot 7!}{2!2!2!} \cup \frac{6!}{2!2!2!})$$

$\endgroup$
  • $\begingroup$ Isn't it possible to count the total number of combinations where we want equal letters to be adjacent and then subtract that from $9!$? $\endgroup$ – Hawk Nov 27 '14 at 7:16
  • $\begingroup$ @jip I guess that's what I'm doing, no? (Sorry, my head is a little messy) $\endgroup$ – Billy Rubina Nov 27 '14 at 7:19
3
$\begingroup$

We begin by writing arbitrary words containing only $a$, $a$, $c$, $c$, $d$, $d$.

There are ${6!\over2!2!2!}=90$ such words .

$6$ of these words contain the forbidden pairs $a^2$, $c^2$, and $d^2$. We then need the three $b$'s to separate these pairs. Makes $6$.

There are ${4!\over2!}=12$ words containing $a^2$, $c^2$, and $d$, $d$ in any order. In $6$ of these the $d$'s are paired as well. It follows that there are $3\cdot(12-6)=18$ words containing exactly two forbidden pairs. For each such word we need two $b$'s to separate the forbidden pairs, and there are $5$ slots left for the third $b$. Makes $18\cdot 5=90$.

There are ${5!\over2!2!}=30$ words containing $a^2$, and $c$, $c$, $d$, $d$ in any order. $2\cdot6$ of these words contain exactly one of $c^2$ and $d^2$, and another $6$ contain both $c^2$ and $d^2$. It follows that there are $3\cdot(30-12-6)=36$ words containing exactly one forbidden pair. We need one $b$ to separate this pair, and there are $6$ slots left for the remaining two $b$'s. Makes $36\cdot{6\choose2}=540$.

There are $90-6-18-36=30$ words containing no forbidden pair. This allows for $7$ slots where the $b$'s can be written in. Makes $30\cdot{7\choose3}=1050$.

Adding up the obtained counts gives a grand total of $$N=1686$$ allowed words from $a$, $a$, $b$, $b$, $b$, $c$, $c$, $d$, $d$.

$\endgroup$
2
$\begingroup$

Use the principle of inclusion and exclusion, iterated for the tripplet and the three pairs.

$$\left(\tfrac{9!}{3!\;2!^3}-\tfrac{8!\;2}{2!^3}+\tfrac{7!}{2!^3}\right) -\tbinom{3}{1}\left(\tfrac{8!}{3!\;2!^2}-\tfrac{7!\;2}{2!^2}+\tfrac{6!}{2!^2}\right) +\tbinom{3}{2}\left(\tfrac{7!}{3!\;2!}-\tfrac{6!\;2}{2!}+\tfrac{5!}{2!}\right) -\left(\tfrac{6!}{3!}-5!\;2+4!\right)$$

  • $\frac{9!}{3!\;2!^3}$ counts all the permutations of the multiset.

  • $-\frac{8!\; 2}{\;2!^2}$ over excludes the permutation where two b are adjacent.

  • $+\frac{7!}{2!^3}$ reincludes permutations where all three b are adjacent

  • $-{3\choose 1}\left(\frac{8!}{3!\;2!^2}-\frac{7!\;2}{2!^2}+\frac{6!}{2!^2}\right)$ excludes (as the above) for where also one pair of a, c, or d are together

  • Then we reinclude where also two pair of those three are together.

  • Finally rexcluding where also all three of those are together/

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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