TransWikia.com

Number of permutations of the letters $a, b, c, d$ such that $b$ does not follow $a$, and $c$ does not follow $b$, and $d$ does not follow $c$

Mathematics Asked on November 24, 2021

QUESTION: Find the number of permutations of the letters $a, b, c, d$ such that $b$ does not follow $a$, and $c$ does not follow $b$, and $d$ does not follow $c$.


MY ANSWER

I know this is a simple problem but I need an explanation as to why my logic is wrong

Firstly, we group $(ab)$ together, so we get $3!$ permutations in which $a$ and $b$ occur together in that order.. Similarly, we do it for $(bc)$ and $(cd)$ to get permutations that are not required..

So we do, $(4!-3!-3!-3!)$.. but obviously, there are repeated cases and we need to take care of that..

Now, thinking about this I came across a solution which stated that $(ab)$ can arrange in $2!$ ways (obviously) so, we just add them up to correct the sum..
Same goes for $(bc)$ and $(cd)$ ..

This means, when we subtracted the cases, we must have subtracted these cases too for which we have to add now..

But when did we do that! To make myself clear, I put forward an example..

Suppose we can arrange $(bc)$ in $2!$ ways so we consider the case –

$$a(cb)d$$

We are adding this up right? But when did we even subtract this case so that we have to add it now? We did permutations of
$$(ab)cd,space a(bc)d,space ab(cd)$$ And however you may permute any of these three, you will never get the configuration $a(cb)d$ because for the first one, there is an $a$ attached before $b$ so $c$ cannot come before $b$, in the second one, we have $(bc)$ and not $(cb)$ and in the third one, there is a $d$ attached after $c$ so we cannot have $b$ after $c$. So why do we even subtract that? What does that mean?

The solution I saw ended in saying that $(ab)$ can arrange in $2!$ ways, so can $(bc)$ and $(cd)$ and that $(bcd)$ can arrange in $1!$ way… Why?!

From where does $(bcd)$ arrange in $1!$ way?

And then, what seemed like the application of inclusion and exclusion principle, the answer looks like-

$$4!-3.3!+3.2!-1=11$$

Can anyone please help me understand the meaning of what is said.. where is my thinking going wrong?

Please don’t answer that this can be done just by brute force.. I know that :’).. what I need to know is just where is my thought process going wrong?

Thank you so much for your kind help and advice :)..

2 Answers

This method is equally lengthy as your but more clearer. Fix $a$ in first position and select the favorable cases. $$begin{align} underline{color{red}{a}},&underline b,underline c ,underline d;checkmark\ &underline b,underline d,underline c;times\ &underline c,underline b,underline d;times\ &underline c,underline d,underline b;checkmark\ &underline d,underline b,underline c;times\ &underline d,underline c,underline b ;checkmarkend{align}$$

Hence, there are three favourable cases. Do it similarly for $b,c$ and $d$, you will get the answer as $11$.

Answered by SarGe on November 24, 2021

It's difficult to sneak through your spirals. I'd argue as follows:

A priori there are $24$ possible words. $6$ of them contain $(ab)$, and $6$ of them contain $(cd)$, whereby $2$ contain both pairs. This excludes $6+6-2=10$ words. There are $6$ words containing $bc$. The three words $$(bc) a d,quad d (bc) a, quad a d (bc)$$ have not occurred before, but in each of these the interchange of $a$ and $d$ would create an $(ab)$ or a $(cd)$. In this way we obtain $3$ more forbidden words, so that there are $11$ admissible words left.

Answered by Christian Blatter on November 24, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP