Question 1182644: Consider the 720 permutations of the numbers 1, 2, 3, 4, 5, 6. In how many of
these permutations does 1 appear next to 2 or 3 appear next to 4 or 5 appear
next to 6?
Found 3 solutions by greenestamps, ikleyn, Edwin McCravy:
Answer by greenestamps(13198)   (Show Source):
You can put this solution on YOUR website!
Let A be the event that 1 and 2 appear next to each other, B be the event that 3 and 4 appear next to each other, and C be the event that 5 and 6 appear next to each other.
Then use the inclusion-exclusion principle:
# ways (A or B or C)
= ((# of ways A) + (# of ways B) + (# of ways C))
- ((# of ways A and B) + (# of ways A and C) + (# of ways B and C))
+ (# of ways A and B and C)
(1) Number of ways A can happen:
Treat the 1 and 2 as a unit; then there are 5 items to be arranged -- the 1-2 pair and the other 4 digits. The 5 items can be arranged in any of 5!=120 ways; the two items in the 1-2 pair can be arranged in either of 2!=2 ways. The number of ways A can happen is 120*2=240.
Then by the same analysis the number of ways B can happen and the number of ways C can happen are each 240.
(2) Number of ways A and B can both happen:
Treat the 1 and 2 as a unit and the 3 and 4 as a unit. Then we have 4 items to arrange -- the two pairs and the other two digits. The 4 items can be arranged in 4!=24 ways; each of the pairs can be arranged in either of 2!=2 ways. The number of ways A and B can happen is 24*2*2 = 96.
Then by the same analysis the number of ways A and C can happen is 96, and the number of ways B and C can happen is 96.
(3) Number of ways A and B and C can all happen:
Now we have three groups of 2 digits each. Those three items can be arranged in 3!=6 ways; the two digits in each pair can be arranged in either or 2!=2 ways. The number of ways A and B and C can all happen is 6*2*2*2=48.
ANSWER: The number of ways 1 and 2 can be together or 3 and 4 can be together or 5 and 6 can be together is
3(240)-3(96)+48 = 720-288+48 = 480
Answer by ikleyn(52778)  (Show Source):
Answer by Edwin McCravy(20054)  (Show Source):
You can put this solution on YOUR website!
Greenestamps' answer of 480 is correct. Ikleyn has a little trouble with
English, as it is not her first language. If '1 appears NEXT to 2', then
and only then, 'numbers 1 and 2 appear next to each other'.
Here is the way I approached it. I went in the "back door".
Let's say each of the numbers have exactly 1 mate.
1,2 are a mated pair, 3,4 a mated pair, and 5,6 a mated pair.
We will now enumerate all ways in which no two mates are together and then
subtract that result from 720.
We can choose the first number 6 ways.
We can then choose the second number 4 ways, as any of its 4 nonmates.
That's 24 ways to pick the first two numbers.
In each of those 24 cases, the remaining four consist of a mated pair and a
non-mated pair.
So there are two cases for picking the third number.
Case 1. We pick the third number as the mate of the first number in only
one way.
Of the three numbers left, two of them are mates and one is a non-mate to
them. So the non-mated one must go between them. There are only 2 ways to
do that, i.e., to place the mated pair on each side of the non-mated one.
That's only 2 ways for case 1.
Case 2. We pick the third number as a non-mate of the first number (and of
course a nonmate to the second number) in 2 ways.
Of the three numbers left, 2 are nonmates to the third number. So we can
choose the fourth number in two ways.
Now the last two remaining numbers are neither mates themselves nor are they
mates to the fourth number, so they are free to be placed 2 ways, in 5th and
6th positions.
That's (2)(2)(2)=8 ways for case 2.
So that's 2+8=10 ways for any of the 24 ways to place the first two numbers.
So the total number of ways no mates are together is (24)(10) or 240 ways.
The means the answer to the problem is 720-240=480 ways.
Edwin
|
|
|
