返回题库

四人晚餐

Dinner For Four

专题
Discrete Math / 离散数学
难度
L4

题目详情

如果每个人都有相同的左邻和右邻，那么有多少种方式可以让十个人中的四个人围坐在圆桌旁，其中两个座位被认为是相同的？

How many ways are there to seat four of a group of ten people around a circular table where two seatings are considered the same when everyone has the same immediate left and immediate right neighbor?

解析

分两步：先选人，再圆桌排座。

1）从 10 人中选出 4 人：(104)\binom{10}{4}。

2）将这 4 人围坐圆桌，若每个人的左右邻居相同则视为同一种座位。圆桌的旋转会产生等价情况，因此固定其中任意 1 人作为参照点后，其余 3 人按顺时针排列共有 3!3! 种。

因此总方式数为

(104)⋅3!.\boxed{\binom{10}{4}\cdot 3!}.

Original Explanation

This question requires we first count the number of distinct ways to select 4 people from our original group of 10, and then, count the number of ways to order these 4 people around our circular dinner table.

The first expression, the number of ways to choose 4 people from 10, is simple (104)10 \choose 4.

Computing the second expression, however, requires a little more effort. We must first carefully consider the constraints of the problem. It helps us understand what distinct orderings look like. For example, using a traditional clock to help understand positioning, the following two seatings are the same for people A, B, C, and D:

  1. 12: A, 3: B, 6: 6, 9: D

  2. 12: D, 3: A, 6: B, 9: C

Take a second to illustrate these two orderings. They are the same because the left and right neighbors of each individual is the same in both seatings. As a result, we cannot simply permute the number of people (4!) to get the value of orderings as we would be overcounting such as in the above two identical cases.

We can solve this subproblem with two methods.

  1. We can first fix any of the four people, let's say person A, then permute the remaining 3 people. Since we've assigned or fixed a single person, we are removing the potential for duplicates. As a result, for 4 people, there are 3! total orderings.

  2. We could also use the approach of counting total orderings, them removing duplicates. The total orderings would be 4! because for the first person there are 4 total seats, the second person 3, the third person 2, and the last person 1. However, with this method of counting we are also including the above scenario of identical counting. A single ordering is counted 4 times, by the fact that we could rotate the ordering to each of the 4 spots. As a result, to get the number of orderings without duplicates, we could divide out the duplicates as such: 4!4=3!\frac{4!}{4}=3!

Putting together the solutions to the two subproblems, we get the final expression: (104)∗3!\boxed{{10\choose4} * 3!}