组合数学（待完成） - 一个人的心灵旅程

计数原理：加法计数原理（分类），乘法计数原理（分步），减法计数原理，除法计数原理
排列组合：

与顺序有关的摆放或选择称排列(Permutation)。

P(n,r)=\dfrac{P(n,n)}{P(n-r,n-r)}=\dfrac{n!}{(n-r)!}

规定 $P(n,r)=0\ \text{when}\ n<r$

与顺序无关的摆放或选择称组合(Combination)。

\begin{pmatrix}n\\r\end{pmatrix}=\dfrac{P(n,r)}{P(r,r)}=\dfrac{n!}{r!(n-r)!}

规定$$\begin{pmatrix}n\r\end{pmatrix}=0\ \text{when}\ n）最大个数，应用容斥原理，将上界限制转化为下界限制，换元求解，即得到各元素都有无穷个时，元素分配个数均不超过各自最大个数的方法数，而这等于题意所求的方法数（无穷相对于最大个数多出的部分不会影响方法数） <ul> <li>生成函数： <pre><code class="language-mathjax">//TODO</code></pre> 对偶问题：将r个相同的球放入k个不同盒子，其中第i个盒子容量为<code class="katex-inline">n_i</code>，允许盒子为空的方法数</li> </ul> 对应不定方程： <pre><code class="language-mathjax">x_1+x_2+...+x_k=r\\其中0\le x_1\le n_1,0\le x_2\le n_2,...,0\le x_k\le n_k</code></pre> 求方程解的个数 PS：关于球的相同与不同，由于盒子放球可以一个一个放，因此对不同的球，将球序固定后放入盒子的顺序不同时，即便每个盒子分配到的球数相同，得到的方法也不同；而相同的球只要结果是每个盒子分配到相同的球数，放入盒子的顺序不同也是一样的方法。由于前者可以映射到元素放置的顺序，而后者可以映射到放置的顺序整体消序（即组合），故分别对应上了多重排列和多重组合。 矩阵填数：先选择填哪些空<code class="katex-inline">C_n^k</code>，再对各数排序<code class="katex-inline">A_k^k</code> 非攻击性车：先选行<code class="katex-inline">C_n^k</code>，再选列<code class="katex-inline">A_n^k</code>，最后做其他限制（如颜色）//TODO <ul> <li>不定方程的解个数（注意解<code class="katex-inline">(1,1,2)</code>与<code class="katex-inline">(1,2,1)</code>不同）</li> </ul> 对于不定方程 <pre><code class="language-mathjax">x_1+x_2+...+x_k=r</code></pre> 1.约束为<code class="katex-inline">0\le x_1,0\le x_2,...,0\le x_k</code>，即非负整数解，直接使用多重组合 2.约束为<code class="katex-inline">a_1\le x_1,a_2\le x_2,...,a_k\le x_k</code>，即下界约束，换元为情况1。特别的，对于正整数解，有<code class="katex-inline">a_1=a_2=...=a_k=1</code>（对应将r个相同的球放入k个不限大小的不同盒子中的方法数，不允许空盒） 这里可以看出，先取走特殊的元素，剩下的一般元素用一般的排列组合即可解决，例如这里可以先每个盒子都分配一个元素，剩下的就变成了多重组合 3.约束为<code class="katex-inline">0\le x_1\le n_1,0\le x_2\le n_2,...,0\le x_k\le n_k</code>，即上界约束，使用容斥原理或生成函数 4.同时拥有上界约束和下界约束，先换元转为情况3，再解决 5.约束为<code class="katex-inline">x_1=mt_1,x_2=mt_2,...,x_k=mt_k;m,t_1,t_2,...t_k\in N</code>，使用生成函数解决 对于不定方程 <pre><code class="language-mathjax">t_1x_1+t_2x_2+...+t_kx_k=r\\t_1,t_2,...t_k\in N</code></pre> 换元，换为上种情况5，使用生成函数。 <ul> <li>排列生成</li> </ul> 递归生成算法邻位对换算法从逆序生成排列算法（最大数开始，最小数开始） 逆序，逆序数，逆序列，逆序个数 <ul> <li>组合生成</li> </ul> 字典序生成算法反射Gray码序生成算法（递归法，逐次法） Gray码序与字典码序的转换 基于字典序的r-组合生成算法 ![image-20210615105537321](C:\Users\Mr Liu\AppData\Roaming\Typora\typora-user-images\image-20210615105537321.png) <ul> <li>二项式定理：</li> </ul> <pre><code class="language-mathjax">(a+b)^n=\sum_{i=0}^{n}\begin{pmatrix}n\\i\end{pmatrix}a^ib^{n-i}</code></pre> 杨辉三角组合意义： 1.某数为左上正上之和 2.某数为从(0,0)到该数位置的路径数，允许的移动方向规定为向下和向右下 （最好参考ppt理解） 延伸公式： 1. <pre><code class="language-mathjax">\sum_{i=0}^{n}\begin{pmatrix}n\\i\end{pmatrix}p^i=(p+1)^n</code></pre> 2. <pre><code class="language-mathjax">\sum_{i=0}^{n}(-1)^{n-i}\begin{pmatrix}n\\i\end{pmatrix}p^i=(p-1)^n</code></pre> 二项式系数性质：1.单峰，最大值可能有一个（n为奇数）或两个（n为偶数），单峰点为<code class="katex-inline">n/2</code>或其两侧的整数 链，反链，最大链：定义参照ppt。 对于n元素集合，最大链有<code class="katex-inline">n!</code>个，其元素个数为<code class="katex-inline">n+1</code>，构造方法为逐一填入（详见ppt）；反链最多元素个数为<code class="katex-inline">\begin{pmatrix}n\\n/2\end{pmatrix}</code>（整数除法），最大反链为包含所有该集合的n/2元素子集的集类（因此最大反链有一个或两个，与n奇偶有关） 多项式定理： <pre><code class="language-mathjax">(a_1+a_2+...a_k)^n=\sum_{n_1+n_2+...+n_k=n}\begin{pmatrix}n\\n_1n_2...n_k\end{pmatrix}a_1^{n_1}a_2^{n_2}...a_k^{n_k}</code></pre> 多项式系数<code class="katex-inline">\begin{pmatrix}n\\n_1n_2...n_k\end{pmatrix}=\dfrac{n!}{n_1!n_2!...n_k!}</code>，即有限多重全排列数 帕斯卡公式： <pre><code class="language-mathjax">\begin{pmatrix}n\\n_1n_2...n_k\end{pmatrix}=\begin{pmatrix}n\\n_1-1\ n_2...n_k\end{pmatrix}+\begin{pmatrix}n\\n_1n_2-1\ ...n_k\end{pmatrix}+...+\begin{pmatrix}n\\n_1n_2...n_k-1\end{pmatrix}</code></pre> 牛顿二项式定理： <pre><code class="language-mathjax">(a+b)^\alpha=\sum_{i=0}^{\infin}\begin{pmatrix}\alpha\\i\end{pmatrix}a^ib^{\alpha-i},0\le |a|<|b|</code></pre> 此时二项式系数被扩展，允许出现实数，有 <pre><code class="language-mathjax">\begin{pmatrix}\alpha\\r\end{pmatrix}=\begin{cases}\dfrac{\alpha(\alpha-1)...(\alpha-r+1)}{r!},r\ge1\\1,r=0\\0,r\le-1\end{cases},\alpha\in \R,r\in \Z</code></pre> 等价形式： 1. <pre><code class="language-mathjax">(1+z)^\alpha=\sum_{i=0}^{\infin}\begin{pmatrix}\alpha\\i\end{pmatrix}z^i,|z|<1</code></pre> 2. <pre><code class="language-mathjax">(1+z)^{-n}=\sum_{i=0}^{\infin}(-1)^i\begin{pmatrix}n+i-1\\i\end{pmatrix}z^i,|z|<1 \\(1-z)^{-n}=\sum_{i=0}^{\infin}\begin{pmatrix}n+i-1\\i\end{pmatrix}z^i,|z|<1</code></pre> （生成函数有用） <ul> <li>矩形寻路问题：对两个方向的运动进行多重排列计数</li> <li>容斥原理：对于集合B和集合B的一个覆盖<code class="katex-inline">\{A_i\}</code>，有</li> </ul> <pre><code class="language-mathjax">|\bigcap_{i\in C} \bar A_i|=|B|-|\bigcup_{i\in C} A_i|=|B|-\sum_{i\in C}|A_i|+\sum_{i,j\in C}|A_i\cap A_j|-...+(-1)^{|C|}|\bigcap_{i\in C} A_i|</code></pre> 注意这里就是为了摆脱你对重复计数数不清的烦恼，在计数等号右边时，只需考虑并集的情况，无需考虑其他的影响；也注意一定要记完整，不能因为有几项相等而擅自等价为一项而遗漏。 顺便一提，等号右边的sum个数依次为<code class="katex-inline">|C|,\begin{pmatrix}|C|\\2\end{pmatrix},...,\begin{pmatrix}|C|\\|C|\end{pmatrix}</code>，可以提示计数与简化计数 错位排列：对<code class="katex-inline">1,2,...,n</code>，其排列<code class="katex-inline">i_1,i_2,...,i_n</code>满足<code class="katex-inline">i_1\neq1,i_2\neq2,...,i_n\neq n</code>时，为一个错位排列，其个数为<code class="katex-inline">D_n</code>。用容斥原理求解，即反过来求解有若干个元素在其自然位置上，其他元素任意排（没有限制）的方法数。 <pre><code class="language-mathjax">D_n=n!(1-\dfrac{1}{1!}+\dfrac{1}{2!}-...+(-1)^n\dfrac{1}{n!}),n\ge1</code></pre> 递推公式：<code class="katex-inline">D_n=(n-1)(D_{n-1}+D_{n-2}),D_n=nD_{n-1}+(-1)^n,D_2=1,D_1=0</code> 绝对禁止位置排列：对错位排列的推广，原理相同，注意一般描述为位置禁止哪些元素，可以反过来理解为元素禁止在哪些位置，具体看需要是转换成就让禁止元素进入这些位置来求解还是就让这些位置进入这些禁止元素求解。 带禁止位置的非攻击性车：//TODO 相对禁止位置排列：带捆绑法的绝对禁止位置排列。相对原来的位置有何限制意味着原来是自然位置 <ul> <li>若干泰勒展开：</li> </ul> <pre><code class="language-mathjax">1+x+x^2+x^3+...=\dfrac{1}{1-x},|x|<1</code></pre> <pre><code class="language-mathjax">1-x+x^2-x^3+...=\dfrac{1}{1+x},|x|<1</code></pre> <pre><code class="language-mathjax">1+x+\dfrac{x^2}{2!}+\dfrac{x^3}{3!}+...=\text e^x</code></pre> <pre><code class="language-mathjax">1+2x+4\dfrac{x^2}{2!}+8\dfrac{x^3}{3!}+...=\text e^{2x}</code></pre> <pre><code class="language-mathjax">1+\dfrac{x^2}{2!}+\dfrac{x^4}{4!}+...=\dfrac{1}{2}(\text e^{x}-\text e^{-x})</code></pre> <pre><code class="language-mathjax">1+x^2+\dfrac{x^4}{2!}+\dfrac{x^6}{3!}+...=\text e^{x^2}</code></pre> 注意<code class="katex-inline">\dfrac{1}{1-x^n}</code>与<code class="katex-inline">\dfrac{1}{(1-x)^n}</code>的区别 <ul> <li>生成函数：对数列<code class="katex-inline">\{h_n\}</code>，其生成函数为<code class="katex-inline">g(x)=\sum_{n=0}^{\infin}h_nx^n</code>。有穷数列可以通过补0得到无穷数列</li> </ul> 多重组合数（<code class="katex-inline">h_n</code>为方程<code class="katex-inline">x_1+x_2+...+x_k=n</code>解的个数）的生成函数 <pre><code class="language-mathjax">g(x)=\sum_{n=0}^{\infin}\begin{pmatrix}n+k-1\\k\end{pmatrix}x^n=\dfrac{1}{(1-x)^k}\\=(1+x+x^2+...)^k=(\sum_{e_1=0}^{\infin}x^{e_1})(\sum_{e_2=0}^{\infin}x^{e_2})...(\sum_{e_k=0}^{\infin}x^{e_k})\\=\sum_{e_1+e_2+...+e_k=n=0}^{\infin}x^{e_1}x^{e_2}...x^{e_k}</code></pre> 注意 <pre><code class="language-mathjax">\sum_{e_1+e_2+...+e_k=n=0}^{\infin}x^{e_1}x^{e_2}...x^{e_k}\neq \sum_{n=0}^{\infin}x^n</code></pre> 根据约束对各个<code class="katex-inline">(1+x+x^2+...)</code>内的单项式进行去除，然后再合并展开，得到目标公式 例如<code class="katex-inline">(x+x^2+x^3)</code>代表该变量约束为<code class="katex-inline">1\le x_i \le 3</code>，<code class="katex-inline">(x+x^3+x^5+...)</code>表述约束为该变量只能取偶数，等等 <ul> <li>指数生成函数：对数列<code class="katex-inline">\{h_n\}</code>，其生成函数为<code class="katex-inline">g^{(e)}(x)=\sum_{n=0}^{\infin}\dfrac{h_n}{n!}x^n</code></li> </ul> 多重排列数（<code class="katex-inline">h_n</code>为k阶（定义参开头）无限多重n排列）的指数生成函数 <pre><code class="language-mathjax">g^{(e)}(x)=\sum_{n=0}^{\infin}\dfrac{k^n}{n!}x^n=\text e^{kx}\\=(1+\dfrac{x}{1!}+\dfrac{x^2}{2!}+...)^k=(\sum_{e_1=0}^{\infin}\dfrac{x^{e_1}}{e_1!})(\sum_{e_1=0}^{\infin}\dfrac{x^{e_2}}{e_2!})...(\sum_{e_1=0}^{\infin}\dfrac{x^{e_k}}{e_k!})\\=\sum_{e_1+e_2+...+e_k=n=0}^{\infin}\dfrac{1}{e_1!e_2!...e_k!}x^{e_1}x^{e_2}...x^{e_k}</code></pre> 多重排列数（<code class="katex-inline">h_n</code>为k阶（定义参开头）有限多重全排列，第i种元素有<code class="katex-inline">n_i</code>个）的指数生成函数（注意各个<code class="katex-inline">n_i</code>固定！） <pre><code class="language-mathjax">g^{(e)}(x)=f_{n_1}(x)f_{n_2}(x)...f_{n_k}(x)=\sum_{0\le m_1\le n_1,0\le m_2\le n_2,...,0\le m_k\le n_k,m_1+m_2+...+m_k=n=0}^{\infin}\dfrac{1}{m_1!m_2!...m_k!}x^{m_1}x^{m_2}...x^{m_k}</code></pre> 其中 <pre><code class="language-mathjax">f_{n_i}(x)=(1+\dfrac{x}{1!}+\dfrac{x^2}{2!}+...+\dfrac{x^{n_i}}{n_i!})\\</code></pre> 带约束时，同样对各子式进行限制，合并展开即可，注意最终要凑出<code class="katex-inline">n!</code>分母，使分子直接为所求 注意： <pre><code class="language-mathjax">\sum_{e_1+e_2+...+e_k=n=0}^{\infin}\dfrac{1}{e_1!e_2!...e_k!}x^{e_1}x^{e_2}...x^{e_k}\neq\sum_{0\le m_1\le n_1,0\le m_2\le n_2,...,0\le m_k\le n_k,m_1+m_2+...+m_k=n=0}^{\infin}\dfrac{1}{m_1!m_2!...m_k!}x^{m_1}x^{m_2}...x^{m_k}</code></pre> <ul> <li>递推：1.确定其中一个，降阶；2.由阶小的补充，升阶</li> </ul> 等差，等比，差比（前n项和可用错位相减，裂项相消，通项公式待定系数求解） 斐波那契数列：1.递推公式：<code class="katex-inline">f_n=f_{n-1}+f_{n-2},f_0=0,f_1=1</code> 2.前n项和<code class="katex-inline">S_n=f_{n+2}-1</code> 3.斐波那契数是偶数当且仅当n被3整除斐波那契数能被3整除当且仅当n可被4整除斐波那契数能被4整除当且仅当n可被6整除 4. <pre><code class="language-mathjax">f_n=\begin{pmatrix}n-1\\0\end{pmatrix}+\begin{pmatrix}n-2\\1\end{pmatrix}+...+\begin{pmatrix}n-k\\k-1\end{pmatrix},k=[(n+1)/2](\text{down})</code></pre> <ul> <li>k阶常系数线性齐次递推关系</li> </ul> <pre><code class="language-mathjax">h_n=a_1h_{n-1}+a_2h_{n-2}+...+a_kh_{n-k},a_k\neq0</code></pre> 求解方法： 1.特征方程法 特征方程为 <pre><code class="language-mathjax">x^n-a_1x^{n-1}-a_2x^{n-2}-...-a_kx^{n-k}=0</code></pre> 设有k个不同的根<code class="katex-inline">q_1,q_2,...,q_k</code>，则<code class="katex-inline">h_n</code>解为 <pre><code class="language-mathjax">h_n=c_1q_1^n+c_2q_2^n+...+c_kq_k^n</code></pre> 给定初值<code class="katex-inline">h_0,h_1,h_2,...,h_{k-1}</code>来确定<code class="katex-inline">c_1,c_2,..,c_k</code> 若有t组重根，其中第i组重数为<code class="katex-inline">s_i</code>，则设 <pre><code class="language-mathjax">H_n^{(i)}=c_1q_i^n+c_2nq_i^n+...+c_nn^{s_i-1}q_i^n</code></pre> 则解为 <pre><code class="language-mathjax">h_n=H_n^{(1)}+H_n^{(2)}+...+H_n^{(t)}</code></pre> 2.生成函数法 利用递推公式配凑： <pre><code class="language-mathjax">g(x)=h_0+h_1x+h_2x^2+...</code></pre> 则有 <pre><code class="language-mathjax">-a_1xg(x)=-(a_1h_0x+a_1h_1x^2+a_1h_2x^3+...)\\ -a_2x^2g(x)=-(a_2h_0x^2+a_2h_1x^3+a_2h_2x^4+...)\\ ...\\ -a_kx^kg(x)=-(a_kh_0x^k+a_kh_1x^{(k+1)}+a_kh_2x^{(k+2)}+...)</code></pre> 得 <pre><code class="language-mathjax">(1-a_1x-a_2x^2-...-a_kx^k)g(x)=h_0+(h_1-a_1h_0)x+(h_2-a_1h_1-a_2h_0)x^2+...+(h_n-a_1h_{n-1}-a_2h_{n-2}-...-a_kh_{n-k})x^n+...</code></pre> 可以利用<code class="katex-inline">h_n-a_1h_{n-1}-a_2h_{n-2}-...-a_kh_{n-k}=0</code>消去n及之后的项。 得到<code class="katex-inline">g(x)=\dfrac{p(x)}{q(x)}</code>的形式后，用部分分式法，分解为多个<code class="katex-inline">\dfrac{c}{(1-rx)^n}</code>的乘积，再将其用牛顿二项式定理展开 <ul> <li>k阶常系数线性非齐次递推关系</li> </ul> <pre><code class="language-mathjax">h_n=a_1h_{n-1}+a_2h_{n-2}+...+a_kh_{n-k}+b_n,a_k\neq0</code></pre> 类似于微分方程，通解<code class="katex-inline">f_n</code>的得到通过求解对应的齐次递推关系，而若能得到一个特解<code class="katex-inline">c_n</code>，则解为<code class="katex-inline">h_n=kf_n+c_n,k\in Z</code> ![image-20210614003524554](C:\Users\Mr Liu\AppData\Roaming\Typora\typora-user-images\image-20210614003524554.png) 特解：1.<code class="katex-inline">b_n</code>是n的k次多项式，则<code class="katex-inline">h_n</code>也是 2.<code class="katex-inline">b_n</code>是指数函数<code class="katex-inline">r^n</code>，若r不是特征根（0重根），则<code class="katex-inline">h_n=cr^n</code>；若r是k重特征根，则<code class="katex-inline">h_n=r^n\sum_{i=0}^kc_in^i</code> 3.<code class="katex-inline">b_n=p_nr^n</code>，r是k重特征根，<code class="katex-inline">p_n</code>是n的p次多项式，则<code class="katex-inline">h_n=r^n\sum_{i=0}^pc_in^{m+i}</code> <ul> <li>Catalan数</li> </ul> 递推公式： <pre><code class="language-mathjax">C_n=C_0C_{n-1}+C_1C_{n-2}+...+C_{n-1}C_0;C_0=1</code></pre> <pre><code class="language-mathjax">C_n=\dfrac{4n-2}{n+1}C_{n-1}</code></pre> 通项公式： <pre><code class="language-mathjax">C_n=\dfrac{1}{n+1}\begin{pmatrix}2n\\n\end{pmatrix}</code></pre> 推导： <pre><code class="language-mathjax">g(x)=C_0+C_1x+C_2x^2+...\\ (g(x))^2=C_0^2+(C_0C_1+C_1C_0)x+(C_0C_2+C_1C_1+C_2C_0)x^2+...=C_1+C_2x+C_3x^2+...</code></pre> 故 <pre><code class="language-mathjax">g(x)-C_0=x(g(x))^2</code></pre> 解得 <pre><code class="language-mathjax">g(x)=\dfrac{1\pm\sqrt{1-4C_0x}}{2x}=\dfrac{1\pm\sqrt{1-4x}}{2x}</code></pre> 由<code class="katex-inline">g(0)=C_0=1</code>，故只能取<code class="katex-inline">g(x)=\dfrac{1-\sqrt{1-4x}}{2x}</code> 展开 <pre><code class="language-mathjax">g(x)=\sum_{n=1}^{\infin}\dfrac{1}{n}\begin{pmatrix}2n-2\\n-1\end{pmatrix}x^{n-1}=\sum_{n=0}^{\infin}\dfrac{1}{n+1}\begin{pmatrix}2n\\n\end{pmatrix}x^n</code></pre> 因为 <pre><code class="language-mathjax">(1+x)^{\frac{1}{2}}=\sum_{n=0}^{\infin}\begin{pmatrix}1/2\\n\end{pmatrix}x^n=\begin{pmatrix}1/2\\0\end{pmatrix}+\begin{pmatrix}1/2\\1\end{pmatrix}x+\begin{pmatrix}1/2\\2\end{pmatrix}x^2+...\\ =1+\dfrac{\frac{1}{2}}{1!}x-\dfrac{\frac{1}{2}\frac{1}{2}}{2!}x^2+\dfrac{\frac{1}{2}\frac{1}{2}\frac{3}{2}}{3!}x^3+...\\ =1+\dfrac{1}{2}x+\sum_{n=2}^{\infin}(-1)^{n-1}\dfrac{(2n-1)!!}{n!2^n}x^n\\ =1+\dfrac{1}{2}x+\sum_{n=2}^{\infin}(-1)^{n-1}\dfrac{(2n-2)!}{n!(n-1)!2^{2n-1}}x^n\\ =1+\dfrac{1}{2}x+\sum_{n=2}^{\infin}\dfrac{(-1)^{n-1}}{n2^{2n-1}}\begin{pmatrix}2n-2\\n-1\end{pmatrix}x^n\\ =1+\sum_{n=1}^{\infin}\dfrac{(-1)^{n-1}}{n2^{2n-1}}\begin{pmatrix}2n-2\\n-1\end{pmatrix}x^n</code></pre> 其中， <pre><code class="language-mathjax">\dfrac{(2n-1)!!}{n!2^n}=\dfrac{(2n-1)!!(2n-2)!!}{n!(n-1)!2^{n-1}2^n}=\dfrac{(2n-2)!}{n!(n-1)!2^{2n-1}}</code></pre> 所以 <pre><code class="language-mathjax">\sqrt{1-4x}=(1-4x)^{1/2}=1-\sum_{n=1}^{\infin}\dfrac{2}{n}\begin{pmatrix}2n-2\\n-1\end{pmatrix}x^n</code></pre> Catalan数的递归关键在于如何分治，且先拿一般的<code class="katex-inline">h_n</code>得到递推式，再根据递推式和初值确定与Catalan数的对应关系 定理：考虑由n个+1和n个-1构成的2n项序列<code class="katex-inline">a_1, a_2,…, a_{2n}</code>，其部分和满足：<code class="katex-inline">a_1 + a_2 + ? + a_k \ge 0(k=1,2,…,2n)</code> 的序列的个数等于第n个Catalan数 证明：减法原理，可接受与不可接受，一一映射（详见ppt），每一个不可接受的n个1，n个-1的序列都对应一个普通的n+1个1，n-1个-1的序列（这个证明思路可以推广使用） 拟Catalan数： <pre><code class="language-mathjax">C_n^*=n!C_{n-1}</code></pre> <pre><code class="language-mathjax">C_n^*=(4n-6)C_{n-1}^*;C_1^*=1</code></pre> <pre><code class="language-mathjax">C_n^*=(n-1)!\begin{pmatrix}2n-2\\n-1\end{pmatrix}</code></pre> <ul> <li>两类Stirling数</li> </ul> 第二类Stirling数：将n个不同的球放入k个相同的无限容量的盒子，每个盒子不允许为空的方法数(由鸽笼原理知n>=k，可令$$S(n,k)=0,nk） | | 不同 | 相同 | 不允许 | 有限制 | 先求盒子不同，再消序 | | 相同 | 不同 | 允许 | 每盒最多1个 | $\begin{pmatrix}n\\k\end{pmatrix}$ | | 相同 | 不同 | 允许 | 无限制 | $\begin{pmatrix}n+k-1\\n\end{pmatrix}$ | | 相同 | 不同 | 允许 | 第i盒最多 $n_i$ 个；其他限制 | 生成函数，容斥原理；生成函数，换元+容斥原理 | | 相同 | 不同 | 不允许 | 每盒最多1个 | $\begin{pmatrix}n\\k\end{pmatrix}$ （n>k） | | 相同 | 不同 | 不允许 | 无限制 | 先每个盒子填一个，再将剩下的填入。 $\begin{pmatrix}n-k+k-1\\n-k\end{pmatrix}=\begin{pmatrix}n-1\\n-k\end{pmatrix}=\begin{pmatrix}n-1\\k-1\end{pmatrix}$ | | 相同 | 不同 | 不允许 | 第i盒最多 $n_i$ 个 | 生成函数，先分配+容斥原理 | | 相同 | 相同 | 允许 | 无限制 | 分拆数 $\sum_{i=0}^{k}p_n^i$ | | 相同 | 相同 | 不允许 | 无限制 | 分拆数 $p^k_n$ |

（不允许也算一种限制，下界限制，但是下界限制不仅限于不允许为空）

（对多重r-排列先分组再分配其实是先多重r-组合，然后就转化为了多重全排列，便于计算）

（待补充）

鸽笼原理：

鸽笼原理强化形式：

Ramsey定理：

群：

Polya计数

发表回复 取消回复

发表回复取消回复