数论——组合数学入门

这篇具有很好参考价值的文章主要介绍了数论——组合数学入门。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

排列组合

排列就是指从给定个数的元素中取出指定个数的元素进行排序;组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。--------OI Wiki

乘法原理和加法原理

加法原理,就好比一个工作,有 \(n\) 个解决的方案,第 \(i\) 项方案有 \(a_{i}\) 种不同的实现方式,所以这个工作有 \(a_{1}+a_{2}+a_{3}+\ldots+a_{n}\) 种方式来解决。

乘法原理,就好比一个工作,有 \(n\) 个步骤,第 \(i\) 步有 \(a_{i}\) 种方法来完成,所以这个工作的方式有 \(a_{1}\times a_{2}\times a_{3}\times \ldots \times a_{n}\) 种方式来解决。

排列数

给定 \(n\) 个数,从中选取 \(m\) 个数形成一个排列,可能的排列的数量,用 \(A_{n}^{m}\) 来表示(给定的数都为正整数)。

排列的计算公式:

\[A_{n}^{m}=n\times (n-1)\times (n-2)\times \ldots \times (n-m+1)=\frac{n!}{(n-m)!},n,m\in \mathbb{N^{*}},m\le n \]

其实就是分子分母同乘一个 \((n-m)!\)

其中 \(n!=1\times 2\times 3\times \ldots \times n\)

全排列就是当 \(n=m\) 的时候的一种特殊情况,此时 \(A_{n}^{n}=n!\)

组合数

区别就是,排列数是要求顺序的,而组合数是从 \(n\) 个元素里面选取 \(m\) 个数组成一个集合,问有多少种可能,通常用 \(C_{n}^{m}\) 来表示。

组合数计算公式:

\[C_{n}^{m}=\frac{n!}{m!(n-m)!} \]

可以发现只比排列的公式分母多了一个 \(m!\),因为不考虑顺序,所以可以想到,挑出来的 \(m\) 个元素组成的集合,里面的排列数是 \(m!\),而这里面的元素组成的集合都是相同的,也就是这 \(m\) 个数本来应该算一个,但是排列里面是算了 \(m!\),所以排列的公式除以 \(m!\) 即为我们要求的答案。

现在人们习惯用 \(\binom{n}{m}\) 表示 \(n\) 个元素里面选 \(m\) 个,但是我个人觉得不如用 \(C_{n}^{m}\) 直观,但我们还是要了解这个表示方式。

插板法

为什么叫插板法呢,因为他是用于解决把一些相同种类的元素分成不同的几组的一种方式, \(n\) 个元素分成 \(k\) 组,每一组至少有一个元素,就相当于拿 \(k-1\) 个板子放到 \(n-1\) 个空里,故因此而得名。

因为元素是完全相同的,所以我们根据上面的组合数可以得出公式:

\[\binom{n-1}{k-1} \]

本质是求 \(x_{1}+x_{2}+\ldots +x_{k}=n\) 的正整数解的组数。

改一下题目,如果要是允许有空的组呢?

如果这样的话,直接插板是不行的,因为有可能出现一堆板子都插到一个空隙里,这样的话求组合数就是错误的了。

所以我们先借来 \(k\) 个元素,在这 \(n+k-1\) 个空隙里插板,保证我们的每一组里面都是至少有 \(1\) 个元素,这样我们就把这个问题转化成了上一个问题,我们也可以得出公式:

\[\binom{n+k-1}{k-1}=\binom{n+k-1}{n} \]

可以想象一下,我们是先借了 \(k\) 个元素来保证我们的每一组里面都至少有一个元素,那么我们就按照第一个问题一样求解,最后把所有的板子都拿走,那么答案是不会有所变化的。

本质上是求 \(x_{1}+x_{2}+\ldots +x_{k}=n\) 的非负整数解的组数。

我们来加一些限制:如果说对于第 \(i\) 组我们需要至少分到 \(a_{i}\) 个元素,\(\sum a_{i}\le n\),我们又该怎么去求解呢?

和上面一样,本质上就是求 \(x_{1}+x_{2}+\ldots+x_{k}=n,x_{i}\ge a_{i}\) 的解的组数。

我们浅想一下,设 \(x_{i}'=x_{i}-a_{i}\),所以 \(x_{i}=x_{i}'+a_{i}\),那么我们要求的就是:

\[(x_{1}'+a_{1})+(x_{2}'+a_{2})+\ldots+(x_{k}'+a_{k})=n \]
\[x_{1}'+x_{2}'+\ldots +x_{k}'=n-a_{1}-a_{2}-\ldots-a_{k} \]
\[x_{1}'+x_{2}'+\ldots +x_{k}'=n-\sum a_{i} \]

那么我们知道 \(x_{i}'\) 是一个非负的整数,所以我们可以直接用问题二的公式:

\[\binom{n-\sum a_{i}+k-1}{n-\sum a_{i}} \]

\(1\)\(n\)\(n\) 个自然数选 \(k\) 个,这 \(k\) 个数种任何两个数都不相邻的组合有 \(\binom{n-k+1}{k}\) 种。

二项式定理

二项式就是由两项组成的式子,比如 \(2x\) 是一项式,\(2x+3y\) 是二项式,\(2x+3y+4z\) 是三项式,以此类推。

主要是用来解决 \((a+b)^{n}\) 的完全展开式的问题,其实是有规律可循的,我们可以通过这个定理快速获得第 \(i\) 项。

举一个最常见的例子:初中的完全平方公式 \((a+b)^{2}=a^{2}+2^{ab}+b^{2}\)

或者高中的完全立方公式 \((a+b)^{3}=a^{3}+3a^{2}b+3ab^{3}+b^{3}\)

相信你已经发现了他们系数的规律,那就是杨辉三角其实就是用来解释 \((a+b)^{n}\) 的各项的系数才有的杨辉三角,这个东西很奇妙,我们后面会提到他和组合数的关系。

数论——组合数学入门
公式就是

\((a+b)^{n}=\sum_{i=0}^{n}\binom{n}{i}a^{n-i}b^{i}\)

为什么呢,你可以考虑一下,我们在推导完全立方公式的时候,我们是一项一项暴力拆开成 \(n\)\((a+b)\) 相乘然后拆开合并的同类项,那么我们暴力拆一下可以知道,每一项都是从 \(n\)\((a+b)\) 中选 \(a\) 或者 \(b\) 相乘得到的,也就是说,我们可以把展开后的第 \(i\) 项看作是选了 \(i\)\(a\)\(n-i\)\(b\) 然后相乘得到的,而这样的组合方案是 \(\binom{n}{i}\),所以我们得到展开后第 \(i\) 项就是 \(\binom{n}{i}a^{n-i}b^{i}\) ,累加后就得到了上面的公式。

组合数性质

下面挑几个会的证明一下,不会的先咕了。

  1. \[\binom{n}{m}=\binom{n}{n-m} \]

证明:

\[\binom{n}{n-m}=\frac{n!}{[n-(n-m)]!(n-m)!}=\frac{n!}{m!(n-m)!}=\binom{n}{m} \]
  1. \[\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1} \]
  2. \[\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1} \]

证明:从 \(n\) 个数里面选 \(m\) 个数,就等同于第一个数选了,然后从 \(n-1\) 个中选 \(m-1\) 个数和第一个数没选,从 \(n-1\) 个数中选 \(m\) 个数的方案的和。或者你可以看看杨辉三角

  1. \[\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{n}=\sum_{i=0}^{n}\binom{n}{i}=2^{n} \]
  2. \[\sum_{i=0}^{n}(-1)^{n}\binom{n}{i}=[n=0] \]

证明:当 \(m\) 为奇数的时候,由性质 \(1\) 得,两项一一对应和为 \(0\) ,显然成立;当 \(m\) 为偶数的时候,利用 \(\binom{n}{0}=\binom{n-1}{0},\binom{m}{m}=\binom{m-1}{m-1}\) 替换,再用递推式得到:

\[\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}=\binom{n}{0}-\binom{n}{1}+\binom{n}{2}-\ldots-\binom{n}{n-1}+\binom{n}{n} \]
\[=\binom{n-1}{0}-\binom{n}{1}+\ldots-\binom{n}{n-1}+\binom{n}{n} \]
\[=\binom{n-1}{0}-(\binom{n-1}{0}+\binom{n-1}{1})+\ldots-(\binom{n-1}{n-2}+\binom{n-1}{n-1})+\binom{n-1}{n-1}=0 \]
  1. \[\sum_{i=0}^{m}\binom{n}{i}\binom{m}{m-i}=\binom{n+m}{m}(n\ge m) \]

证明:

\((n+m)\) 个数中选 \(r\) 个数,在前 \(n\) 个中选 \(i\) 个数的方案有 \(\binom{n}{i}\) 种,在后 \(m\) 个里选 \((r-i)\) 个数的方案数为 \(\binom{m}{r-i}\) 种,相乘求和即可得到

\[\binom{n+m}{r}=\sum_{i=0}^{r}\binom{n}{i}\binom{m}{r-i} \]

一开始的式子就是这个式子的 \(r=m\) 的情况。

  1. \[\sum_{i=0}^{n}\binom{n}{i}^{2}=\binom{2n}{n} \]

证明:其实是 \(6\) 的特殊情况,取 \(n=m\) 即可。

  1. \[\sum_{i=0}^{n}i\binom{n}{i}=n2^{n-1} \]

证明:把左边拆开得到:

\[=\sum_{i=0}^{n}\frac{n!}{(n-i)!(i-1)!} \]
\[=n\times \sum_{i=0}^{n}\frac{(n-1)!}{(n-i)!(i-1)!} \]
\[=n\times \sum_{i=0}^{n}\binom{n-1}{i-1} \]
\[=n\times \sum_{i=0}^{n-1}\binom{n-1}{i}=n\times 2^{n-1} \]
  1. \[\sum_{i=0}^{n}i^{2}\binom{n}{i}=n(n+1)2^{n-2} \]

证明:和性质 \(8\) 类似,先不证了。

  1. \[\sum_{i=0}^{n}\binom{i}{k}=\binom{n+1}{k+1} \]
  2. \[\binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k} \]

证明:

\[\binom{n}{r}\times \binom{r}{k}=\frac{n!}{r!(n-r)!}\times\frac{r!}{k!(r-k)!} \]
\[=\frac{n!}{k!(n-r)!(r-k)!} \]

分子与分母同乘 \((n-k)!\)

\[\frac{n!}{k!(n-k)!}\times\frac{(n-k)!}{(r-k)!(n-r)!}=\binom{n}{k}\times \binom{n-k}{r-k} \]
  1. \[\sum_{i=0}^{n}\binom{n-i}{i}=F_{n+1} \]
  2. \[\binom{n+m+1}{m}=\sum_{i=0}^{m}\binom{n+i}{i} \]

证明:首先对性质 \(3\) 变形:\(\binom{n}{m}+\binom{n}{m-1}=\binom{n+1}{m}\),并且我们知道 \(\binom{n}{0}=\binom{n+1}{0}=1\),那么就有:

\[\sum_{i=0}^{m}\binom{n+i}{i}=\binom{n}{0}+\binom{n+1}{1}+\ldots+\binom{n+m}{m} \]
\[=\binom{n+1}{0}+\binom{n+1}{1}+\ldots+\binom{n+m}{m} \]
\[=\binom{n+2}{1}+\binom{n+2}{2}+\ldots+\binom{n+m}{m} \]

最后就会得到:

\[=\binom{n+m+1}{n} \]

其中 \(F\) 指斐波那契数列,\([n=0]\) 表示如果 \(n\)\(0\) 则值为 \(1\),反之值为 \(0\)

其实还有二项式反演啥的但是我咕了。

组合数取模

有的时候我们题目里面会看到一些要求取模的那种问题。

当然我们都知道取模之后做除法是会出问题的,这个时候我们就需要结合逆元来做。

我们大致可以把这类问题分为三类:

一、\(1\le n,m\le 1000\)\(p\) 为任意实数,显然我们可以利用组合数的性质 \(\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}\) 来递推,但很明显 \(O(n^{2})\) 的复杂度不足以让我们在数据范围更大的地方使用。

二、\(1\le n,m\le 10^{6}\)\(p\) 为质数且 \(p> 10^{6}\)\(O(n)\) 预处理 \(i!\bmod{p}\),然后用费马小定理,扩欧啥的搞一搞 \(m!\)\((n-m)!\) 的逆元一乘就好,询问是 \(O(\log n)\) 的,当然也可以用线性求逆元直接 \(O(n\log n)\) 预处理 \(i!\)\(i!\) 的逆元,询问直接 \(O(1)\) 的:

ans=jc[n]*inv[m]*inv[n-m]%P;

三、若 \(p\) 为质数,\(1\le n,m\le 10^{18},p\le 10^{5}\) ,这个时候用卢卡斯定理来解决,具体下面讲。

其中最常用的是第二种了,因为题目里一般的取模都是 \(1e9+7\) 之类的某大质数,而且 \(10^{6}\) 也足够了。

卢卡斯定理

如上文所述,卢卡斯定理一般都是用于求解组合数取模。

上文中讲的,当 \(p<m\) 的时候,分母的乘法逆元是可能不存在的(\(m\) 可能是 \(p\) 的倍数),所以我们就要用到卢卡斯定理。

内容

对于非负整数 \(n,m\) 和质数 \(p\)

\[\binom{n}{m}\equiv \binom{\frac{n}{p}}{\frac{m}{p}}\times \binom{n\bmod{p}}{m\bmod{}p}\pmod{p} \]

(或许你在其他地方看见的都没有这个乘号,我觉得打出来更清楚)

引理一

对于组合数 \(\binom{p}{i}\),其中 \(p\) 为质数,满足如下同余式子:

\[\binom{p}{i}\equiv 0 \pmod{p}(0<i<p) \]

首先我们由组合数的定义式可以知道:

\[\binom{p}{i}=\frac{p!}{i!(p-i)!} \]

由于 \(0<i<p\) ,且 \(p\) 为质数,所以 \(i!\)\((p-i)!\) 都不可能是 \(p\) 的因子。又因为组合数一定是一个整数,所以 \(i!(p-1)!\) 一定是 \((p-1)!\) 的因子,这样组合数就可以表示成:

\[\binom{p}{i}=\frac{(p-1)!}{i!(p-i)!}p=kp \]

等式两边模 \(p\) 得到:

\[\binom{p}{i}\equiv 0 \pmod{p}(0<i<p) \]

引理二

对于整数 \(x\) 和素数 \(p\),满足如下同余式:

\[(1+x)^{p}\equiv (1+x^{p})\bmod{p} \]

还记得我们之前的二项式定理吗,我们用它来对左边进行二项式展开,然后用引理一:

\[(1+x)^{p}\equiv (\binom{p}{p}+\binom{p}{p-1}x+\ldots+\binom{p}{0}x^{p}) \]
\[\equiv (\binom{p}{p}+\binom{p}{0}x^{p}) \]
\[\equiv (1+x^{p})\bmod{p} \]

在第二步中将中间的多项都利用定理一给抹除了(因为模 \(p\)\(0\) 嘛)。

第三步中,因为 \(\binom{p}{p}=\binom{p}{0}=1\) 所以最后得到了这个式子。

证明

对于组合数 \(\binom{n}{m}\),将 \(n\)\(m\) 分别除上 \(p\) 得到商和余数,设:

\[n=sp+q(q<p) \]
\[m=tp+r(r<p) \]

\((1+x)^{n}\bmod{p}\) 转化成同余式:

\[(1+x)^{n}\equiv (1+x)^{sp+q} \]
\[\equiv ((1+x)^{p})^{s}(1+x)^{q} \]
\[\equiv (1+x^{p})^{s}(1+x)^{q} \]
\[\equiv \sum_{i=0}^{s}\binom{s}{s-i}x^{ip}\sum_{i=0}^{q}\binom{q}{q-i}x^{i}\pmod{p} \]

第四步是用到了二项式定理。

或者:

\[(1+x)^{n}\equiv (1+sx^{p}+\ldots+\binom{s}{s-i}x^{ip}+\ldots+x^{sp})(1+qx+\ldots+\binom{q}{q-i}x^{i}+\ldots+x^{q})\pmod{p} \]

由于这里 \(x\) 为未知数,所以等式左侧的 \(x^{i}\) 系数必然与等式右侧的系数 \(x^{i}\) 的系数一致。

对于左侧 \((1+x)^{n}\) 中,$x^{m} $ 对应的系数为 \(\binom{n}{n-m}=\binom{n}{m}=\binom{sp+q}{tp+r}\)

对于右侧,\(x^{m}=x^{tp+r}=x^{tp}x^{r}\),这有一种可能,即:

\[\binom{s}{s-t}x^{tp}\times \binom{q}{q-r}x^{r} \]
\[\binom{s}{s-t}\binom{q}{q-r}=\binom{s}{t}\binom{q}{r} \]

从而得到卢卡斯定理如下:

\[\binom{n}{m}\equiv \binom{sp+q}{tp+r}\equiv \binom{s}{t}\binom{q}{r}\pmod{p} \]

还可以表示成:

\[\binom{n}{m}\equiv \binom{\frac{n}{p}}{\frac{m}{p}}\binom{n\bmod{p}}{m\bmod{p}}\pmod{p} \]

这样就把问题转化为了递归的问题,只要 \(n\ge p\) 时,我们就可以调用这个公式,将问题转化为 \(\binom{n}{m}\bmod{p} (n<p)\) 的问题,而 \(p\le 10^{5}\) 时满足:\(n<p\le 10^{5}\)

可以通过 \(O(n)\) 的复杂度计算出 \(n!\bmod{p}\)\(inv_{n!}\bmod{p}\),预处理完直接调用。

感谢OI Wiki以及bloodstalk的帮助文章来源地址https://www.toymoban.com/news/detail-451967.html

到了这里,关于数论——组合数学入门的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【ACM组合数学 | 错排公式】写信

    题目链接:https://ac.nowcoder.com/acm/contest/54484/B 题意很简单,但是数据范围偏大。 首先来推导一下错排公式: [D(n) = n!sum_{k=0}^{n}frac{(-1)^k}{k!}] 设一个函数: [S_i表示一个排列中p_i = i的方案数] 那么我们可以知道: [D(n) = n! - |cup_{i=1}^{n}S_i|] 这个表示 所有方案数 减去 至少有

    2023年04月17日
    浏览(37)
  • 组合数学——Min-Max容斥

    Min-Max 容斥,即 $$max(S)=sum_{Tin S,Tneqemptyset}(-1)^{|T|-1}min(T)$$ 接下来证明上面那个式子是对的。定义 (S) 中共有 (N) 个元素,由大到小分别为 (s_1,s_2,dots,s_N) , (T_i) 为所有 (S) 大小为 (i) 的子集。 所有元素都大于 (s_i) 且大小为 (j) 的子集有 (tbinom{i-1}{j}) 个;则最

    2024年04月08日
    浏览(38)
  • P3799 妖梦拼木棒(组合数学)

                                                                                                       (学习自用) 提交65.01k 通过15.35k 时间限制1.00s 内存限制125.00MB 上道题中,妖梦斩了一地的木棒,现在她想要将木棒拼起来。 有 n 根木棒,现在从中选 44 根,

    2024年02月01日
    浏览(29)
  • 【组合数学】【动态规划】【前缀和】1735生成乘积数组的方案数

    【动态规划】【状态压缩】【2次选择】【广度搜索】1494. 并行课程 II 动态规划汇总 C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 组合数学 给你一个二维整数数组 queries ,其中 queries[i] = [ni, ki] 。第 i 个查询 queries[i] 要求构造长度为 ni 、每个

    2024年02月19日
    浏览(50)
  • 【深度优先搜索】【组合数学】【动态规划】1467.两个盒子中球的颜色数相同的概率

    【动态规划】【字符串】【行程码】1531. 压缩字符串 动态规划汇总 深度优先搜索 组合数学 桌面上有 2n 个颜色不完全相同的球,球上的颜色共有 k 种。给你一个大小为 k 的整数数组 balls ,其中 balls[i] 是颜色为 i 的球的数量。 所有的球都已经 随机打乱顺序 ,前 n 个球放入第

    2024年02月21日
    浏览(37)
  • 基于组合优化的3D家居布局生成看千禧七大数学难题之NP问题

    本文探讨了运筹学和组合优化方法在3D家居布局生成中的应用,并调研了AI生成3D场景布局的最新方法。文中结合了家居家装业务的实际应用场景,从算法建模和计算复杂度的角度上阐述了室内设计的布局问题中存在的难点,以及如何用简化和近似的思想来建模3D布局生成问题

    2024年02月07日
    浏览(34)
  • LeetCode 1359. Count All Valid Pickup and Delivery Options【动态规划,组合数学】1722

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月09日
    浏览(40)
  • 2018-2019 ACM-ICPC, Asia Nanjing Regional Contest G. Pyramid(组合数学 计数)

    题目 t(t=1e6)组样例,每次给定一个n(n=1e9),统计边长为n的上述三角形的等边三角形个数 其中等边三角形的三个顶点,可以在所有黑色三角形白色三角形的顶点中任取, 答案对1e9+7取模 思路来源 申老师 oeis A000332 Solution to Problem #3 题解 oeis打一下前四项的表,发现是C(n,4),并且

    2024年02月07日
    浏览(34)
  • Educational Codeforces Round 157 (Rated for Div. 2) F. Fancy Arrays(容斥+组合数学)

    题目 称一个长为n的数列a是fancy的,当且仅当: 1. 数组内至少有一个元素在[x,x+k-1]之间 2. 相邻项的差的绝对值不超过k,即 t(t=50)组样例,每次给定n(1=n=1e9),x(1=x=40), 求fancy的数组的数量,答案对1e9+7取模 思路来源 灵茶山艾府群 官方题解 题解 看到 至少 的字眼,首先想到容斥,

    2024年02月05日
    浏览(37)
  • 2023年MathorCup 高校数学建模挑战赛-A 题 量子计算机在信用评分卡组合优化中的应用-思路详解(模型代码答案)

    运筹优化类题目,不同于目标规划,该题限制了必须使用量子退火算法QUBO来进行建模与求解。本身题目并不难,但是该模型较生僻,给出的参考文献需要耗费大量时间去钻研。建议擅长运筹类题目且建模能力强的队伍选择。 问题 1 :在 100 个信用评分卡中找出 1 张及其对应阈

    2024年02月06日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包