组合数学入门

发表于 | 分类于 |

组合数学入门

由于老师直播卡到自闭才开始学习

抽屉原理

内容：

把 n+1 件东西放入 n 个抽屉，则至少有一个抽屉里放两件或两件以上的东西。

从令一角度说，把 n-1 件东西放入 n 个抽屉，则至少一个抽屉是空的。

证明：

对于第一条，考虑最差情况，既每个球都放到一个单独的抽屉里，这样还剩下一个球，将其放到任意一个抽屉里，该抽屉都会有两个，故成立。(第二条证明方法与第一条相似，建议百度)。

应用：

给出一个含有 n 个数字的序列，要找一个连续的子序列，使他们的和一定是 c 的倍数(n<=1000000;)

看到这道题一开始确实没看出来是抽屉原理。。。首先考虑$n^2$的情况，既枚举左端点和右端点，用前缀和来判断，然后TLE了。。。那么这道题和组合数有什么关系呢？我们给每个抽屉标号为0~c-1,代表了$ 当前数 \bmod b$的值，可以发现，如果 $a \bmod b=c \bmod b (a \geq b )$，则($(a-c) \bmod b=0$),如果我们对于每一位做前缀和处理，sum[i]代表第i位的前缀\和，将每一个sum放入抽屉中，如果有两个sum被放入同一个抽屉，则这两个前缀和之间就是可行区间，就是$if(sum[i] \bmod c=sum[j] \bmod c ) ans= 区间 i -j $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main()
{
cin>>n>>c;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n;i++)
{
if(chou[sum[i]%c]!=0)
{
for(int j=chou[sum[i]%c];j<=i;j++)
{
cout<<a[i]<<" ";
}
return 0;
}
else chou[sum[i]%c]=i;
}
}

德·摩根定律

内容：

$\lnot(p\vee q )\Longleftrightarrow(\lnot p) \wedge (\lnot q)$

$\lnot(p\wedge q )\Longleftrightarrow(\lnot p) \vee (\lnot q)$

证明：

枚举四种情况即可；

推广

$\lnot(p\vee q \vee z)\Longleftrightarrow(\lnot p) \wedge (\lnot q) \wedge (\lnot z)$

同样可推至多位；

（虽然我也不知道这和组合数有什么关系）

容斥原理

定义：

在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。

实例：

由于实在是想不出怎么解释了，还是直接上例子吧。。。

某校六⑴班有学生$45$人，每人在暑假里都参加体育训练队，其中参加足球队的有$25$人，参加排球队的有$22$人，参加游泳队的有$24$人，足球、排球都参加的有$12$人，足球、游泳都参加的有$9$人，排球、游泳都参加的有$8$人，问：三项都参加的有多少人？

解：容斥原理有一项很重要的内容：奇加偶减：以本体为例，我们先将单独参加的数加上：sum=$25+22+24=71$,再将参加两项的人减去：$sum-=12+9+8=42$,所以ans=$45-42=3$.

或许这么说有点不清楚，下面这张图或许更直白：

实例

容斥原理应用非常广，具体还是看百度吧。

排列数

定义

从 n 个元素的集合 S 中，有序的选出 r 个元素，叫做 S 的一个 r 排列，不同的排列总数$A_n^r$ 或 A(n,r)。

如果两个排列所含元素不全相同，或所含元素相同但顺序不同，就会被认为是不同的排列。

公式

$A_n^m=\frac{n!}{(n-m)!}$

公式证明：

$A_n^m=n\times (n-1)\times (n-2)……\times (n-m+1)=\frac{n!}{(n-m)!}$

特殊情况：

$A_n^n=n!$;

不全相异元素的全排列:

所谓不全相异元素的全排列，是指这样一个问题：若在 n 个元素中，有$n_1$个元素彼此相同,$n_2$个元素彼此相同，…,$n_m$个元素彼此相同，且 $n_1+n_2+…+n_m=n$则这 n 个元素的全排列叫做不全相异元素的全排列。

其方案数为：$\frac{n!}{n_1!+n_2!+n_3!+…+n_m!}$

证明: 全排列不考虑重复情况下，方案数为$n!$,而每一位重复的方案数为$n_i!$,将每一种重复的方案除去便得到总方案数。

错位排列:

内容：

所谓错位排列，既将标号为1至n的小球放入标号为1至n的盒子中，求每个小球的标号都不等于其盒子标号的方案数。

公式：

$D_n=n!*(\frac{1}{2!}-\frac{1}{3!}+….+(-1)^n\frac{1}{n!})$

公式证明：

首先，我们假设一对数$1,k$，就是在错排问题中的第一项和第k项，那么对于对于总方案数，我们分为两种情况：

1.第k项在第1位，第1项在第k位，这样的话，错排的方案数与第k位和第i位无关，为D(n-2)

2将第1项固定在第1位，剩下的错排，方案数D(n-1),然后将第k项与第1项交换，由于第k项不可能在第k位，所以不会与情况1有重复。

k共有n-1种情况(2~n),故有公式 $D_n=n-1(D_{n-1}+D_{n-2})$

化简既的上述公式。(确信)

圆排列：

内容：

既将n个数据选m个，首尾相连，求方案数；

公式：

$ans=\frac{A_n^m}{m}$

公式证明：

破圆为链，方案总数为$A_n^m$,变成圆之后，不同开头点的方案变的唯一，故除以m。

组合数

好，如果你上面这些都看懂了，那么，这节课才刚刚开始。前面那些，你就当我随便说说而已，你完全可以无视掉。

定义

从 n 个元素的集合 S 中，无序的选出 r 个元素，叫做 S 的一个 r 组合。

如果两个组合中，至少有一个元素不同，它们就被认为是不同的组合。

所有不同组合的个数，叫做组合数

符号

从m个数中取n个数计做$C_m^n$或c(m,n);

公式

$c_m^n=\frac{A_m^n}{n!}=\frac{\frac{n!}{(n-m)!}}{n!}=\frac{n!}{(n-m)!n!}$

公示证明

对于c来说，$c_m^n$与$A_m^n$的区别在于将方案求出之后是否进行全排列，全排列的可能方案数为n!故上述公式成立。

可重复组合数

概念

可重复组合数既在n个数中选择m个数，可重复选取，计做$H_n^m$

公式

$H_n^m=c_{n+m-1}^m=\frac{n+m-1}{m!(n-1)!}$

证明

可重复组合数的计算公式可以理解为，在n个数的基础上再加上m-1个万能数，这样在选择时，万能数被选就等同于多次选取一个数，可以感性理解一下，比较容易懂。

拓展

从 A={1,2,…,n} 中选取 m 个不相邻的组合，其组合数为：$C_{n-m+1}^m$,同样感心理解一下，减去的这些数就当成是两数之间的相邻了。

递推公式：

$c_n^m=c_{n-1}^{m-1}+c_{n-1}^{m}$

证：选取集合中任意一数作为特定数，将答案分为是否选取该特定数，一种情况为选取，情况数既在其他n-1个数中选取m-1个数的方案数，另一种情况既不选取该特定数，情况数既在其他n-1个数中选取m个数。

以上知识，大概在普及组+，也就是普及组$t4$难度，提高组吗，这些完全不够勇用，深入一点的可以看我的另一篇博客：组合数学提高.

-------------end.thanks for reading-------------