https://wiki.cvbbacm.com/ 2026-04-30T02:30:12+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-05-29T02:34:05+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics:permutaitiongroup&rev=1590690845&do=diff 理论 置换的定义 设$X$是有限集。不失一般性，取$X$为有前n个正整数组成的集合$\{1,2,\ldots,n\}$。$X$的置换$i_1,i_2,\ldots,i_n$可以看成是$X$到自身的一一映射，其定义为： $$f:X\to X$$ 其中$$f(1)=i_1,f(2)=i_2,\ldots,f(n)=i_n$$ 为了强调其可视性，常用$2\times n$的阵列来表示这个置换，如： $$\left( \begin{array}{c} 1 &2 &\ldots &n\\i_1 &i_2 &\ldots &i_n\end{array} \right)$$$\X={1,2,\ldots,n\}$$n!$$S_n$$S_n$$G$$X$$\forall f,g\in G,f\circ g\in G$$S_n$$\iota \in G$$\forall f\in G,f^{-1}\in G$$S_n$$n$$G=\{\iota \}$$$f\circ g=f\circ h \; \leftrightarrow \; g=h$$$f^{-1}$$T$$$f=\left (\begin… text/html 2020-05-25T10:33:44+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics:polya&rev=1590374024&do=diff 理论 理论部分太长惹。。晚点填 题目 1、模板: poj2154 Color 给正$n$边形染$m$种颜色，问有多少种染色方案。 对任意正$n$边形有如下$2n$阶二面体群： $G = \{\rho^0,..,\rho^{n-1},\tau^1,\ldots,\tau^n\}$ 然后通过$\text{Burnside定理}$:$$N(G,\mathcal{C})=\frac 1{|G|}\sum_{f\in G}|\mathcal{C}(f)|$$求解 对于旋转产生的置换$\rho^i$产生的贡献$|\mathcal{C}(\rho^i)|$，奇偶都一样，要通过$gcd$$|\mathcal{C}(\rho^i)|=m^{gcd(n,i)}$$$ \begin{cases} & \sum |\mathcal{C}(\tau^i)| & = & n\times m^{n/2+1} & (n\%2==1) \\ & \sum |\mathcal{C}(\tau^i)| & = & \frac n2\times m^{n/2}+\frac n2\times m^{n/2+…