Thread: Combinatorics

How many ways are there to put 9 distinguishable objects into 5 distinguishable slots such that two particular objects (from the same 9 distinguishable objects) are placed next to each other among the 5 slots?

Originally Posted by posix_memalign

How many ways are there to put 9 distinguishable objects into 5 distinguishable slots such that two particular objects (from the same 9 distinguishable objects) are placed next to each other among the 5 slots?

I will call the objects a1,a2,...,a9.
Let us say that you want a1 and a2 to be in adjacent slots.
Can you calculate the number C of all possibilities how to divide 7 objects a3,...,a9 into the 5 slots?

Now, if a3,...,a9 are divided, you have to put a1 and a2 into two adjacent slots. So the actual result is
C*N
where N denotes the number of possibilities how to put a1 and a2 into adjacent slots.

I'd like to show you that N=8.
One way to see this: If you place a1 into the first or into the 5th slot, you have only one possibility where to put a2. (This gives you possibilities.)
If you put a1 into one of the remaining slots, you have always two possibilities for a2. (This gives you 3*2=6 possibilities).
So there are altogether 8 of them.

Another way:
If a1 and a2 are supposed to be adjacent, then they are placed in one of these two orders:
a1,a2 or a2,a1
Of course you have only four possibilities where to put the left one.
So you have 2*4=8 possibilities.

Originally Posted by kompik

I will call the objects a1,a2,...,a9.
Let us say that you want a1 and a2 to be in adjacent slots.
Can you calculate the number C of all possibilities how to divide 7 objects a3,...,a9 into the 5 slots?

Now, if a3,...,a9 are divided, you have to put a1 and a2 into two adjacent slots. So the actual result is
C*N
where N denotes the number of possibilities how to put a1 and a2 into adjacent slots.

I'd like to show you that N=8.
One way to see this: If you place a1 into the first or into the 5th slot, you have only one possibility where to put a2. (This gives you possibilities.)
If you put a1 into one of the remaining slots, you have always two possibilities for a2. (This gives you 3*2=6 possibilities).
So there are altogether 8 of them.

Another way:
If a1 and a2 are supposed to be adjacent, then they are placed in one of these two orders:
a1,a2 or a2,a1
Of course you have only four possibilities where to put the left one.
So you have 2*4=8 possibilities.

Thanks, I see why N is 8 and I can calculate the number C of all possibilities how to divide 7 objects $\displaystyle a_3 , ... , a_9$ into 5 slots.
But when I did this I found that the number of slots must be 3 after the two objects that must be immediately adjacent have already been placed into the slots.

If there are a total of 5 slots, two adjacent objects are placed into 2 of the 5 slots, then there would only be 3 slots remaining for the possible permutations of the 7 remaining objects?

Originally Posted by posix_memalign

Thanks, I see why N is 8 and I can calculate the number C of all possibilities how to divide 7 objects $\displaystyle a_3 , ... , a_9$ into 5 slots.
But when I did this I found that the number of slots must be 3 after the two objects that must be immediately adjacent have already been placed into the slots. If there are a total of 5 slots, two adjacent objects are placed into 2 of the 5 slots, then there would only be 3 slots remaining for the possible permutations of the 7 remaining objects?

I found the question so vague that I did not bother with it.
Now you reply confirms my judgment.
You see to read the question as if the two ‘special’ objects must be alone in adjacent cells. That is not implicit in the statement.
I read it as the selected objects are in adjacent cell that can be done in 8 ways.
Then the other seven can be put into anyone of the five cells: $\displaystyle 5^7$ ways.

How do you read it?

Originally Posted by Plato

I found the question so vague that I did not bother with it.
Now you reply confirms my judgment.
You see to read the question as if the two ‘special’ objects must be alone in adjacent cells. That is not implicit in the statement.
I read it as the selected objects are in adjacent cell that can be done in 8 ways.
Then the other seven can be put into anyone of the five cells: $\displaystyle 5^7$ ways.

How do you read it?

Forgive me if there was too much ambiguity in the stated problem, I'll try to revise the problem as follows:

There are a total of 9 objects of which 2 are special.
There are a total of 5 slots, each slot has the capacity of 1 object.

Each object including the two special objects are distinguishable.
Each slot is distinguishable, i.e. numbered.

When the two special objects are placed in two of the slots then there are only three slots left for additional objects; these two special objects must always be part of the selection.

How many permutations are there in total for these objects?

Originally Posted by posix_memalign

There are a total of 9 objects of which 2 are special. There are a total of 5 slots, each slot has the capacity of 1 object. Each object including the two special objects are distinguishable.
Each slot is distinguishable, i.e. numbered.
When the two special objects are placed in two of the slots then there are only three slots left for additional objects; these two special objects must always be part of the selection. How many permutations are there in total for these objects?

That is a completely different question from the OP.
The answer is $\displaystyle 8\cdot \left(^7\mathcal{P}_3\right)=8\cdot\frac{7!}{4!}$.