返回题库

13 把椅子

13 chairs in a row

专题
General / 综合
难度
L4

题目详情

一排有 13 把椅子，13 个人编号为 1 到 13。每个人依次进入房间。

除第 1 个人随机选座位外，其余每个人都必须坐在某个已就座的人旁边（相邻椅子）。

问：一共有多少种可能的最终入座组合（座位安排）？

英文原题

There are 13 chairs in a row and 13 people ordered 1 to 13. Each person enters the room one at a time and must sit next to someone else apart from the first person who chooses his seat randomly. How many possible combinations are there?

解析

第 1 人坐下后，已占椅子集合是一个长度为 1 的连续区间。

由于之后每个人都必须坐在“已坐的人旁边”，可选的空位只能是当前已占区间的左边界外侧或右边界外侧，因此已占集合始终是一个连续区间，并且每来一人区间长度加 1。

设第 1 人选的椅子位置为 s∈{1,…,13}s\in\{1,\ldots,13\}。那么后续 12 次入座中：

  • 需要向左扩展 s−1s-1 次才能覆盖到椅子 1；
  • 需要向右扩展 13−s13-s 次才能覆盖到椅子 13。

任意一种把这两类扩展交错排列的顺序都会产生一种不同的最终座位分配，数量为

(12s−1).\binom{12}{s-1}.

对所有 ss 求和：

∑s=113(12s−1)=212=4096.\sum_{s=1}^{13}\binom{12}{s-1}=2^{12}=\boxed{4096}.

英文解析

After the first person sits, the set of occupied chairs is a contiguous interval of length 1.

Since each subsequent person must sit next to someone already seated, the only available empty seats are immediately to the left or right of the current occupied interval. Therefore, the set of occupied chairs remains a contiguous interval, and its length increases by 1 with each new arrival.

Let the position chosen by the first person be s∈{1,…,13}s \in \{1, \ldots, 13\}. In the subsequent 12 seating events:

  • It requires s−1s-1 leftward expansions to cover chair 1;
  • It requires 13−s13-s rightward expansions to cover chair 13.

Any interleaving order of these two types of expansions results in a distinct final seating arrangement, with a count of

(12s−1).\binom{12}{s-1}.

Summing over all ss:

∑s=113(12s−1)=212=4096.\sum_{s=1}^{13}\binom{12}{s-1}=2^{12}=\boxed{4096}.