Question

This is a permutations problem in which certain pairs of elements are not allowed---like two kids who will not stand next to each other in line.

Say we have 5 symbols a b c d e. There are 5! = 120 possible orders.

Now we say that any orders with a next to b are not allowed. The way I'd calculate this is to enumerate the non-allowed orders like this:

a b - - -
- a b - -
- - a b -
- - - a b

plus four more in which b comes before a. So, there are 8 of these types of order that are not allowed, each one having 6 possibilities for the remaining slots. Total is 8 x 3 x 2 = 48, lea

Answer 1

Is this logic correct?
Does anyone know a reference to the theory. For example, suppose there were two or more excluded pairs or triplets (with more symbols overall).

Thanks.

Answer 2

truncated , leaving 72 allowed orders.

Answer 3

its same as

5! - 4!2!

Answer 4

if you have two pairs that should be isolated, for example :
a,b shouldnt be together
c,d shouldnt be together

Answer 5

it becomes

5! - 3!2!2!

Answer 6

Thanks. Something like:
n! - (n-p!) 2! 2!
where p is the number of pairs?
Where to learn more about this? I've never seen it.

Answer 7

i dont know... this logic is blessed to me by my friend... not sure whether its available online..

i can explain how it works... if you'd like

Answer 8

typo
n! - (n-p)! 2! 2!

Answer 9

I'll work on it and get back if needed, thanks again.

Answer 10

okay.. but im slightly skeptical about the second expression :
5! - 3!2!2!

it removes permutations in which (both ab together & cd together)

Answer 11

we should remove two terms more :
1) ab alone together
2) cd alone together

Answer 12

I'll leave this open for a bit, maybe someone else has something to say.

Answer 13

@amistre64 can you add anything? Thanks.

Answer 14

abcde
abced
abdce
abdec
abecd
abedc looks to be the setup for any one ab--- variety to me, and make
that 12 for the ba--- setup

as you noted, there are 4 setups that would have to be accounted for makeing 48 bad

the remaining 120-48 would seem good to me them

Answer 15

how to get that into n! notation ... dunno :)

Answer 16

5! - 4(2*3!)

Answer 17

Thanks. I'm going to try some simulations before I close this.

Answer 18

good luck

Answer 19

Simulation confirms the basic formula:
C = n! - 2*(n-1)(n-2)!
but not the other one.
Thanks again.