0

Six alphabets, A,B,C,D,E, and F have to be arranged in six numbered positions(1-6). How many ways can you arrange them so that A is not in position numbered 1 , B a is not in position numbered 2 and C is a is not in position numbered 4.

I am trying to break this problem into boolean algebra. Let X=# of ways A is in position 1 Y=# of ways B is in position 2 Z=# of ways C is in position 4

The question is basically asking in how many ways is ~Xu~Yu~Z which is:

(~X)or(~Y)or(~Z)=~X+~Y+~Z-(~X)n(~Y)-(~X)n(~Y)-(~Y)n(~Z)+(~X)n(~Y)n(~Z) for which I get=3*600-3*288+6. Am I doing this correctly?

Could have I solved this problem by rewording ~Xu~Yu~Z=~(XuYuZ)=Total-(XuYuZ)?

jessica
  • 1,002

1 Answers1

1

It's asking for the size of $\neg(X \cup Y \cup Z)=\neg X \cap \neg Y \cap \neg Z$ by de Morgan's Law. This is $6!-|X \cup Y \cup Z|$. We can use Inclusion-Exclusion to find $|X \cup Y \cup Z|$, namely $$|X \cup Y \cup Z|=|X|+|Y|+|Z|-|X \cap Y|-|X \cap Z|-|Y \cap Z|+|X \cap Y \cap Z|.$$

The number of permutations with A in the 1 position is $5!$. The number of permutations with B in the 2 position is $5!$. The number of permutations with C in the 4 position is $5!$.

Hence $|X|=|Y|=|Z|=5!$.

The number of permutations with A in the 1 position and B in the 2 position is $4!$. The number of permutations with A in the 1 position and C in the 4 position is $4!$. The number of permutations with B in the 2 position is $5!$ and C in the 4 position is $4!$.

Hence $|X \cap Y|=|X \cap Z|=|Y \cap Z|=4!$.

The number of permutations with A in the 1 position, B in the 2 position and C in the 4 position is $3!$.

Hence $|X \cap Y \cap Z|=3!$.

So, using Inclusion-Exclusion, we obtain $$6!-3 \times 5!+3 \times 4!-3!$$ as the number of non-clashing permutations.

Rebecca J. Stones
  • 26,845
  • Thank you very much for you help Rebecca. Hypothetically speaking what if I encounter a boolean problem such that $|\neg X \cap Y|=|\neg X|+|Y|-|\neg X \cup Y|$. Is there another law that could be used to break $|\neg X \cup Y|$ into simpler bite size terms without the "negations" – jessica Sep 12 '13 at 02:06
  • I'm not aware of other methods that work in general. I would think it's unlikely there's something much better without some restrictions on the problem. – Rebecca J. Stones Sep 12 '13 at 02:19