Warning: session_start(): open(/tmp/sess_a9061596035dea5439bf754d2dda4b1b, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/feed.php on line 40
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/feed.php on line 41
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/feed.php on line 42
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/feed.php on line 43
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/httputils.php on line 28
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/httputils.php on line 29 CVBB ACM Team 2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics
https://wiki.cvbbacm.com/
2025-07-07T15:51:37+0800CVBB ACM Team
https://wiki.cvbbacm.com/
https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.icotext/html2020-05-29T02:34:05+0800Anonymous (anonymous@undisclosed.example.com)2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics:permutaitiongroup
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/html2020-05-25T10:33:44+0800Anonymous (anonymous@undisclosed.example.com)2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics:polya
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+…