4
$\begingroup$

Seated around the table are: - 2 Americans - 2 Canadians - 2 Mexicans - 2 Jamaicans.

Each countryman is distinguishable.

How many ways possible can all 8 people be seated such that AT LEAST TWO men from the same country sit next to each other?

Rotations are considered the same.

I know that I have to use PIE somehow on the two men, but it is slightly more confusing because there are four groups and two men in each group. Any hints?

EDIT 12/1/2014: I checked the original problem statement and it said that "In how many ways can all eight people be seated such that at least two pairs of countrymen are seated together?". I mistakenly put "at least two men" rather than "at least two pairs". I'm terribly sorry for the confusion!

$\endgroup$
2
  • $\begingroup$ By the way, are you asking about 1-4 pairings of countrymen or just 2-4? $\endgroup$
    – Hernandez
    Nov 30 '14 at 9:01
  • 1
    $\begingroup$ @Hernandez 1-4. The question asks that "AT LEAST TWO men from the same country sit next to each other". Two men = 1 pair $\endgroup$ Nov 30 '14 at 17:36
4
$\begingroup$

Case 1: $1$ group of countrymen to sit together. Obviously, there $4$ ways to do choose the group. Groups of countrymen can be unitized, and within each group the men can be arranged in $2$ ways. There are $7$ units in total around the table. Hence, total number of arrangements here is: $$4\cdot2\cdot6!$$ Case 2: $2$ groups of countrymen sit together. There are $\binom{4}{2}$ to choose the group. $6$ units around the table, $2$ of which contain $2$ arrangements: $$\binom{4}{2}\cdot2^2\cdot5!$$ Case 3: $3$ groups of countrymen sit together. $\binom{4}{3}$ to choose the groups, $5$ units altogether, $3$ of which contain $2$ arrangements of countrymen within themselves: $$\binom{4}{3}\cdot2^3\cdot4!$$ Case 4: All $4$ groups are seated together. Only $1$ way to choose the groups, $4$ units altogether, and accounting for the $2$ arrangements within the groups:$$1\cdot2^4\cdot3!$$

We can now apply the inclusion-exclusion principle. In terms of cases:

$$(1) -\{(2) - [(3)-(4)]\}$$

$\endgroup$
11
  • $\begingroup$ Case three is mostly correct. Consider (AA_CC_MM). This is a round table where three countrymen are sitting together, but the Jamaicans are not. So we have to account for the number of cases where all four are sitting together as desired. Then apply Inclusion-Exclusion. $\endgroup$
    – ml0105
    Nov 29 '14 at 5:06
  • $\begingroup$ @ml0105 Thanks for that. Rookie oversight. $\endgroup$
    – Hernandez
    Nov 29 '14 at 5:12
  • $\begingroup$ Not a problem! Looks much better. :-) $\endgroup$
    – ml0105
    Nov 29 '14 at 5:16
  • $\begingroup$ is it 2016????? $\endgroup$ Nov 29 '14 at 5:58
  • 1
    $\begingroup$ My second comment above should have appended: $$|A\cup C\cup M\cup J| = \\ [|A|+|C|+|M|+|J|] - \left(\sum\limits_{cyc} {|A\cap C|}\right) + \left(\sum\limits_{cyc} {|A\cap C\cap M|}\right) - |A\cap C\cap M\cap J|$$ i.stack.imgur.com/COLX5.jpg $\endgroup$
    – Hernandez
    Nov 30 '14 at 8:14
2
$\begingroup$

Since there has been some discussion in the comments about whether the OP meant to ask for the number of seating arrangements in which the countrypersons of at least one country are seated adjacent to each other or the number of seating arrangements in which the the countrypersons of at least two countries are seated adjacent to each other, I thought it worth recording the method for solving the following general problem:

Let there be $2n$ people consisting of two people from each of $n$ countries seated around a circular table. In how many ways may the people be seated so that, for at least $k$ of the countries, the two representatives of a country are seated next to each other?

We use a general form of the inclusion-exclusion principle. Let there be $n$ sets, $T_1,$ $T_2,\ \ldots,$ $T_n.$ Define $T_{ij}=T_i\cap T_j,$ $T_{ijk}=T_i\cap T_j\cap T_k,$ and so on. Then the number of elements in at least $k$ of the sets $T_i$ is $$ \sum_{j=k}^n(-1)^{j+k}\binom{j-1}{k-1}\sum_{S\subseteq\{1,\ldots,n\},\ \lvert S\rvert=j}\lvert T_S\rvert.\tag{*} $$ For example, when $k=1,$ the binomial coefficient in this expression reduces to $1,$ and we get the usual principle of inclusion-exclusion $$ \lvert T_1\cup T_2\cup\ldots\cup T_n\rvert=\sum_{j=1}^n(-1)^{j+1}\sum_{S\subseteq\{1,\ldots,n\},\ \lvert S\rvert=j}\lvert T_S\rvert. $$ When $k=2,$ we get $$ \lvert T_{12}\cup T_{13}\cup\ldots\cup T_{n-1,n}\rvert=\sum_{j=2}^n(-1)^{j+2}(j-1)\sum_{S\subseteq\{1,\ldots,n\},\ \lvert S\rvert=j}\lvert T_S\rvert. $$ This more general version of inclusion-exclusion can be proved using the binomial coefficient identity $$ \sum_{j=k}^r(-1)^{j+k}\binom{j-1}{k-1}\binom{r}{j}=\begin{cases}0 & \text{if $r<k$,}\\ 1 & \text{if $r\ge k$,}\end{cases} $$ which holds for $k\ge1,$ $r\ge0.$ The proof runs by considering an element $x$ that is a member of exactly $r$ of the sets $T_1,$ $T_2,\ \ldots,$ $T_n.$ We claim that $x$ gives a net contribution of $1$ to the sum (*) if $r\ge k,$ and a contribution of $0$ if $r<k.$ The latter is clear since $x\notin T_S$ for any $\lvert S\rvert>r$ and therefore $x$ doesn't contribute to any term in the inner sum. The former follows from the binomial coefficient identity since $x$ contributes once to exactly $\binom{r}{j}$ of the terms in the inner sum.

Applying this to the problem at hand, let $T_i$ be the set of seating arrangements in which the representatives of country $i$ sit next to each other. If $S$ is a set of countries, then the number of seating arrangements in which the representatives of each of the countries in $S$ sit next to each other is $$ \lvert T_S\rvert=(2n-1-\lvert S\rvert)!\,2^{\lvert S\rvert}. $$ The generalized principle of inclusion-exclusion then implies that the number of seating arrangements in which at least $k$ of the countries have their representatives seated side-by-side is $$ \sum_{j=k}^n(-1)^{j+k}\binom{j-1}{k-1}\binom{n}{j}(2n-1-j)!\,2^j. $$ Applying this to the case $n=4,$ we get that the number of arrangements for $k=1$ is $$ 4\cdot6!\cdot2-6\cdot5!\cdot2^2+4\cdot4!\cdot2^3-1\cdot3!\cdot2^4=3552. $$ For $k=2,$ it's $$ 1\cdot6\cdot5!\cdot2^2-2\cdot4\cdot4!\cdot2^3+3\cdot1\cdot3!\cdot2^4=1632. $$ For $k=3,$ it's $$ 1\cdot4\cdot4!\cdot2^3-3\cdot1\cdot3!\cdot2^4=480. $$ For $k=4,$ it's $$ 1\cdot1\cdot3!\cdot2^4=96. $$

Proof of binomial coefficient identity (added): Let $$ S(r,k)=\sum_{j=k}^r\binom{r}{j}\binom{j-1}{k-1}(-1)^{j+k} $$ with $r\ge0,$ $k\ge1.$ We immediately see that $S(r,k)=0$ for $k>r.$ Now, using the Pascal's triangle recurrence, $$ S(r,k)-S(r,k+1)=\sum_{j=k}^r\binom{r}{j}\left[\binom{j-1}{k-1}+\binom{j-1}{k}\right](-1)^{j+k}=\sum_{j=k}^r\binom{r}{j}\binom{j}{k}(-1)^{j+k}. $$ Expanding $(x-1+1)^r$ using the binomial theorem, we get $$ \begin{aligned} x^r=(x-1+1)^r=\sum_{j=0}^r\binom{r}{j}(x-1)^j&=\sum_{j=0}^r\sum_{k=0}^j\binom{r}{j}\binom{j}{k}x^k(-1)^{k-j}\\ &=\sum_{k=0}^rx^k\sum_{j=k}^r\binom{r}{j}\binom{j}{k}(-1)^{j+k}. \end{aligned} $$ Comparing the left and right sides of this equation, we see that $$ \sum_{j=k}^r\binom{r}{j}\binom{j}{k}(-1)^{k-j}=\begin{cases}0 & k<r\\1 & k=r.\end{cases} $$ We conclude that $S(r,r)-S(r,r+1)=1$ and that $S(r,k)=S(r,k+1)$ for $k<r.$ Since $S(r,r+1)=0,$ we have $S(r,r)=1,$ and therefore $S(r,k)=1$ for $1\le k\le r.$

$\endgroup$
2
  • $\begingroup$ Hi, I am the original poster. please see my edit on the original problem statement. $\endgroup$ Dec 2 '14 at 20:52
  • $\begingroup$ @MathyPerson: my post includes answers to both your original question (this is the case $k=1$) and the revised question (this is the case $k=2$). Alistair's answer does the same. (In fact he believed from the start that the revised question was the one you meant to ask!) $\endgroup$ Dec 3 '14 at 2:39
2
$\begingroup$

Here is the number of all orderings such that exactly specific number of countries have adjacent sitting arrangements:

  • Case 1: Number of orderings such that exactly two countries have adjacent sitting arrangements (Ignore the unusual case ordering, this is most trickier case.):

Number of ways to select two countries from four is $4 \choose 2$. Once you chose these countries you need to make sure that no other countrymen sit next to each other; therefore you have to make a list:

Let $A$ and $B$ be the countrymen which have countries that have non-adjacent sitting arrangements. Let $C$ be the country that has adjacent sitting arrangements; meaning that $C$ contains two countrymen that sit next to each other. Here is the list of all orderings:

$$ ABABCC\\ ABACBC\\ ABACCB\\ ABCABC\\ ABCACB\\ ABCBAC\\ ACBACB $$

So, there are $7$ cases. In each case; you can change the ordering of same letters (Namely, $A$ and $A$ can change places, so on..), and you can change the ordering of people in each $C$; getting you a total of $2^5$ combinations. But, $ABCABC$ and $ACBACB$ have $2^4$ combinations as opposed to $2^5$ just like Will Orrick's explanation in comments. Therefore, final answer is:

$$ {4 \choose 2}2.2^4+{4 \choose 2}5.2^5=1152 $$

  • Case 2: Number of orderings such that exactly one country have adjacent sitting arrangement:

By the same naming convention above, we get $5$ orderings starting with $CAB$:

$$ CABADBD\\ CABDABD\\ CABDADB\\ CABDBAD\\ CABDBDA $$

If you look for orderings starting with $CAD$, you get $5$ new ones just like above, netting you a total of $10$. From this point, there comes a new $10$ orderings starting with $CB$ and then new $10$ starting with $CD$, giving a total sum of $30$ orderings. Note that this orderings are different because they all start with $C$. We can change the places of $A$s, $B$s and $D$s with each other, as well as change the places of persons in $C$; giving a $2^4$ combinations. Also, there's a $4 \choose 1$ way to choose country $C$. Putting all together:

$$ {4 \choose 1}2^430=1920 $$

  • Case 3: Number of orderings such that exactly three countries have adjacent sitting arrangements:

By the same reasoning above you get only $1$ different ordering which is $ACACC$. Changing letters and people give you $2^43!$ combinations. Lastly, there are $4 \choose 3$ way to choose countries. Putting all this together:

$$ {4 \choose 3}2^43!.1=384 $$

  • Case 4: Number of orderings such that exactly four countries have adjacent sitting arrangements:

There are $4 \choose 4$ way to choose countries and this countries have $3!$ different orderings around table. Every person in every country can change places, netting you a $2^4$ combinations. So:

$$ {4 \choose 4}2^43!.1=96 $$

Finally, total number of orderings such that at least one country have adjacent sitting arrangement, is:

$$ 1920+1152+384+96=3552 $$

Update: Total number of orderings such that at least two countries have adjacent sitting arrangements, is:

$$ 1152+384+96=1632 $$

$\endgroup$
12
  • $\begingroup$ I think you mean to say that the men of at least two countries sit next to each other. I say this because, in counting the number of arrangements of six persons as $5!,$ you have not forced the men of the other two countries to sit apart. Also, aren't there three more cases, not two: at least one pair of countrymen, at least three pairs of countrymen, all four pairs of countrymen, sit together? $\endgroup$ Nov 29 '14 at 12:09
  • $\begingroup$ Regarding the last point in my previous comment, I think I see where the confusion lies. The question asks for the number of ways that "AT LEAST TWO men from the same country sit next to each other." I believe this means two men of one country sit together, not two men of two different countries. $\endgroup$ Nov 29 '14 at 12:13
  • $\begingroup$ @WillOrrick. I only look at one case and also emphasize that to show the right approach to asker. I know there are other cases as i stated in last sentence of my answer. I did this on purpose because once you understand the process, it is an easy exercise to apply it to other cases. Regarding to your second comment: I believe asker trying to mean that "at least two countries". If the intent is your claim, then asker felt no need to emphasize "at least" in question. $\endgroup$
    – Alistair
    Nov 29 '14 at 19:44
  • $\begingroup$ @WillOrrick. Your second comment confuses me, i think you're right when saying "you have not forced the men of the other two countries to sit apart". I immediately saw my mistake when i read the sentence independent of your second comment. However resulting number still seems too big for an at least two case. I will think about more and correct my answer when i found the right approach. $\endgroup$
    – Alistair
    Nov 29 '14 at 20:00
  • $\begingroup$ Yes, I saw that you only presented one case, leaving it to the asker to fill in the others, and I agree that this is a nice approach pedagogically. I do agree that it's strange that the asker chose to put the words "at least two" in all capital letters, but I still think my interpretation of the question is more natural, given the wording. It's probably not so important, since the methods used will be similar in either case. $\endgroup$ Nov 29 '14 at 20:08
0
$\begingroup$

How about this.

Any of the 8 sits down first. Followed by his/her countrymen. And then we don't care how the rest sit down.

(8)(1)(6)(5)(4)(3)(2)(1) = 5760

And since we're talking about a circular table, are we now done?

Alternately you could think, 4 ways to choose the country, 2 ways to arrange them, and again, 6! to arrange the rest.

EDIT: This is incorrect. Brute force (VBA+Excel) method confirms Hernandez's answer is correct. 3552.

$\endgroup$
8
  • $\begingroup$ In answer to your question: I don't think that we are exactly "done", since the problem asks for at LEAST two countrymen, so we also have to consider about the pairing of two pairs of countrymen, then three pairs, and then all four. We already have the first pair of countrymen figured out. I will figure the probability out and then comment again. $\endgroup$ Nov 29 '14 at 3:52
  • $\begingroup$ I think those possibilities would be included in the 6!. Some of those arrangements will included country pairs? I could be wrong. $\endgroup$ Nov 29 '14 at 3:54
  • $\begingroup$ I think the 6! would come from the rest of the countrymen being seated with no restrictions, so we would need additional cases. $\endgroup$ Nov 29 '14 at 3:55
  • $\begingroup$ What I have so far for the two pairs of countrymen is this: we have 4C2 ways to choose the two countries. What makes this a bit more confusing is the fact that when one person is seated, there are two possibilities for his partner countryman to sit. Say that countryman sits to the left of the original first person. Then another person from another country can sit to the right of the original first person, then the partner of that person will sit to the right of the person from the other country. Therefore, it would look like this: M , M , C , C . $\endgroup$ Nov 29 '14 at 4:01
  • $\begingroup$ It was noted in the edit that this answer is too large, but it may be helpful to say where it went wrong. Because the table is circular, the correct assumption has been made that we can assume that seats 1 and 2 are occupied by fellow countrypersons. The problem is in the factor $6!.$ As mentioned in the comments, this factor includes arrangements in which other pairs of fellow countrypersons also sit together. But seatings in which there are exactly two such pairs get counted twice by this method; seatings in which there are three such pairs get counted three times, and ... $\endgroup$ Nov 29 '14 at 11:52
0
$\begingroup$

Let us try to find those arrangements in which no two countrymen sit together.Let A1A2,B1B2,C1C2 and D1D2 represent same countrymen. Since we are talking about circular permutations,let A1 be reference point and let B1,C1 and D1 be seated at poition 3,5 and 7 respectively.

              1 
              A1

      8               2


   7 D1               B1 3


      6               4


              C1
              5

At position 2 we can have C2,D2 only,at 4-A2,D2 at 6-A2,B2 and at 8-B2,C2.If C2 is chosen at 2, other places get fixed since 8 can have B2 only,6-A2 and 4 D2. Thus, we can have only 2 permutaions if we select 2 as C2 and D2. Now,since postions 3,5 and 7 may be selected with any 3 people out of 7 thus we have a total of P(7,3)*2 permutations in which no two sit together. Thus 7!-P(7,3)*2 permutations are those in which two or more countrymen sit together.

$\endgroup$
2
  • 1
    $\begingroup$ Very interesting method. But choosing any 3 out of the 7 people would include the possibility of choosing 2 men of the same country. Suppose we had $(1) A_1, (3)A_2, (5)B_1, (7)B_2$. The even positions could then be occupied by any permutation of $\{C_1,C_2,D_1,D_2\}$. $\endgroup$
    – Hernandez
    Nov 29 '14 at 6:04
  • $\begingroup$ Hi, I am the original poster. please see the edit on the original problem statement. $\endgroup$ Dec 2 '14 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.