作业帮排列组合中相同元素不相邻的问题有n个位置放数字1和2,要求相邻的位置不能同时有数字1（数字2可以相邻）,有多少种排法?我的想法是对数字1插空,根据含有1的个数分类讨论,而且n也得分奇偶
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/29 13:52:39
排列组合中相同元素不相邻的问题有n个位置放数字1和2,要求相邻的位置不能同时有数字1（数字2可以相邻）,有多少种排法?我的想法是对数字1插空,根据含有1的个数分类讨论,而且n也得分奇偶
排列组合中相同元素不相邻的问题
有n个位置放数字1和2,要求相邻的位置不能同时有数字1（数字2可以相邻）,有多少种排法?我的想法是对数字1插空,根据含有1的个数分类讨论,而且n也得分奇偶数
排列组合中相同元素不相邻的问题有n个位置放数字1和2,要求相邻的位置不能同时有数字1（数字2可以相邻）,有多少种排法?我的想法是对数字1插空,根据含有1的个数分类讨论,而且n也得分奇偶
你的想法很正确,构造序列的思路是:
(1)先把[2]摆放好;(全是[2],只有1种排列)
(2)把每个[1]逐个查到2的空隙中;
1个[1]只能占1个空隙,所以,选择空隙的[组合数],就是我们所求的[排列数].要求组合数,我们需要知道[1]和[2]的个数.
设有a个[1],b个[2].因为:
a + b = n ——①,
所以我们只需确定其中一个.
另外,要想把[1]全部插入,就得有足够多的空隙.即:
b ≥ a + 1;——②
举个例子：设n = 8；根据①、②可知：
(b, a) ∈ {(8, 0), (7, 1), (6, 2), (5, 3), (4, 4)};
那么,结果就是:
C(9, 0) + C(8, 1) + C(7, 2) + C(6, 3) + C(5, 4);
规律很明显:
计算组合数的两项之和 = n + 1;
前项 ≥ 后项;——这是组合数公式的要求.
所以,对于任意的 n,结果就是:
ΣC(i, n+1-i); (i = n+1, n, n-1, n-2, …, 0)
如果考虑当后项＞前项时,组合数都是0,那用上面的结果就可以了.
如果你想给出明确的界限,也不难:
i ≥ n+1-i
i ≥ (n+1)/2;
n 为偶数: i ≥ n/2;
n 为奇数: i ≥ (n+1)/2;