UC知道已知：n把椅子排成一排，任意m（2=<m<n）人不相邻的坐法为（n-m+1取m）
来源：百度知道 编辑：UC知道 时间：2024/06/06 13:57:25
注：若首尾椅子都无人坐且与有人坐的椅子不相邻，则被视为一个独立的情况来考虑。
比如：8个椅子（标号1，2，...，8），任意3人互不相邻的坐法有（8-3+1取3）=20种，这时，有2把空椅子与有人坐的椅子不相邻的坐法有4种（可以是：135，138，168，468）; 有1把空椅子与有人坐的椅子不相邻的坐法有12种（可以是：136，137，148，246，248，268，357，358，368，146，157，158）；有0把空椅子与有人坐的椅子不相邻 坐法有4种（可以是：147，247，257，258），有-1把空椅子的情况是0 。于是有20=4+12+4，现在就是想知道这里的4，12，4 怎么能计算出来，而不是查出来，最好能用一个组合数表示出来。在下感激不尽！！！！
总共n个椅子，m个人，k个椅子不与人相邻。
组合是：C(n-2m,k) * C(m+1,n-2m-k+1)
其中，C(n,r)代表n个元素中取r个的组合数。
由于我的过程太烦，有多张图要贴，不知楼主是否需要。
如果需要的话，我写在我的博客上好了，这样也便于修改：
http://hi.baidu.com/xtimz/blog/item/6314bb5190c1df541138c2ec.html
相当于，1到n取m个整数，任意两个不相邻
将这m个数从小到大排列
然后把第2个数减1，第3个数减2……第m个数减m-1
就变成1到n-（m-1）取m个数了
我只说说8个椅子的情况。A=人，B=空椅子。
1、有2把空椅子与有人坐的椅子不相邻的坐法。
把两把空椅子看做一部分，相当于一个人，让它与其它的3个人不相邻排列时，便是以上所举的这种情况（把A A A BB排列）。
除去这两把除外排空的椅子，剩下3把椅子，插在这3个人+两把椅子组合的中间，只能是插在4部分的3个中间的空位（成A B A B A B BB)。
所以最终的排法就变成了3个人和一个椅子组合的排法（把A A A BB排列）。显然是A41（1上，4下），所以是4种排法。
2、有1把空椅子与有人坐的椅子不相邻的坐法。
也是把两把椅子看成一个整体，先排列剩余的3个椅子和3个人，让他们都恰好互相隔开而坐，那么坐法就是2种（就是要么首位空，要么末尾空两种情况:ABABAB或者BABABA）。
然后把那个两把椅子的整体插入椅子和人已经排好的队列中。应该有7个位置可以选择的。但是分析，如果本来排列的椅子在最边了，再排上两椅子在边上，是不是就变成了两个空椅子与有人坐的椅子相隔了？所以所选的位置不能是7个，而是六个。排法有C16（1在上，6在下）。
所以总的排法有2*C16=12 种。<