标签：... le 组合 sum 中选笔记数学物品 kx

引入

Question 1

\(Question\quad1\)

从 \(n\) 个不同元素中选 \(r\) 个元素，每个元素可以选多次，求方案数。

分析：

从 \(1,2,3,...,n\) 中选 \(r\) 个元素，不能重复，方案数显然为 \(C_n^r\)。

这个问题可以换一种形式描述：

为 \(a_1,a_2,...a_r\) 这 \(r\) 个变量赋值，使得：\(1\le a_1<a_2<a_3<...<a_r\le n\)。

而当每个元素可以选多次时，问题就变为：

为 \(a_1,a_2,...a_r\) 这 \(r\) 个变量赋值，使得：\(1\le a_1\le a_2\le a_3\le...\le a_r\le n\)。

问题求解的关键，在于如何将 \(\le\) 转化为 \(<\)。

我们可以引入一个新的序列 \(b\) 来构造先前的形式。

设 \(b_1=a_1,b_2=a_2+1,b_3=a_3+2,...,b_r=a_r+r-1\)。

此时则有：\(1\le b_1<b_2<b_3<...<b_r=a_r+r-1\le n+r-1\)。

这样，问题便转换为：

从 \(1,2,3,...,n+r-1\) 中选 \(r\) 个元素，不能重复。

方案数显然为 \(C_{n+r-1}^{r}\)。

Question 2

\(Question\quad2\)

从 \(n\) 个不同元素中选 \(r\) 个不同元素，但是选择的元素不能相邻，求方案数。

分析：

仍然沿用上一题的思路，将此问题转化为：

为 \(a_1,a_2,...a_r\) 这 \(r\) 个变量赋值，使得：\(1\le a_1<a_2<a_3<...<a_r\le n\) 且 \(a_i+1<a_{i+1}\)「\(1\le i<r\)」。

可以将两个条件合并为一个条件：「\(a_i+1<a_{i+1}\) 等价于 \(a_i<a_{i+1}-1\)」

为 \(a_1,a_2,...a_r\) 这 \(r\) 个变量赋值，使得：\(1\le a_1<a_2-1<a_3-2<...<a_r-r+1\le n-r+1\)。

同样的，设 \(b_1=a_1,b_2=a_2-1,b_3=a_3-2,...,b_r=a_r-r+1\)。

此时则有：\(1\le b_1<b_2<b_3<...<b_r=a_r-r+1\le n-r+1\)。

这样，问题便转换为：

从 \(1,2,3,...,n-r+1\) 中选 \(r\) 个元素，不能重复。

方案数显然为 \(C_{n-r+1}^{r}\)。

组合数及其相关性质

\(C_{n+m}^n=C_{n+m}^m\)
- 证明：
  
  显然，\(C_{n+m}^n=C_{n+m}^m=\frac{(n+m)!}{n!m!}\)
\(C_n^m=C_{n-1}^{m-1}+C_{n-1}^m\)「组合数递推式」
- 证明一：
  
  \[\begin{aligned} C_{n-1}^{m-1}+C_{n-1}^m&=\frac{(n-1)!}{(m-1)!(n-m)!}+\frac{(n-1)!}{m!(n-m-1)!} \\&=\frac{m(n-1)!}{m!(n-m)!}+\frac{(n-m)(n-1)!}{m!(n-m)!} \\&=\frac{n(n-1)!}{m!(n-m)!}=\frac{n!}{m!(n-m)!}=C_n^m \end{aligned} \]
- 证明二：
  
  从 \(n\) 个物品中选 \(m\) 个物品，方案数为 \(C_n^m\)。考虑选的第 \(1\) 个物品：
  1. 若选该物品，则需要从剩下的 \(n-1\) 个物品中再选 \(m-1\) 个物品，方案数为 \(C_{n-1}^{m-1}\)。
  2. 若不选该物品，则需要从剩下的 \(n-1\) 个物品中选 \(m-1\) 个物品，方案数为 \(C_{n-1}^m\)。
  综上，总的方案数等于两种情况的方案数之和，即：\(C_n^m=C_{n-1}^{m-1}+C_{n-1}^m\)。
直接用 \(C_n^m=\frac{n!}{m!(n-m)!}\) 求组合数很容易溢出，而利用该递推式可以在 \(O(nm)\) 的时间内求解更大的组合数。

代码：
```
read(n),read(m);
for(int i=0;i<=n;++i) C[i][0]=1;
for(int i=1;i<=n;++i)
    for(int j=1;j<=i;++j)
        C[i][j]=C[i-1][j-1]+C[i-1][j];
write(C[n][m]);
```
其中，将 \(C\) 数组逐行输出，即可得到杨辉三角：
```
1
1   1
1   2   1
1   3   3   1
1   4   6   4   1
1   5  10  10   5   1
1   6  15  20  15   6   1
1   7  21  35  35  21   7   1
1   8  28  56  70  56  28   8   1
1   9  36  84 126 126  84  36   9   1
1  10  45 120 210 252 210 120  45  10   1
```
「从第 \(0\) 行第 \(0\) 列开始，杨辉三角第 \(i\) 行第 \(j\) 列的数就是 C[i][j]」
\((x+y)^n=\sum_{k=0}^nC_n^kx^{n-k}y^k=\sum_{k=0}^nC_n^kx^{k}y^{n-k}\)「二项式定理」
- 证明：「可以先跳过，最后再看」
  
  考虑用数学归纳法。
  
  当 \(n=1\) 时，\((x+y)^1=\sum_{k=0}^1C_1^kx^{1-k}y^k=C_1^0x^1y^0+C_1^1x^0y^1=x+y\) 成立。
  
  设二项式定理在 \(n=m-1\) 时成立，则有：
  
  \[(x+y)^{m-1}=\sum_{k=0}^{m-1}C_{m-1}^kx^{m-1-k}y^k \]
  由此：
  
  \[\begin{aligned} (x+y)^{m}&=(x+y)(x+y)^{m-1} \\&=(x+y)\sum_{k=0}^{m-1}C_{m-1}^kx^{m-1-k}y^k \\&=x\sum_{k=0}^{m-1}C_{m-1}^kx^{m-1-k}y^k+y\sum_{k=0}^{m-1}C_{m-1}^kx^{m-1-k}y^k \\&=\sum_{k=0}^{m-1}C_{m-1}^kx^{m-k}y^k+\sum_{k=0}^{m-1}C_{m-1}^kx^{m-1-k}y^{k+1}「将x,y乘入」 \\&=\sum_{k=1}^{m-1}C_{m-1}^kx^{m-k}y^k+\sum_{k=0}^{m-1}C_{m-1}^kx^{m-1-k}y^{k+1}+x^m「取出左边k=0的项」 \\&=\sum_{k=1}^{m-1}C_{m-1}^kx^{m-k}y^k+\sum_{k=1}^{m}C_{m-1}^{k-1}x^{m-k}y^{k}+x^m \\&「右边使k上下界+1,为使结果不变要让求和过程中的循环变量k-1」 \\&=\sum_{k=1}^{m-1}C_{m-1}^kx^{m-k}y^k+\sum_{k=1}^{m-1}C_{m-1}^{k-1}x^{m-k}y^{k}+x^m+y^m「取出右边k=m的项」 \\&=\sum_{k=1}^{m-1}(C_{m-1}^k+C_{m-1}^{k-1})x^{m-k}y^k+x^m+y^m「合并同类项」 \\&=\sum_{k=1}^{m-1}C_{m}^kx^{m-k}y^k+x^m+y^m「运用前面的组合数递推式」 \\&=\sum_{k=0}^{m}C_{m}^kx^{m-k}y^k「放入k=0和k=m的项,证毕」 \end{aligned} \]
- 应用「important！！！」
  1. \(C_n^0+C_n^1+...+C_n^n=2^n\)
    - 证明一：
      
      令二项式定理中的 \(x=y=1\)：
      
      \[2^n=(1+1)^n=\sum_{k=0}^nC_n^k1^{n-k}1^k=\sum_{k=0}^nC_n^k \]
      证毕。
    - 证明二：
      
      等式左边表示从 \(n\) 个物品中选 \(0、1、2...n\) 个物品的方案数之和，相当于在 \(n\) 个物品中选几个都行，而每个物品可以选或不选有 \(2\) 种方案，\(n\) 个物品则有 \(2^n\) 种方案。
    「这也说明，杨辉三角的第 \(n\) 行数字之和为 \(2^n\)」
  2. \(C_n^0-C_n^1+C_n^2-...=0\)
    - 证明一：
      
      令二项式定理中的 \(x=1,y=-1\)：
      
      \[0=(1+(-1))^n=\sum_{k=0}^nC_n^k1^{n-k}(-1)^k=\sum_{k=0}^nC_n^k(-1)^k \]
      证毕。
    - 证明二：
      
      该式可以描述为：在 \(n\) 个物品中选奇数个物品的方案数等于选偶数个物品的方案数。
      
      由于随意改变一个物品选/不选的状态，就可以使当前选物品个数的奇偶性改变，因此选奇数个物品的方案与选偶数个物品的方案要一一对应，这样才能满足前面的条件。这便要求两种方案数相等，否则不满足双射的对应关系。
    「这也说明，杨辉三角的每一行中，奇数列的数字之和等于偶数列的数字之和。结合上一条性质，杨辉三角第 \(n\) 行中，奇数列的数字之和、偶数列的数字之和均为 \(2^{n-1}\)」

~~还有几个公式，这里就不证明了，留做课后练习……~~

\(C_{n+r+1}^r=C_{n+r}^{r}+C_{n+r-1}^{r-1}+...+C_{n}^{0}\)
\(C_n^lC_l^r=C_n^rC_{n-r}^{l-r}\)
\(C_r^r+C_{r+1}^r+...+C_n^r=C_{n+1}^{r+1}\)

练习

Question 3

\(Question\quad3\)

求 \(\sum_{k=0}^n(C_n^k)^2\)

分析：

将 \((C_n^k)^2\) 拆为 \(C_n^k\cdot C_n^{n-k}\)，此题已解。

仔细想想，\(C_n^k\cdot C_n^{n-k}\) 表示的是从 \(n\) 个物品中选 \(k\) 个物品的方案数乘以从 \(n\) 个物品中选 \(n-k\) 个物品的方案数。

根据乘法原理，这等价于从 \(n\) 个物品中选 \(k\) 个物品，再从另外 \(n\) 个物品中选 \(n-k\) 个物品的方案数。

可以看作共有 \(2n\) 个物品，先从前 \(n\) 个物品中选 \(k\) 个，再从后 \(n\) 个物品中选 \(n-k\) 个，总共选 \(k+n-k=n\) 个。

由于从 \(k=0\) 枚举到 \(k=n\)，这就相当于从 \(2n\) 个物品中选 \(n\) 个物品的方案数，即 \(C_{2n}^n\)。

「前 \(n\) 个物品中已经选了 \(k\) 个，因为总共要选 \(n\) 个，因此后 \(n\) 个物品要选 \(n-k\) 个。\(k\) 从 \(0\) 取到 \(n\) 即可取遍所有可能」

因此：

\[\sum_{k=0}^n(C_n^k)^2=\sum_{k=0}^nC_n^k\cdot C_n^{n-k}=C_{2n}^n \]

Question 4

\(Question\quad4\)

要求把 \(x\) 拆成 \(k\) 个不同的组合数之和。
若 \(n_1\ne n_2\) 或 \(m_1\ne m_2\)，\(C_{n_1}^{m_1}、C_{n_2}^{m_2}\) 就叫做不同的组合数。
输出任意一种方案即可。
输入：一行两个整数 \(x\)、\(k\)。
输出：\(k\) 行，每行两个数 \(n_i、m_i\)，表示拆分结果中的第 \(i\) 个组合数 \(C_{n_i}^{m_i}\)。要求不能有完全相同的两行且 \(0\le m_i\le n_i\le x\)。
数据范围：\(x\le10^9,k\le10^6\)，数据保证有解。
样例
- 输入
```
6 2
```
- 输出
```
3 1
3 2
```

分析：

此题看似无从下手，其实非常非常简单。

先不管组合数，我们只需要将 \(x\) 拆分为 \(k-1\) 个 \(1\) 和 \(1\) 个 \(x-k+1\) 即可。

如何将这些数写成不同的组合数呢？

对于 \(k-1\) 个 \(1\)，可以写成：\(C_1^0、C_2^0、C_3^0、...、C_{k-1}^0\)。

对于 \(x-k+1\) ，可以写成：\(C_{x-k+1}^1\)。

此题秒解。

代码：

#include<iostream>
#include<cstdio>

using namespace std;

int x,k;

signed main()
{
    cin>>x>>k;
    for(int i=1;i<k;++i) cout<<i<<' '<<0<<endl;
    cout<<x-k+1<<' '<<1<<endl;
    return 0;
}

Lucas 定理

若 \(p\) 是质数，则对于任意整数 \(1\le m\le n\)，有：
\[C_n^m\equiv C_{n\bmod p}^{m\bmod p}\cdot C_{n/p}^{m/p}\pmod{p} \]

也就是把 \(n\) 和 \(m\) 表示成 \(p\) 进制数，对 \(p\) 进制下对每一位分别计算组合数，最后再乘起来。

~~可以用生成函数证明，读者自证～~~

标签：...,le,组合,sum,中选,笔记,数学,物品,kx
From： https://www.cnblogs.com/lingyunvoid/p/16771547.html

组合数学笔记

引入