Question 1002588: please help to solve this question
in how many ways can 8 pupils sit in a row if two must not sit near each other
Answer by Theo(13342)   (Show Source):
You can put this solution on YOUR website! the formula that i came up with is:
the number of ways to arrange where any 2 can't be together is:
n! - (n-1!) * 2
this is derived by figuring out the ways that have to be together and then subtracting that from the number of ways they can be arranged without restriction.
when they have to be together, they can be modelled as one unit.
when they are modelled as one unit, you get (n-1)! rather than n!, because there is one less member to consider since 2 of them are being treated as 1.
each unit pair, however, can be modelled in 2 ways, so you need to multiply that by 2.
you would get the number of ways any 2 have to be together would be (n-1)! * 2.
the number of ways that can't be together would then be n! - (n-1)! * 2.
that's the formula i came up with.
i modelled it with 3 members and with 4 members and it appears to be accurate.
i did not model it with 5 members bcause the possible number of combinations became too high to do manually.
i satisfied myself with the 3 member and 4 member models and figured the formula was probably good for more.
here's my work.
start with 3.
number of arrangements is 3! without any restrictions.
3! = 6
arrangements without any restrictions are:
abc
acb
bac
bca
cab
cba
if 2 must be together then they act as 1 unit.
you would then get 2! = 2
since each unit has two possible arrangements, then multiply that by 2 to get 4.
you have 4 possible arrangements out of 6 where they have to be together.
6 - 4 = 2 possible arrangements where they can't be together.
marking the arrangements where a and b have to be together, you get:
abc ***
acb
bac ***
bca
cab ***
cba ***
there are 4 where they are together.
what's left is 2 where they are not together.
the formula is 3! - 2*2! = 6 - 4 = 2
it works with 3 members.
now we'll do the same thing with 4 members.
number of arrangements without restrictions is 4! = 24
those arrangements are:
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba
we'll mark the arrangements where a and b have to be together.
if the formula is correct, the number should be 3! * 2 = 6 * 2 = 12.
abcd ***
abdc ***
acbd
acdb
adbc
adcb
bacd ***
badc ***
bcad
bcda
bdac
bdca
cabd ***
cadb
cbad ***
cbda
cdab ***
cdba ***
dabc ***
dacb
dbac ***
dbca
dcab ***
dcba ***
the number where they have to be together is 12.
24 - 12 = 12
the number of ways where they must not be together is also 12.
the formula works with 3 and 4 members.
it more then likely will work with 5 or more.
i'll gamble and assume that it does.
the formula for numbr of arrangements where 2 members can't be together is:
n! - (n-1)! * 2
with 3 members, that becomes 3! - 2! * 2 = 6 - 2*2 = 6 - 4 = 2.
this was confirmed to be correct.
with 4 members, that becomes 4! - 3! * 2 = 24 - 6*2 = 24 - 12 = 12.
this was confirmed to be correct.
with 8 members, that becomes 8! - 7! * 2 = 40320 - 5040*2 = 40320 - 10080 = 30240.
this is assumed to be correct.
there's no way of knowing for sure unless you can model it.
you assumed it's good on faith that the formula applies to any number of members and not to just 3 and 4.
while it could be modelled manually, doing so would take way too long and the chance of error would be way too high.
some sort of software would have to be developed to do it mechanically.
i'll go with my gamble.
hopefully the answer will be what you expect.
|
|
|
