[组合] 100人坐两排，每排50个座位，每个座位坐一个人，问坐法

isee

100人坐两排，每排50个座位，每个座位坐一个人。一个接一个地入座时，每排除第一个人外，其他人都必须坐在已有人的座位的左邻或右邻。问有多少种不同的坐法？

游客

数据那么大，直接考虑10个人坐一排就好了，思路应该是一样的。
另外，这个题有两个主要问题没交代清楚：
1、这10人原来有没有排好队？不然怎么一个一个来？
2、不同的坐法，是指就坐顺序，还是最后位置，还是都考虑？

isee

回复 2# 游客

1. 没有排好队，我的理解就是一次坐一人。
2. 第二点，似乎我也说不清。个人以为，人全部坐下来，就是一种坐法，如10个人，8个人相同，但AB的顺序不同，是两种坐法。

当然，这也是我个人理解此题。。


浅色不重要，向后看。

kuing

一排是比较简单的，昨晚就想好了，但两排似乎复杂得多，暂时还没搞定。

先写下一排的，不妨将人和座位依次编号为 $1$ 至 $n$。

设一排 $n$ 个位的坐法为 $f(n)$，考虑 $k$ 号人坐 $1$ 号位的坐法数。
若 $k=1$，则剩下的只能顺次到最后。
若 $k>1$，这时显然前 $k-1$ 个人必然坐在 $2$ 号至 $k$ 号位中，方法数为 $f(k-1)$，而后 $n-k$ 个人则只能顺次坐到最后。
综上有 $f(n)=1+f(1)+f(2)+\cdots+f(n-1)$，解得 $f(n)=2^{n-1}$。

kuing

或者这样，当一排 $n$ 个位的坐法为 $f(n)$ 时，再增加一人一位，这人只能坐在这堆人的左或右，所以 $f(n+1)=2f(n)$，直接得出 $f(n)=2^{n-1}$。

以 $n=4$ 来验证结果的正确性，坐法为：
1234
2134
3124
3214
4123
4213
4312
4321
共 8 种。

游客

回复 3# isee


    比如三个人ABC坐三位置，最后座位上依次是BAC，
这时是否考虑谁最先坐，谁最后坐？
如果不考虑就坐顺序，只看最后结果，那就是A（100，100）。
4楼和5楼说的，都是人已经排队了的，然后依次就坐。
如果人已经有就坐顺序了，只考虑他坐到哪个位置上，直接就乘法原理，即5楼方法。

isee

回复 6# 游客


    我明白了，”不考虑就坐顺序“，按k的来吧。

kuing

回复 7# isee

题意虽然交待得不够清晰，不过意思应该就是我理解的那样，因为只有那样理解这题才有玩头。

游客

回复 7# isee


    那就关注2个问题：
1、第一人坐哪排；2、另一排谁先坐。剩下的应该就是乘法原理了。

kuing

回复 9# 游客

按我的理解：
第一人任意坐；
无需坐满一排再坐另一排，否则一排和两排无异，那就太简单了

也就是说可以这样排 $\dfrac{6214}{8735}$
这样的话就不是简单的乘法原理可以玩了

游客

回复 10# kuing


   $ N=C_{100}^{50}·2^{49}·2^{49}$

色k

回复 11# 游客

噢，你的意思是先选50人坐第一排，剩下的坐第二排，而每排就和一排时是一样的，所以。。。唔。。。有道理！

isee

其实，我只是"发"上来。

看看单墫的解法。

kuing

回复 13# isee

嗯，和上面的讨论一样。

isee

回复 14# kuing


    对，巧的是，形式都一样，哈哈。。。。

走走看看

$单墫老师的解法是否正确呢？他的答案是:C（100,50）*2^{49}*2^{49}。$
如果是正确的，显然同平常的排列不一样啊。

在他的解说中，如果有甲乙丙3个人，坐1、2、3三个位置，
“甲坐1位，乙坐2位，丙坐3位”与“甲坐1位，丙坐2位，乙坐3位”被看作是一种方法。

走走看看

回复 16# 走走看看

可能是3个人先排队,A(3,3)种方法，然后按照这个顺序就座，即第一个入座的人必须是站在队列的第一个人，第二个入座的人只能是站在队列的第二个人，以此类推。入座的规则是，第一个人任意坐，其他的依照与前一个相邻的规则坐进去。
排队A(3,3)，3个座位4种坐法，
$根据乘法原理，应该是A(3,3)*2^{3-1}=24种吧？$

初步排了下，远远少于24种。
不做任何限制，3个人坐3个座位，A(3,3)才6种坐法，因此，限定后应少于等于6种。
难搞懂的东西。

经实际编排，并去除相同的情况，结果是6种，3的全排列，不是24种，也不是4种。