有几种坐法

王守恩

n个人(编号 1,2,...,n)，n个座位(编号 1,2,3,...,n)，依序(1,2,3,...,n)对号入座，
如果允许第 1 个人(编号 1)随便坐，后面的人尽可能对号入座，问有几种坐法？
题目没说好：n个人依序(1,2,3,...,n)对号入座，一个一个进来，尽可能对号入座，
如果自己的座位被别人座了，就得另外找个座位坐下来，不能站在那里，也不能换座位。

gxqcn

为了满足“尽可能对号入座”，
1) 如果第 1 个人坐在 1 号座，那大家都按序坐即可，只有一种坐法；
2) 如果第 1 个人错坐在第 k 号座，那让第 k 个人坐在第 1 号座，其余人全部对号入座，也只有一种坐法。

.·.·.

gxqcn 发表于 2019-5-15 15:46
为了满足“尽可能对号入座”，
1) 如果第 1 个人坐在 1 号座，那大家都按序坐即可，只有一种坐法；
2) 如 ...

2^{n-1}
只需要统计第2到第n个椅子哪里坐错了人
每一种坐错方案都对应唯一一个坐法
这就完成了证明