亲宝软件园·资讯

展开

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

帕格里亚齐 人气:1
也不知道老师讲不讲 话说好久没有水博客了,看了一点$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$组 必须是相同物品!!! ### 问题 > 现在有四只一模一样佳爱琉,有十一个一模一样神探要解开佳爱琉的死亡谜题,神探之间可以合作,但是每只佳爱琉的谜题必须有至少一个神探解谜,求有多少种搭配的方法呢 插板法的名字起的很形象啊,我们要做的就是插板求解这一问题 那怎么插板呢 首先我们将十一个神探小朋友一字摆开 ![](https://img2020.cnblogs.com/blog/1803578/202003/1803578-20200318212218623-819865500.png) 因为他们是一模一样的,而佳爱琉也都是一模一样的,所以我们不妨认为,每个佳爱琉的神探,都是左右相邻的 比如下面这样就是一种分组方案 ![](https://img2020.cnblogs.com/blog/1803578/202003/1803578-20200318212648380-1880358649.png) 怎么样,是不是很像在每组神探之间插入了一块板子 那我们就可以把问题转化成插三块板子有多少种方案 这三个板子有十个位置可插,不妨把这十个位置叫成$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

加载全部内容

相关教程
猜你喜欢
用户评论