How many ways can 6 people be seated at a round table if it does not matter who sits next to whom?

In general, the number of ways of arranging n objects around a round table is (n-1)!

An easier way of thinking is that we "fix" the position of a particular person at the table. Then the remaining n -1 persons can be seated in (n-1)! ways. Done!

Thus the number of ways of arranging n persons along a round table so that no person has the same two neighbours is(n-1)!/2

Similarly in forming a necklace or a garland there is no distinction between a clockwise and anti clockwise direction because we can simply turn it over so that clockwise becomes anti clockwise and vice versa. Hence the number of necklaces formed with n beads of different colours = (n-1)!/2

Illustrative Examples

Example

In how many ways can 3 men and 3 women be seated at a round table if

1. no restriction is imposed
2. each woman is to be between two men
3. two particular women must sit together
4. two particular women must not sit together
5. all women must sit together
6. there is exactly one person between two particular women?

Solution

1. Total six persons can be seated at a round table in 5! = 120 ways.
2. Three men can be seated first at the round table in 2! = 2 ways. Then the three women can be seated in 3 gaps in 3! = 6 ways.

   Hence the required number of ways = 2 x 6 = 12

3. Temporarily treating two particular women as one big fat woman, five persons can be seated at a round table in 4! = 24 ways. However these two women can be arranged within themselves in 2! = 2 ways.
   Hence the required number of arrangements = 24 x 2 = 48
4. As out of total 120 arrangements, there are 48 ways in which these two women sit together, the required number of arrangements = 120 -48 = 72
5. Temporarily treating three women as one person, four persons can be arranged at round table in 3! = 6 ways. Further, these 3 women can be arranged among themselves in 3! = 6 ways.
   Hence the required number of arrangements is 6 x 6 = 36
6. Temporarily leave aside two particular women. The remaining 4 persons can be seated in 3! = 6 ways. Now these two particular women may be seated "around" any of 4 persons, and further the two can be arranged within themselves in 2 ways.
   Hence the required number of arrangements is 24 x 2 = 48

Example

1. A cat invites 3 rats and 4 cockroaches for dinner. How many seating arrangements are possible along a round table? Assume that animals of a species all look alike, though they will be deeply offended at this assumption.
2. If m indistinguishable men from Mars and n indistinguishable women from Venus sit around a round table, how many possible seating arrangements are there?

Solution

1. "Fix" the position of the cat. Now remaining 3 rats and 4 cockroaches can be seated in 7!/(3! 4!) = 35 ways.
2. Important. You may think that the formula (m -n -1)!/[m! n!] should work in such cases. Try putting m = 3, n = 3, you get 5!/[3! 3!] = 10/3, which is a fraction! In general, there is no formula for circular permutations where all items are repeated. However, even if a single item is there which is not repeated, we can "fix" its position and then find permutations of all remaining items.

Exercise

1. In how many ways can 7 boys be seated at a round table so that two particular boys are (i) next to each other

   (ii) separated?

2. In how many ways can 4 ladies and 4 gentlemen be seated at a round table so that all ladies sit together?
3. 6 person sit around a table. In how many ways can they sit so that no person has the same neighbors?
4. How many different necklaces can be made with 6 beads (i) of different colors

   (ii) of same color?

5. Find the number of ways in which 5 men and 4 women can be seated round a table so that no two women are together.
6. In how many ways can 7 men and 7 women be seated round a table so that no two women are together?
7. In how many ways may six Hindus and six Muslims sit round a table so that no two Hindus sit together?
8. Three boys and three girls go out for dinner. A shy boy does not want to sit with any girl and a shy girl does not want any boy as a neighbour. How many seating arrangements are possible?
9. A round table conference is to be held between 20 delegates. How many seating arrangements are possible if two particular delegates are (i) always to sit together (ii) never to sit together

   (iii) always separated by exactly one person?

10. Indian cricket team sits down for dinner at a round table. In how many arrangements is Saurav flanked by Sachin and Dravid?
11. (i) How many ways can a necklace be formed from 2 red and 2 blue beads?
    (ii) Two twin brothers are married to two twin sisters. In how many ways can they sit at a round table?
12. How many different garlands can be made from 6 marigolds and 2 roses?

Answers

7 People: Person 1, Person 2, 3,4,5,6, and 7 at a round table 7 Chairs: 1,2,3,4,5,6,7 Let chairs 1 and 2 be next to each other; Person 1 is at chair 1 and Person 2 is at chair 2 The rest of the people on 3,4,5,6,7 - can sit in 5! ways Next, Person 1 and Person 2 change their positions; Person 1 is sitting at 2 and Person 2 is sitting at 1 The rest of the people on 3,4,5,6,7 - can be rearranged in 5! ways Therefore, total number of ways in which Person 1 and Person 2 are next to each other is: 2*5! = 120*2 = 240 You then have to find in how many ways they are not sitting next to each other; subtract 240 from the total number of possible arrangements; In circular permutation, Total number of arrangements of n people = (n-1)! Here the number of people is 7 Arrangement = (7-1)! = 6!= 720

Number of ways Person 1 and Person 2 are not next to each other = 720-240 = 480

We turn first to counting. While this sounds simple, perhaps too simple to study, it is not. When we speak of counting, it is shorthand for determining the size of a set, or more often, the sizes of many sets, all with something in common, but different sizes depending on one or more parameters. For example: how many outcomes are possible when a die is rolled? Two dice? $n$ dice? As stated, this is ambiguous: what do we mean by "outcome''? Suppose we roll two dice, say a red die and a green die. Is "red two, green three'' a different outcome than "red three, green two''? If yes, we are counting the number of possible "physical'' outcomes, namely 36. If no, there are 21. We might even be interested simply in the possible totals, in which case there are 11 outcomes.

Even the quite simple first interpretation relies on some degree of knowledge about counting; we first make two simple facts explicit. In terms of set sizes, suppose we know that set $A$ has size $m$ and set $B$ has size $n$. What is the size of $A$ and $B$ together, that is, the size of $A\cup B$? If we know that $A$ and $B$ have no elements in common, then the size $A\cup B$ is $m+n$; if they do have elements in common, we need more information. A simple but typical problem of this type: if we roll two dice, how many ways are there to get either 7 or 11? Since there are 6 ways to get 7 and two ways to get 11, the answer is $6+2=8$. Though this principle is simple, it is easy to forget the requirement that the two sets be disjoint, and hence to use it when the circumstances are otherwise. This principle is often called the addition principle.

This principle can be generalized: if sets $A_1$ through $A_n$ are pairwise disjoint and have sizes $m_1,\ldots m_n$, then the size of $A_1\cup\cdots\cup A_n=\sum_{i=1}^n m_i$. This can be proved by a simple induction argument.

Why do we know, without listing them all, that there are 36 outcomes when two dice are rolled? We can view the outcomes as two separate outcomes, that is, the outcome of rolling die number one and the outcome of rolling die number two. For each of 6 outcomes for the first die the second die may have any of 6 outcomes, so the total is $6+6+6+6+6+6=36$, or more compactly, $6\cdot6=36$. Note that we are really using the addition principle here: set $A_1$ is all pairs $(1,x)$, set $A_2$ is all pairs $(2,x)$, and so on. This is somewhat more subtle than is first apparent. In this simple example, the outcomes of die number two have nothing to do with the outcomes of die number one. Here's a slightly more complicated example: how many ways are there to roll two dice so that the two dice don't match? That is, we rule out 1-1, 2-2, and so on. Here for each possible value on die number one, there are five possible values for die number two, but they are a different five values for each value on die number one. Still, because all are the same, the result is $5+5+5+5+5+5=30$, or $6\cdot 5=30$. In general, then, if there are $m$ possibilities for one event, and $n$ for a second event, the number of possible outcomes for both events together is $m\cdot n$. This is often called the multiplication principle.

In general, if $n$ events have $m_i$ possible outcomes, for $i=1,\ldots,n$, where each $m_i$ is unaffected by the outcomes of other events, then the number of possible outcomes overall is $\prod_{i=1}^n m_i$. This too can be proved by induction.

Example 1.2.1 How many outcomes are possible when three dice are rolled, if no two of them may be the same? The first two dice together have $6\cdot 5=30$ possible outcomes, from above. For each of these 30 outcomes, there are four possible outcomes for the third die, so the total number of outcomes is $30\cdot 4=6\cdot 5\cdot 4=120$. (Note that we consider the dice to be distinguishable, that is, a roll of 6, 4, 1 is different than 4, 6, 1, because the first and second dice are different in the two rolls, even though the numbers as a set are the same.) $\square$

Example 1.2.2 Suppose blocks numbered 1 through $n$ are in a barrel; we pull out $k$ of them, placing them in a line as we do. How many outcomes are possible? That is, how many different arrangements of $k$ blocks might we see?

This is essentially the same as the previous example: there are $k$ "spots'' to be filled by blocks. Any of the $n$ blocks might appear first in the line; then any of the remaining $n-1$ might appear next, and so on. The number of outcomes is thus $n(n-1)(n-2)\cdots(n-k+1)$, by the multiplication principle. In the previous example, the first "spot'' was die number one, the second spot was die number two, the third spot die number three, and $6\cdot5\cdot4=6(6-1)(6-2)$; notice that $6-2=6-3+1$. $\square$

This is quite a general sort of problem:

Definition 1.2.3 The number of permutations of $n$ things taken $k$ at a time is $$P(n,k)=n(n-1)(n-2)\cdots(n-k+1)={n!\over (n-k)!}.$$ $\square$

A permutation of some objects is a particular linear ordering of the objects; $P(n,k)$ in effect counts two things simultaneously: the number of ways to choose and order $k$ out of $n$ objects. A useful special case is $k=n$, in which we are simply counting the number of ways to order all $n$ objects. This is $n(n-1)\cdots(n-n+1)=n!$. Note that the second form of $P(n,k)$ from the definition gives $${n!\over (n-n)!}={n!\over 0!}.$$ This is correct only if $0!=1$, so we adopt the standard convention that this is true, that is, we define $0!$ to be $1$.

Suppose we want to count only the number of ways to choose $k$ items out of $n$, that is, we don't care about order. In example 1.2.1, we counted the number of rolls of three dice with different numbers showing. The dice were distinguishable, or in a particular order: a first die, a second, and a third. Now we want to count simply how many combinations of numbers there are, with 6, 4, 1 now counting as the same combination as 4, 6, 1.

Example 1.2.4 Suppose we were to list all 120 possibilities in example 1.2.1. The list would contain many outcomes that we now wish to count as a single outcome; 6, 4, 1 and 4, 6, 1 would be on the list, but should not be counted separately. How many times will a single outcome appear on the list? This is a permutation problem: there are $3!$ orders in which 1, 4, 6 can appear, and all 6 of these will be on the list. In fact every outcome will appear on the list 6 times, since every outcome can appear in $3!$ orders. Hence, the list is too big by a factor of 6; the correct count for the new problem is $120/6=20$. $\square$

Following the same reasoning in general, if we have $n$ objects, the number of ways to choose $k$ of them is $P(n,k)/k!$, as each collection of $k$ objects will be counted $k!$ times by $P(n,k)$.

Definition 1.2.5 The number of subsets of size $k$ of a set of size $n$ (also called an $n$-set) is $$C(n,k)={P(n,k)\over k!}={n!\over k!(n-k)!}={n\choose k}.$$ The notation $C(n,k)$ is rarely used; instead we use $n\choose k$, pronounced "$n$ choose $k$''. $\square$

Example 1.2.6 Consider $n=0,1,2,3$. It is easy to list the subsets of a small $n$-set; a typical $n$-set is $\{a_1,a_2,\ldots,a_n\}$. A $0$-set, namely the empty set, has one subset, the empty set; a $1$-set has two subsets, the empty set and $\{a_1\}$; a $2$-subset has four subsets, $\emptyset$, $\{a_1\}$, $\{a_2\}$, $\{a_1,a_2\}$; and a $3$-subset has eight: $\emptyset$, $\{a_1\}$, $\{a_2\}$, $\{a_3\}$, $\{a_1,a_2\}$, $\{a_1,a_3\}$, $\{a_2,a_3\}$, $\{a_1,a_2,a_3\}$. From these lists it is then easy to compute $n\choose k$: $$\displaylines{\cr \matrix{ &\rlap{\lower 3pt\hbox{$\Rule{65pt}{0pt}{0.5pt}$}}\cr &0\cr n&1\cr &2\cr &3\cr }\left\vert \matrix{ 0&\lower 3.5pt\hbox{}\rlap{\smash{\raise 1.5em \hbox{$k$}}}1&2&3\cr 1\cr 1&1\cr 1&2&1\cr 1&3&3&1\cr }\right.\cr}$$ $\square$

You probably recognize these numbers: this is the beginning of Pascal's Triangle. Each entry in Pascal's triangle is generated by adding two entries from the previous row: the one directly above, and the one above and to the left. This suggests that ${n\choose k}={n-1\choose k-1}+{n-1\choose k}$, and indeed this is true. To make this work out neatly, we adopt the convention that ${n\choose k}=0$ when $k< 0$ or $k>n$.

Theorem 1.2.7 $\ds{n\choose k}={n-1\choose k-1}+{n-1\choose k}$.

Proof. A typical $n$-set is $A=\{a_1,\ldots,a_n\}$. We consider two types of subsets: those that contain $a_n$ and those that do not. If a $k$-subset of $A$ does not contain $a_n$, then it is a $k$-subset of $\{a_1,…,a_{n-1}\}$, and there are $n-1\choose k$ of these. If it does contain $a_n$, then it consists of $a_n$ and $k-1$ elements of $\{a_1,…,a_{n-1}\}$; since there are $n-1\choose k-1$ of these, there are $n-1\choose k-1$ subsets of this type. Thus the total number of $k$-subsets of $A$ is ${n-1\choose k-1}+{n-1\choose k}$.

Note that when $k=0$, ${n-1\choose k-1}={n-1\choose -1}=0$, and when $k=n$, ${n-1\choose k}={n-1\choose n}=0$, so that ${n\choose 0}={n-1\choose 0}$ and ${n\choose n}={n-1\choose n-1}$. These values are the boundary ones in Pascal's Triangle. $\qed$

Many counting problems rely on the sort of reasoning we have seen. Here are a few variations on the theme.

Example 1.2.8 Six people are to sit at a round table; how many seating arrangements are there?

It is not clear exactly what we mean to count here. If there is a "special seat'', for example, it may matter who ends up in that seat. If this doesn't matter, we only care about the relative position of each person. Then it may or may not matter whether a certain person is on the left or right of another. So this question can be interpreted in (at least) three ways. Let's answer them all.

First, if the actual chairs occupied by people matter, then this is exactly the same as lining six people up in a row: 6 choices for seat number one, 5 for seat two, and so on, for a total of $6!$. If the chairs don't matter, then $6!$ counts the same arrangement too many times, once for each person who might be in seat one. So the total in this case is $6!/6=5!$. Another approach to this: since the actual seats don't matter, just put one of the six people in a chair. Then we need to arrange the remaining 5 people in a row, which can be done in $5!$ ways. Finally, suppose all we care about is who is next to whom, ignoring right and left. Then the previous answer counts each arrangement twice, once for the counterclockwise order and once for clockwise. So the total is $5!/2=P(5,3)$. $\square$

We have twice seen a general principle at work: if we can overcount the desired set in such a way that every item gets counted the same number of times, we can get the desired count just by dividing by the common overcount factor. This will continue to be a useful idea. A variation on this theme is to overcount and then subtract the amount of overcount.

Example 1.2.9 How many ways are there to line up six people so that a particular pair of people are not adjacent?

Denote the people $A$ and $B$. The total number of orders is $6!$, but this counts those orders with $A$ and $B$ next to each other. How many of these are there? Think of these two people as a unit; how many ways are there to line up the $AB$ unit with the other 4 people? We have 5 items, so the answer is $5!$. Each of these orders corresponds to two different orders in which $A$ and $B$ are adjacent, depending on whether $A$ or $B$ is first. So the $6!$ count is too high by $2\cdot5!$ and the count we seek is $6!-2\cdot 5!=4\cdot5!$. $\square$

Exercises 1.2

Ex 1.2.1 How many positive factors does $2\cdot3^4\cdot7^3\cdot11^2\cdot47^5$ have? How many does $p_1^{e_1}p_2^{e_2}\cdots p_n^{e_n}$ have, where the $p_i$ are distinct primes?

Ex 1.2.2 A poker hand consists of five cards from a standard 52 card deck with four suits and thirteen values in each suit; the order of the cards in a hand is irrelevant. How many hands consist of 2 cards with one value and 3 cards of another value (a full house)? How many consist of 5 cards from the same suit (a flush)?

Ex 1.2.3 Six men and six women are to be seated around a table, with men and women alternating. The chairs don't matter, only who is next to whom, but right and left are different. How many seating arrangements are possible?

Ex 1.2.4 Eight people are to be seated around a table; the chairs don't matter, only who is next to whom, but right and left are different. Two people, X and Y, cannot be seated next to each other. How many seating arrangements are possible?

Ex 1.2.5 In chess, a rook attacks any piece in the same row or column as the rook, provided no other piece is between them. In how many ways can eight indistinguishable rooks be placed on a chess board so that no two attack each other? What about eight indistinguishable rooks on a $10\times 10$ board?

Ex 1.2.6 Suppose that we want to place 8 non-attacking rooks on a chessboard. In how many ways can we do this if the 16 most `northwest' squares must be empty? How about if only the 4 most `northwest' squares must be empty?

Ex 1.2.7 A "legal'' sequence of parentheses is one in which the parentheses can be properly matched, like $()(())$. It's not hard to see that this is possible precisely when the number of left and right parentheses is the same, and every initial segment of the sequence has at least as many left parentheses as right. For example, $())\ldots$ cannot possibly be extended to a legal sequence. Show that the number of legal sequences of length $2n$ is $C_n={2n\choose n}-{2n\choose n+1}$. The numbers $C_n$ are called the Catalan numbers.