[组合数学专项]1115 组合数学专项

1. 七夕节n对恋人（n>=2）围成一圈举行篝火晚会。晚会的规则是：男女相同，且每对恋人处在相邻的位置上。请问有多少种不同的圈子？
     
2. 书架一排有5个格子。现在有20本书，编号从1到20。要求20本书要摆放在同一排里，并且从左到右编号依次递减；每个格子至少有一本书；并且编号7，8，9的书籍必须在同一个格子里面。问，一共有多少种可能的摆放方法？

3. 6×9的的方格中，起点的左下角，终点在右上角，从起点到终点，只能从下向上，从左向右走，问一共有多少种不同的走法。

4. 10个相同的糖果，分给三个人，每个人至少要得一个。有()种不同分法


5. 一个合法的表达式由()包围，()可以嵌套和连接，如(())()也是合法 表达式；现在有 6 对()，它们可以组成的合法表达式的个数为____

6. 参加支付宝夜谈分享的同学共有50人，现设有甲、乙、丙三个夜谈主题。有40人选择参加甲夜谈主题，36人选选择参加乙夜谈主题，30人选择参加丙夜谈主题，兼选甲乙夜谈主题的有28人，兼选甲丙夜谈主题的有26人，兼选乙丙两门夜谈主题的有24人，甲乙丙三个夜谈主题均选的有20人，问三个夜谈主题未选的有多少人？( )

7. 6支笔，其笔身和笔帽颜色相同：但6支笔颜色各不相同，求全部笔身都戴错笔帽的可能性有多少种？

8. 

在如下8*6的矩阵中，请计算从A移动到B一共有____种走法。要求每次只能向上或向右移动一格，并且不能经过P。

 

9. 将7723810的各位数字打乱排序,可组成的不同的7位自然数的个数是?

10. a）ABCDEFG七人站队，要求A必须在B的左边（可不相邻），共有 ？ 种排法?
       b）在a的条件下若AB必须相邻，有 ？ 种排法？

==============================================================================
答案及解析:
1. 解析:
n 对恋人围成一个圈，n 对恋人全排列的情况是 n! ， 去除掉围成一个圈转动的情况围成一圈的所有情况是 (n-1)!
每对恋人对应的是 2 个人，男女，女男，一共 n 个位置，只要有一对男，女的位置发生变化就是一个新的圈子。
所以，n 个位置，每个位置都有 2 中不同的排列，所以一共 2^n 种，再加上围成一圈的所有情况，一共就是
2^n*(n-1)!

2. 解析:
这道题涉及到捆绑法+ 挡板法
捆绑法: 7,8,9 当做一个元素来看，因为顺序一定，所以不进行内部排序，
20 个元素编程 18 个元素，18 个元素形成了 17 个空挡 。而我们要将这 17 个元素分成 5 份，就需要 4 个挡板。

C(空挡个数，挡板个数) = C(17,4) = 2380

3. 解析:
这道题是经典的走格子问题
从起点到终点一共要走 (6+9) = 15 个格子，其中横坐标选 6 个 C(15,6) 便是所有不同的走法
C(15,6) = 5005

4. 解析:
这道题是最基本的挡板法
10个糖果形成 9 个空
分给 3 个人，需要 2 个板
因为这道题是每个人至少 1 颗糖，所以 C(空数目，板数目) = C(9,2) = 36

如果这道题变型的话，去掉”每个人至少要得一个“这个条件的话，对应的公式为 C(空挡数目-1+板数目-1，挡板数目-1)

5.解析:
这道题考察的是卡特兰数，对应的是 6 组，每组中的两个元素 '(', ')' 是需要有序列的，C(2n,n)/(n+1) = C(12,6)/(6+1)

6. 解析:
这道题考察的是组合数学中的容斥问题
未选主题的人数 = 总人数(全集) - (选择 甲， 乙 ， 丙 主题的人数)

|甲 U 乙 U 丙| = |甲| + |乙| + |丙| - |甲n乙| - |乙 n 丙| - |甲 n 丙| + |甲 n 乙n 丙|= 
                     = 40+36+30 - 28 - 26 - 24 + 20 = 48 
带入上述式子

50 - 48 = 2 

7.解析：
这道题做错了，是典型的容斥定理中的错排问题
级数和的公式背下来就行，要不就是记住递归公式，到时候往里面代数就可以了

下面的 n 代表的是， 将 n 个编号元素放在 n 个编号位置上，元素编号与位置编号不对应的方法数 D(n)

D(n) = (n-1)[D(n-2) + D(n-1)] ; (n > 2) 
D(0) = 1 ; D(1) = 0  

n = 6 

D(6) = 265


8.解析:
这道题考察的同样是容斥定理中的'斥'

首先计算出 A--> B 的所有可能是 C(12,7)
然后计算出 A->P->B 的所有可能，这一过程满足的是乘法技术原理
使用 A-> P 的所有情况乘上 P->B 的所有情况，

C(6,2)*C(6,3) 


最后结果 = C(12,7) - C(6,2)*C(6,3) = 492

9. 解析:
这道题考察的是，全排列 - 不满足条件的

首先 7 个数字全排列 = 7!
而不满足条件的是首项数字为 0 的这种情况，因为如果首项为 0 那么，
它就是一个六位数了，

7！-6! 

除了上述处理，还需要知道在这些数据中存在重复的数字， 7 ， 对于数字 7 来说 两个 7 之间存在一个先后的排序问题，
两个 7 A(2,2)= 2 , 这种重复性同样存在于 6! 这种情况中，

所以为了去掉两个 7 的排序问题，还需要除上两个 7 的排序问题
即， 

(7!-6!)/2! = 2160

10. 解析:
##这道题考察的是捆绑和排列去重
7!/2! ， 即， 全排列除上AB 全排列 = 2520 ， 我的乘法算错了

##这道题考察的是捆绑法将 AB 两个元素看做一个元素，一共6 个元素全排列，6! 
但是别忘了， AB 两个元素自己还有一个顺序全排列呢 2！ 
但是别忘了，这道题是在第一问的条件下展开的，即 AB 顺序是一定的，所以 2！ 是无需计算上的
  
所以这道题b)的答案为 6!


end