返回题库

一排 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}.