领域展开，坐杀数学

· · 个人记录

//Genshin impact,lauch! /* 4.25上午 组合数学初步 realskc

组合数

组合数C^mn (n,m) n选m 无序,二项式系数，狭义 n>m 下降幂 a^{n}=a(n-1)....(n-a+1)=a!/(a-n)! C^mn =n^{m} /m! 展开 拓展 n是实数 下降幂定义 默认狭义 组合数 对称m=n-m 加法公式 杨辉三角 n-1 m n-1 m-1 吸收公式 m(n,m)= n(n-1,m-1) 组合数求和 阶乘公式理解 sum{m=0,n} m(n,m) =n sum{m=0,n}(n-1,m-1)? 求和题 三项式恒等式 (a,b)(b,c)=(a,c)(a-c,b-c) 三部分 上指标求和sum{i=a,b} (i,a)=(b+1,a+1) 吸收公式 平行求和 sum (a+i,I)=(A+N+1,n) 二项式定理 (a+b)^n=sum{i=0,n}(n,i)a^ib^(n-i) 挑一个a或b 感性理解一下 带a=1,b=1(数学课) sum{i=0,n}(n,i)=2^n; 实数x,y,a (x+y)^n=sum{i=0,inf} (a,i)x^{i}y^{a-1} (-x+1)^{-n} 广义二项式定理展开 范德蒙德卷积恒等式 sum{i=0,a}(n,i)(m,a-1)=(n+m,a) (n+m)选a 意义容易理解 多项式乘法考虑 上指标范德蒙德卷积恒等式 sum{i=a,n-b}(i,a)(n-1,b)=(n+1,a+b+1) 组合意义 第a+1人位置，前面和后面的位置选a,b n球放m个盒子 n球m-1板 n+m-1 选m-1版 (n+m-1,n-1) n个整数变量，有下界，求和=k的解的数量，变量是盒子，k是球，把下界减掉 p5520 m个不同放到n个 不能相邻 变量=中间的间隙 边缘>=0,中间>=1,和为n-m，用前面的方法即可 n不同取m排成环，方案数？ 本来n^{m_}m列一个环 再除以m 多重集的排列数 k种ai个 派一列的方案数 若每种互不相同 一个会对mul ai!,sum!/mul ai! n=sum ai,取第一种... (n,a1)(n-a1,a2)..(1) 阶乘展开是一样的 证毕 下降幂的二项式定理 (a+b)^{n}=sum{i=0,n}(n,i)a^{i}b^{n-i} 归纳法易证 左边x(a+b-n+1) (a+b)^(n-1下)=(a+b)^(n下) (a-i)(b-n+1+i)x到右面的形式，归纳 特殊数列 错排 长度为n的错排数量？枚举第n个元素是i，第i个{是n？剩下n-2个是错排，不是n？这一位不是n交换，最后一位不=n 与n-1相对 感性理解} dn=(n-1)(dn-2+dn-1); 卡特兰数 2n括号序列的数量 枚举第一个括号的内部有几个括号 cn=ciCn-1-i，容易理解 cn=1/n+1(2n,n) 括号序列到二叉树里面左儿子外面右儿子 一一对应 出栈序列个数 左入右出 p4921 g(n)全错开 k对(n,k)n{k下}2^kg(n-k) 选情侣选位置换位置剩下的 考虑求g(n)?错开想到错排？第一排两男选n(n-1),其他错开2(n-1)g(n-2),伴侣不相邻，他俩构成g(n-1) ，两女类似，一男一女类似，不过要2 g(n)=4n(n-1)(2(n-1)g(n-2)+g(n-1)感性理解inf) 第二类斯特林数 {n,m} 元素分两集合 集合无标号，无空集 eg{3,2}=3 考虑递推 原先的一组 m{n-1,m},自己开始新的一组{n-1,m-1},{n,m}=m{n-1,m}+{n-1,m-1}{0,0}=0 普通幂转下降幂 sum{i=0,n} {n,i}m^{i下}=m^n 组合意义证明？斯特林：元素分两集合 集合无标号，无空集 刻画左右两边，证是一样的，左边n个不同物品放到m个不同盒子 ，右边枚举非空盒子数量i,放到无标号，在分配标号（下降幂），左边=右边 自然数k次幂和 sum{i=0,n}i_k 用上一页的式子展开 sum{i=0,n} sum{j=0,k} {k,j}i^{j下}=sum{i=0,n} sum{j=0,k} {k,j}j!(i,j)=sum{j=0,k} {k,j}j!sum{i=0,n} (i,j)=sum{j=0,k} {k,j}j!(n+1,j+1) 省选联考2020a p6620 n,x,p,m和f(x)=sum{i=0,m} aix^i求一个狮子（捕获6）转下降幂 只有1项 sum{k=0,n}k{i下}x^k(n,k)下降幂展开sum{k=0,n}i! x^k(n,k)(k,i) 三项式恒等 得i!(n,i)sum{k=i,n}(n-i,k-i)x^k,对k换元，sum{k=0,n-i}(n-i)x^k,二项式定理，把求和消掉，得i!(n,i)x^i(x+1)^(n-i),回到转下降幂，即f(x)=sum{i=0,m}bi x^{i下}，用第二类斯特林数展开，得f(x)=sum{i=0,m}a_i sum{j=0,i} {i,j}x^{j下}=sum{j=0,m}(sum{i=j,m}a_i{i,j})x^{j下}，得b，代入上一个式子 //鸽巢原理 //CF1305C %m意义下相等，然后就是0，但n>m必然出现，n<=m，暴力即可 Prufer 序列可以将一个带标号 n 个节点的树用 [1, n] 中的 n − 2 个整数表示.选择一个编号最小的叶节点并删掉它，然后在序列中记录下它连接到的那个节点的编号。重复 n − 2 次后就只剩下两个节点，算法结束。从Prufer序列到树.出现次数为deg-1,考虑从树到prufer序列，得编号最小得叶子是哪个，谁与他连边了，然后做更新deg，然后最后得连边 凯莱定理 n点tree n^(n-2) 因为有这么多得prufer n个连通块，每个ai点，连n-1条边联通，方案数？连通块看成点，ai是点权，答案=sum{tree} mul{i=1,n}a_{i}^{degi}改成枚举prufer序列，(mul{i=1,n}ai)sum{prufer}mul{i=1,n-2}a{p_i}=(sum{i=1,n}a_i)^(n-2)(mul{i=1,n}ai)(挑出来求和法) burnside 引理 p4980 polya定理 n点n边环，n色，染色，本质不同染色方案？不能n^n/n得到本质不同得环得数量 def:对于一个环，我们称它任意旋转能得到的所有环构成一个轨道。注意轨道指的是环的集合，与生成这个集合的初始环无关。显然所有的环被分成了若干个轨道，而答案就是轨道的数量。对于任意一个环，都存在一个最小的正整数 d，使得这个环在旋转d 格后会与自身重合。我们称 d 为这个环的最小循环节。容易发现，这个环所在轨道大小恰好为 d，且 d 一定是 n 的因子。把旋转看作变换，n种变换，保持环不变得变换是稳定子=n/d。对于轨道，每个环得稳定子都是n，总的稳定子就是ansn=(cir是环）sum_{circ}n/d(circ),令tra是变换，则sum n/d(cir)=sum{cir}sum{tra}[tra{cir}=cir]=sum{tra}sum{cir}[tra{cir}=cir]=sum{i=1,n}n^{gcd(n,i)}ans=sum{i=1,n}n^{gcd(n,i)}/n=sum{d|n}phi(n/d)n^d/n，线性筛预处理即可。 群论 旋转推广为变换 环推广为元素，构成变换群 变换群：对于一个变换的集合，如果其中存在恒等变换，且每个变换都存在逆变换，则称这个变换的集合构成群。如果群 G 的一个子集 H 也满足群的限制，则称 H 是 G 的子群。可以发现，任意一个元素的稳定子都是变换群的一个子群。 轨道稳定子定理 对于任意一个元素，它所在的轨道的大小乘它的稳定子大小等于变 换群的大小。 感性理解：轨道里每个元素的稳定子大小相同 令 G 表示变换群，|G| 表示 G 的大小。由于每个轨道内元素的稳定子大小之和均等于 |G|，故所有元素的稳定子大小之和等于轨道个数乘 |G|。令 X/G 表示所有轨道构成的集合。对于一个变换 g，Xg 表示在 g作用下的不动点数量（在变换 g 下保持不变的元素数）。则有：|X/G|=sum{g \in G} X^g/|G|

*/