Question

Suppose there are m Martians & n Earthlings at a peace conference. To ensure the Martians stay peaceful at the conference, we must make sure that no two Martians sit together, such that between any two Martians there is at least one Earthling?(see detail)

a) Suppose all m+n Martians & Earthlings are seated in a line. How many ways can the Earthlings & Martians be seated in a line?
b) Suppose that the m+n Martians & Earthlings are seated around a circular round-table. How many ways can the Martians & Earthlings be seated around the round-table?

Answer 1

a) `(n!(n+1)!)/((n-m+1)!)`

b) `(n!(n-1)!)/((n-m)!)`

Explanation:

In addition to some extra reasoning, we will use three common techniques for counting.

First, we will make use of the fact that if there are `n` ways to do one thing and `m` ways to do another, then assuming the tasks are independent (what you can do for one doesn't rely on what you did in the other), there are `nm` ways to do both. For example, if I have five shirts and three pairs of pants, then there are `3*5=15` outfits I can make.

Second, we will use that the number of ways of ordering `k` objects is `k!`. This is because there are `k` ways of choosing the first object, and then `k-1` ways of choosing the second, and so on and so forth. Thus the total number of ways is `k(k-1)(k-2)...(2)(1)=k!`

Finally, we will use that the number of ways of choosing `k` objects from a set of `n` objects is `((n),(k)) = (n!)/(k!(n-k)!)` (pronounced as n choose k). An outline of how to arrive at this formula is given here.

---

a) If we disregard the splits initially, there are `m!` ways to order the Martians and `n!` ways to order the Earthlings. Finally, we need to see where the Martians are placed. As each Martian needs to be placed either on an end or between two Earthlings, there are `n+1` locations that they can sit (one to the left of every Earthling, and then one more at the far right). As there are `m` Martians, that means that there are `((n+1),(m)) = ((n+1)!)/(m!(n+1-m)!)` possible ways to place them. Thus the total possible seating arrangements is

`n!m!((n+1)!)/(m!(n+1-m)!) = (n!(n+1)!)/((n-m+1)!)`

b) This problem is similar to the above. To make things simpler, let's pick an Earthling and call him the president. Because it does not matter how a circle is rotated, instead of referring to seating arrangements based on an absolute ordering, we will consider seating arrangements based on their relation to the president.

Just as above, if we start from the president and continue clockwise around the circle, we can count the number of ways of ordering the remaining attendees. As there are `m` Martians and `n-1` remaining Earthlings, there are `m!` ways to order the Martians and `(n-1)!` ways to order the remaining Earthlings.

Next, we once again need to position the Martians. This time we don't have an additional spot at the end, thus there are only `n` locations they can sit. Then there are `((n),(m))=(n!)/(m!(n-m)!)` ways to place them. Thus the total possible seating arrangements is

`(n-1)!m!(n!)/(m!(n-m)!)=(n!(n-1)!)/((n-m)!)`