0
$\begingroup$

Given a list of $n$ elements, such as $[a,b,b,c,c,c,d],$ in how many ways can they be arranged such that $a$ and $d$ are never direct neighbors? For example, $a,d,b,c,c,b,c$ is not allowed.

  • Without the restriction, we know the count is $$\frac{n!}{n_1!n_2!....} $$ where $n_1$ and $n_2$ are the number of repetitions of the first and second elements in the original list. So in the example given earlier we'd have $$\frac{7!}{2!3!} $$
  • How does the above change by including the condition over $a$ and $d$?
$\endgroup$
3
$\begingroup$

We will first arrange $[b,b,c,c,c,]$ without the $a$ and $d$.

There are $\frac{5!}{2!3!}$ ways.

We notice that there are 6 slots where we can put in $a$ and $d$.

So to put in $a$ and $d$ there are $\binom{6}{2}2!$ ways

To find the total number of ways we multiply the two together.

$\endgroup$
  • $\begingroup$ You're welcome! I'm guessing it removes the $2!$ term since only one order of slotting will be allowed. $\endgroup$ – Nicholas Oct 23 '15 at 16:20
2
$\begingroup$

Consider the conditions where $a$ and $d$ are neighbours and subtract those cases from the unrestricted arrangement.

In this case, consider $a$ and $d$ as a pair and they themselves can arrange in $2!$ ways. And number of such permutations are $\frac{6!}{2!3!} \times 2 = 60 \times 2 = 120$

Your answer will be as $\frac{7!}{2!3!}-120 = 420-120 =300$

$\endgroup$
  • $\begingroup$ Yes you are correct. $\endgroup$ – SchrodingersCat Oct 23 '15 at 16:16

Your Answer

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