也不知道老师讲不讲
话说好久没有水博客了，看了一点$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
