[CSP初赛] 组合数学的三个技巧以及从另一方面思考组合类问题

也不知道老师讲不讲 话说好久没有水博客了，看了一点$python$然后就去搞文化课了 正好网课讲到组合数学，然后觉得还蛮难的（其实是我变菜了），就想到了以前的$csp$的组合数学基础 果然被我找到了，**插板法，插空法和捆绑法** ~~就从数学作业里找例题吧~~ 最后还有关于**四个人选三个项目的情况数**与**三个人选四个项目的情况数**这两种问题如何用进制解决 ~~感觉把博客写成参考书了呢~~ ## 前置芝士 ### 阶乘 $n!=1*2*3*...*(n-1)*n$ ### 组合数 组合数的定义：从$n$个不同元素中任取$m$个的所有组合的个数为$C_{n}^{m}$ $C_{n}^{m} = \frac{n!}{m!(n-m)!}$ ### 排列数 排列数的定义：从$n$个元素中任取$m$个元素的所有排列的个数为$A_{n}^{m}$ $A_{n}^{m} = \frac{n!}{(n-m)!}$ 可以发现组合数只强调选出的组合的数量，而排列还要求组合里的元素有序（小声$bb$和后文无关哈） # 插板法 ### 适用范围:$n$个相同物品分为不同的$m$组 必须是相同物品！！！ ### 问题 > 现在有四只一模一样佳爱琉，有十一个一模一样神探要解开佳爱琉的死亡谜题，神探之间可以合作，但是每只佳爱琉的谜题必须有至少一个神探解谜，求有多少种搭配的方法呢 插板法的名字起的很形象啊，我们要做的就是插板求解这一问题 那怎么插板呢 首先我们将十一个神探小朋友一字摆开  因为他们是一模一样的，而佳爱琉也都是一模一样的，所以我们不妨认为，每个佳爱琉的神探，都是左右相邻的 比如下面这样就是一种分组方案  怎么样，是不是很像在每组神探之间插入了一块板子 那我们就可以把问题转化成插三块板子有多少种方案 这三个板子有十个位置可插，不妨把这十个位置叫成$1,2,3...$ 那我们就可以进一步把问题转化成，在这十个数字中任选三个 这个问题很好求解，答案就是$C_{10}^{3} = \frac{10!}{3!7!} = 120$ ### 基本模型 这类题目可以抽象出如下模型 >把$n$个**相同**物品分成**不同**的$m$组的方案数为$C_{n-1}^{m-1}$ ## 插板法的变形 ### 变形一与变形二 为什么放到一起？？？ 当然是因为太像了啊 >有四只小狗，叫豆豆一号，豆豆二号……有十一个一模一样的屁桃（一种桃子），现在要把屁桃分给豆豆们，有的豆豆可能分不到，请问有多少种分配方案 这个好像和模型不太一样，怎么办 那当然就是把它变得和模型一样喽 我们发现最多会有三只豆豆没分到屁桃，太可怜了，干脆先给四只豆豆每人发一个屁桃~~然后再收回来~~ 那这样就会多出四个屁桃，所以问题就变成了十五个屁桃，四只豆豆，每只豆豆至少一个屁桃 然后就可以很轻易地抽象出模型： >把$15$个**相同**物品分成**不同**$4$组，有几种方案 答案是$C_{14}^{3}$ ~~欸？好像忘了把屁桃收回来了，真是喂了狗了~~ >有四只小狗，叫豆豆一号，豆豆二号……有十一个一模一样的屁桃（一种桃子），现在要把屁桃分给豆豆们，鉴于上一题中豆豆们太可怜，现在要求每只豆豆最少两个屁桃，请问有多少种分配方案 有上一题的启发就好办多了嘛，我们先给每只豆豆一个屁桃 问题变为有七个屁桃，要分给四只豆豆，每只豆豆至少一个，有多少种方案，这不就是基本模型吗 ### 变形三 >停电了，单元楼的楼梯有$11$个台阶，为了防止隔壁的老奶奶散步回来看不到路，豆豆要在楼梯上放三支蜡烛，每个台阶上只能放一个，相邻的台阶不能都放（因为作用不大），请问有多少种放置的方案 $emmmm$又变得和模型不一样了，怎么办呢 我们的思路还是把没见过的模型转换成我们会的模型 我们稍微把题目里的主人公们换一换，我们把蜡烛换成板子，把台阶换成神探 怎么样，是不是很熟悉，这不就是用$3$块板子把八位神探分成四组嘛 等等，是不是漏了什么？？？ 哦对了，这个题里我们可以把板子插在最左边和最右边 答案就是$C_{7+2}^{3}$ # 捆绑法 和乘法原理很像的 ### 适用范围 用于解决某几个物品必须在一起的排列问题 ### 问题 >豆豆有好多书啊，有全套七本哈利波特，四本数学课本和三本课外杂志。出于对魔法世界的敬畏，豆豆必须要把哈利波特摆在一起，在数学老师的淫威之下（其实我们的数学老师人很好的QWQ），也必须把数学课本摆在一起，请问有几种摆放方法呢 我们要把不会的转变成我们会的 把哈利波特当做一个整体$A$，把数学课本当做一个整体$B$，剩下的三本杂志是$CDE$ 然后问题就转换成了五个字母，有多少种排列的方法 答案是$A_{5}^{5}$ 但是哈利波特的七本也是不同的啊，所以$A$内部的摆放方法有$A_{7}^{7}$ 同理，数学课本也有$A_{4}^{4}$种，这就是典型的分步乘法 所以最终答案是$A_{5}^{5}A_{4}^{4}A_{7}^{7}$ ### 基本模型 >有$n$个物品，其中有$m$个物品$A$必须摆在一起，摆放方案数为$A_{n-m+1}^{n-m+1}A_{m}^{m}$ 要注意必须在一起的物品有没有顺序要求哦，如果没有要求，答案就是$A_{n-m+1}^{n-m+1}$ # 插空法 其实是插板法的变形 ### 适用范围 用于某几个物品不能在一起的问题 ### 问题 >屁桃和豆豆吵架了，恰好这天全球七大蠢蛋要在一起照相，豆豆和屁桃当然不想挨在一起照相，请问有多少种拍照的方式呢 还是老思路啦，化不会的为会的 怎么办呢 既然屁桃和豆豆这么倔，那不如我们把他俩当做两块顽固的板子吧 问题变成了两块板子把五个蠢蛋分成三组，每组最少一个人，有多少种方案 容我细细思考，发现板子可以插在最左边和最右边 答案就是$C_{6}^{2}$ # 总结 相同物品分组用插板法 存在相邻物品用捆绑法 存在不邻物品用插空法 ### 千万注意考虑两端能否插板的问题 # 一些其它问题的独特思考方法和思路 其实是一些自己发现的奇技淫巧（很多人应该本来就会吧 >三个运动员，要报名两个项目，每个人只能且必须报一项，请问有几种报名方案 如何判断这个问题的答案是$2^3$还是$3^2$呢，以下是从信息奥赛的角度进行理解 受到答案形式的启发（$3^2$或$2^3$）我们考虑采用转换进制的方法 二进制数$111_2$的大小是多少呢？简单运算一下发现是$7$ 运算方法$2^0+2^1+2^2$，为了方便我们表示为$2^3-1$ 那么比$7$小的自然数有几个呢？八个，即$2^3-1+1 = 2^3$ 他们的二进制形式分别是 $000$，$001$，$010$，$011$，$100$，$101$，$110$，$111$ 观察一下，有什么发现？ 这八个数，就是用$0$和$1$组成一个三位数的所有情况 那我们再深入思考，我们用$0$表示参加项目$A$，用$1$表示参加项目$B$ 用第一位数表示第一个人，第二位数表示第二个人，第三位数表示第三个人 那么以上八个数字就是所有的情况了，可见共有八种情况，也就是$2^3$种 第一个$2$表示可以选的项目数，我们把选项目$A$或$B$叫做运动员的状态，那第一个$2$就是状态数 第二个$3$就是运动员的数目 同样的，如果是三个运动员报名四个项目，我们可以表示成$4^3 - 1 + 1 = 4^3$ ### 总而言之，面对没见过的奇怪的题，我们要想办法把它转化成我们熟悉的形式 不知道怎么分类，随手扔到数论区里吧~ 啊我要去睡觉了，好困QWQ