# Way to Pólya Counting Theory 本文是 [Way to Burnside's Lemma](/yTfRpxg7QvW3bqQgkY-77A) 的拓展，主要包含以下內容 * cyclic index * inventory * pólya counting theorem * pólya counting formula 本質上，Pólya Enumeration theorem (簡稱PET) 是 Burnside's lemma 的拓展版本， 能夠解決類似限制顏色選擇次數的本質不同計數問題。 請參考 https://oi-wiki.org/math/combinatorics/polya/ For the sake of trying to confuse you the readers，來先給出一些定義。 ## Cyclic index 給定有限群 $G$ 作用在有限集 $X$, 其中 $|X| = n$, 則 $g \in G$ 的 cyclic index (循環指標) 是 $$z_{g,X}(t_1,\dots,t_n) = \prod_{O \in X/\langle g \rangle}t_{|O|} = \prod_{k=1}^{n}t_k^{r_k(g)} \in \mathbb Z[t_1,\dots,t_n]$$ 其中 $r_k(g) := |\left\{\langle g \rangle \cdot x \in X/\langle g \rangle : |\langle g \rangle \cdot x| = k\right\}|$ 算的是有幾個 order 為 k 的 $\langle g \rangle$-orbit. :::spoiler 第二個等號的證明 把各種 $O$ 按照大小分類，分成 $k := |O| \in\{ 1, \dots, n\}$ 再來相乘 $$\prod_{O \in X/\langle g \rangle}t_{|O|} = \prod_{k=1}^{n}\prod_{O \in X/\langle g \rangle:\,|O|=k}t_k = \prod_{k=1}^{n}t_k^{r_k(g)}$$ ::: 並且，群 $G$ 本身的 cyclic index 是 $$z_{G,X}(t_1,\dots,t_n) = \frac{1}{|G|}\sum_{g\in G}z_{g,X}(t_1,\dots,t_n) \in \mathbb Q[t_1,\dots,t_n]$$ ### Remark $\alpha$ 關於這個定義，有一個值得一提的是：根據上一篇文章，我們知道 $$|Map(X,C)/G| = \frac{1}{|G|}\sum_{g\in G}|C|^{|X/\langle g \rangle|}$$ 因此改寫右邊等式就有 $$|Map(X,C)/G| = z_{G,X}(|C|,\dots,|C|)$$ 細節如下 ::: spoiler $$\begin{aligned} z_{G,X}(|C|,\dots,|C|) &= \frac{1}{|G|}\sum_{g\in G} t_{g,X}(|C|,\dots,|C|) \\ &= \frac{1}{|G|}\sum_{g\in G} \prod_{O \in X/\langle g \rangle} |C| & (\text{as } t_i = |C| \quad\forall i)\\ &= \frac{1}{|G|}\sum_{g\in G}|C|^{|X/\langle g \rangle|} \\ &= |Map(X,C)/G| \end{aligned}$$ ::: ### Remark $\beta$ 如果根據 Cayley theorem 把 $G$ 看成一個 $X$ 的置換群，我們知道 $g$ 的每個元素都可被分解為一堆 disjoint cycle，則上述定義的 $r_k(g)$ 就等於 $g$ 的 cycle decomposition 中長度為 $k$ 的數目。 因此，把「各種長度的軌道數相加 = 軌道總數」這句話寫成數學，就有 $$\sum_{k=1}^{|X|}{r_k(g)} = |X/\langle g \rangle|$$ 以及，「每個 $X$ 的元素都屬於一個軌道」就可以寫成 $$\sum_{k=1}^{|X|}{kr_k(g)} = |X|$$ ### Remark $\gamma$ 上述定義中 $z_{g,X}(t_1,\dots,t_n)$ 是一個 degree 為 $\sum_{k=1}^{|X|}{r_k(g)} = |X/\langle g \rangle|$ 的 monomial. ## Inventory and pattern inventory polynomial 定義 inventory 如下: $\forall f \in Map(X,C)$ $$p(f) = \prod_{x\in X}f(x) = \prod_{c\in C}c^{|f^{-1}(c)|}$$ :::spoiler 第二個等號的證明 由交換累加順序，證明如下 $$\begin{aligned} \prod_{x\in X}f(x) &= \prod_{c\in C}\prod_{x\in X: f(x) = c} c \\ &= \prod_{c\in C}\prod_{x\in X: x \in f^{-1}(c)} c \\ &= \prod_{c\in C} c^{|f^{-1}(c)|} \end{aligned}$$ ::: Pattern inventory polynomial of $C$ is $$p_{G,X}(C) = \sum_{O_f \in Map(X,C)/G}p(f)$$ 其中 $f$ 可以是 $O_f$ 的任意元素 我們不禁要問，真的可以*任意元素*嗎？ 請見 :::spoiler 良定義的證明 令 $O_f \in Map(X,C)/G$ 為給定。假設 $f,\,f' \in O_f$ 為某兩個著色函數。(此處的 $f'$ 不是指微分...) 因爲他們同屬一個軌道，假設有 $g\in G$ 使得 $f(g^{-1} \cdot x) = f'(x)\quad \forall x\in X$ 則確實，因為 $g^{-1}\cdot G = G$，則可以改寫 product 如下 $$\begin{aligned} \prod_{x\in X}f(x) &= \prod_{x'\in X}\prod_{x : g \cdot x = x'}f(x) \\ &= \prod_{x'\in X}\prod_{x : x = g^{-1} \cdot x'}f(x) \\ &= \prod_{x'\in X}f(g^{-1}\cdot x') \\ &= \prod_{x'\in X}f'(x) \end{aligned}$$ 此即說明 $f\in O_f$ 可以任取。 ::: ### Remark 實務上，我們知道 $C$ 可以被看做顏色的集合，然而這邊在定義 $p(f)$ 的時候卻把「顏色」給相乘了。 事實上，這是把每個 $c\in C$ 的元素都看成另一個變數 $x_c$ 並且才把 $p(f)$ 定義成這些變數的形式和， 就像你在生成函數做的事情一樣，而這些 $c_x$ 形成的形式多項式是一個向量空間 $\mathbb{Q}[c_x | x \in X]$。 以下把這個向量空間記為 $\mathbb{Q}[C]$ ## Pólya Counting Theorem statement: 給定有限群 $G$ 作用在有限群 $X$, 顏色集合 $C$ 我們有 $$p_{G,X}(C) = z_{G,X}(\sum_{c\in C}c,\sum_{c\in C}c^2,\dots,\sum_{c\in C}c^n)$$ proof sketch: 根據上一篇的 [Lemma 1](https://hackmd.io/@a93951230/r173iKXaxg#Lemma-1) 我們可以把 $p_{G,X}(C)$ 的定義改寫成易於 Lemma 2 使用的形式 (we will prove equivalence in the following)： $$p_{G,X}(C) = \sum_{O \in Map(X,C)/G}\bar{p}(O)$$ 其中 $\bar{p}(O)$ 做的事情就是從軌道 $O$ 中挑出一個 $f \in O$ 並計算回傳 $\prod_{x\in X}f(x)$ > 注意 $\bar{p}$ 是從 $Map(X,C)/G$ 打到 $C$ 的函數。也就是 > $$\bar{p} \in Map(Map(X,C)/G,C)$$ 令 $W=\mathbb Q [C]$，此時便可以使用上一篇的 [Lemma 2](https://hackmd.io/@a93951230/r173iKXaxg#Lemma-2) ::: spoiler lemma 2 敘述 假設有限 $G$ 作用在有限 $X$，且 $W$ is a vector space over $\mathbb Q$， 則 $\forall w\in Map(X,W)^G$，以及 $\bar{w}\in Map(X/G,W)$ corresponding to $w$ by lemma 1, 都有 $$\sum_{O\in X/G}\bar{w}(O) = \frac{1}{|G|}\sum_{g\in G}\sum_{x\in X^g}w(x)$$ ::: 按此得到 $$p_{G,X}(C) = \frac{1}{|G|}\sum_{g\in G}\sum_{f\in Map(X,C)^g}p(f) = \frac{1}{|G|}\sum_{g\in G}\sum_{f\in Map(X,C)^g}\prod_{x\in X}f(x)$$ --- 現在我們 Claim 一些事實，所以關於定理的等號可以被推導。 Claim $\tau$: $$p_{G,X}(C) = \sum_{O \in Map(X,C)/G}\bar{p}(O)$$ ::: spoiler proof 按照定義對於每個 $O$， $\bar{p}(O) = p(f)$ 其中 $f$ 是某個$f \in O$。 ::: Claim $\mathfrak{A}$ $$\forall g\in G, \quad\sum_{f\in Map(X,C)^g}\prod_{x\in X}f(x) = \sum_{\bar{f} \in Map(X/\langle g \rangle,C)}\prod_{O \in X/\langle g\rangle}\bar{f}(O)^{|O|}$$ ::: spoiler proof 因為$Map(X,C)^g \cong Map(X/\langle g \rangle,C)$，我們只要證明對於 $\forall f\in Map(X,C)^{g}$ 以及 $\phi(f) := \bar{f} \in Map(X/\langle g \rangle,C)$ 都有 $$\quad \prod_{x\in X}f(x) = \prod_{O\in X/\langle g \rangle}\bar{f}(O)^{|O|}$$ 如下： $$\prod_{x\in X}f(x) = \prod_{O\in X/\langle g \rangle}\prod_{x\in O}f(x) = \prod_{O\in X/\langle g \rangle}\prod_{x\in O}\bar{f}(O) = \prod_{O\in X/\langle g \rangle}\bar{f}(O)^{|O|} $$ ::: Claim $\aleph$: $$\forall g\in G, \quad\sum_{\bar{f}\in Map(X/\langle g\rangle,C)}\prod_{O\in X/\langle g\rangle}\bar{f}(O)^{|O|} = \prod_{O\in X/\langle g\rangle}\sum_{c\in C}c^{|O|}$$ ::: spoiler proof Claim $\aleph$ 也許是本定理最難理解的部分。 令 $g$ 為給定。在這邊請容我暫時讓 $|C| := \tilde{c},\,|X/\langle g \rangle| := \tilde{o}$，以及將 $\prod,\,\sum$ 下面的符號化簡 ，以避免大家看得頭痛。 化簡後，左邊變成 $\sum_{\bar{f}}\prod_{i=1}^{\tilde{o}}\bar{f}(O_i)^{|O_i|}$，而右邊變成 $\prod_{i=1}^{\tilde{o}}\sum_{j=1}^{\tilde{c}}c_j^{|O_i|}$ 首先，對於任何 $\tilde{c}$-tuple $(c_1,\dots,c_\tilde{o})\in C^{|\tilde{o}|}$，都有唯一一個 $\bar{f}$ 使得 $\bar{f}(O_i) = c_i\quad \forall i = 1,\dots,\tilde{o}$ 所以等號的左邊可以改寫成 $$ \sum_{\bar{f}}\prod_{i=1}^{\tilde{o}}\bar{f}(O_i)^{|O_i|} = \sum_{(c_1,\dots,c_\tilde{o})}\sum_{\bar{f}(O_i) = c_i} \prod_{i=1}^{\tilde{o}}c_i^{|O_i|} = \sum_{(c_1,\dots,c_\tilde{o})}\prod_{i=1}^{\tilde{o}}c_i^{|O_i|} $$ 再用到下面的 lemma 就結束了。 *Lemma:* 如果 $A,\,B \subset \mathbb R$ 是兩有限集，並且 $|A| = \alpha,\,|B| = \beta$，$A = \{a_1, \dots, a_{\alpha}\},\,B = \{b_1,\dots,b_{\beta}\}$，則有 $$\prod_{i=1}^{\alpha}\sum_{j=1}^{\beta}b_j^{a_i} = \sum_{({b'}_1,\dots,{b'}_{\alpha})\in B^{\alpha}}\prod_{i=1}^{\alpha}{b'}_i^{a_i}$$ proof sketch. 其實用一些小數字實驗，會發現這是一個挺直覺的 lemma，然證明的方法卻未必好想。 這件事情粗糙的說可以用交換律跟結合律直接解釋，但是我們還是給出一個 induction on $\alpha$ 的證明。 假設命題在更小值成立。 則有 $$\begin{aligned} \prod_{i=1}^{\alpha}\sum_{j=1}^{\beta}b_j^{a_i} &= \left(\prod_{i=1}^{\alpha-1}\sum_{j=1}^{\beta}b_j^{a_i} \right)\left(\sum_{j=1}^{\beta}b_j^{a_{\alpha}} \right) \\ &= \left(\sum_{({b'}_1,\dots,{b'}_{\alpha-1})\in B^{\alpha-1}}\prod_{i=1}^{\alpha-1}{b'}_i^{a_i} \right)\left(\color{red}{\sum_{j=1}^{\beta}b_j^{a_{\alpha}}} \right) \\ &= \sum_{({b'}_1,\dots,{b'}_{\alpha-1})\in B^{\alpha-1}}\left( \color{red}{\sum_{j=1}^{\beta}}\left(\prod_{i=1}^{\alpha-1}{b'}_i^{a_i}\right)\color{red}{b_j^{a_{\alpha}}} \\ \right) \\ &= \sum_{({b'}_1,\dots,{b'}_{\alpha})\in B^{\alpha}}\prod_{i=1}^{\alpha}{b'}_i^{a_i} \end{aligned}$$ ::: Claim $\square$: $$\forall g\in G, \quad\prod_{O\in X/\langle g\rangle}\sum_{c\in C}c^{|O|} = z_{g,x}(\sum_{c\in C}c,\sum_{c\in C}c^2,\dots,\sum_{c\in C}c^n)$$ ::: spoiler proof 依 $z_{g,X}$ 的定義計算即可。 注意我們使用的是 $z_{g,X} = \prod_{O\in X/\langle g \rangle}t_{|O|}$ 的定義。用另一種使用 $r_k(g)$ 的定義也不是不行，不過會繞遠路。 ::: --- 最後把這些 claims 組裝起來，終於得到 $$\begin{aligned} p_{G,X}(C) &= \frac{1}{|G|}\sum_{g\in G}\sum_{f\in Map(X,C)^g}\prod_{x\in X}f(x) & \text{Lemma 1 + claim }\tau\\ &= \frac{1}{|G|}\sum_{g\in G}\sum_{\bar{f} \in Map(X/\langle g \rangle,C)}\prod_{O \in X/\langle g\rangle}\bar{f}(O)^{|O|} & \text{claim }\mathfrak{A}\\ &= \frac{1}{|G|}\sum_{g\in G}\prod_{O\in X/\langle g\rangle}\sum_{c\in C}c^{|O|} & \text{claim }\aleph \\ &= \frac{1}{|G|}\sum_{g\in G}z_{g,X}(\sum_{c\in C}c,\sum_{c\in C}c^2,\dots,\sum_{c\in C}c^n) & \text{claim }\square \\ &= z_{G,X}(\sum_{c\in C}c,\sum_{c\in C}c^2,\dots,\sum_{c\in C}c^n) \end{aligned}$$ ### Remark A 如果有 $|X|=n$ 個格子要填 $|C|=k$ 個顏色，令這些顏色所代表的形式變數為 $c_1, c_2, \cdots, c_k$ 則我們按生成函數的想法知道在 $G$ 作用下，使用 $p_1$ 個 $c_1$ 顏色，$p_2$ 個 $c_2$ 顏色， ... $p_r$ 個 $c_r$ 顏色的本質不同的方法數是多項式 $p_{G,X}(C)\in \mathbb Q [C]$ 中$c_1^{p_1}\dots c_k^{p_k}$ 的係數。 因此如果不限制顏色個數的話，他就是全體單項式的係數和，也就是讓所有 $c_i = 1$ 帶入 $p_{G,X}$ 所得。 根據 Pólya enumeration theorem, 也就是 $z_{G,X}(k,k,\dots,k)$，而這跟 Remark $\alpha$ 是吻合的。 ## Appendix 下面的 C++ 代碼可以在 $O(n)$ 的時間計算 $\langle g \rangle$-orbit 的數目。 ```cpp #include <bits/stdc++.h> using namespace std; // clear an orbit void clear(vector<int>& sigma,int i) { while (sigma[i] != -1) { int inext = sigma[i]; sigma[i] = -1; i = inext; } } // cycle count int cycnt(vector<int> sigma) { int ans = 0; for (int i=0;i<sigma.size();i++) { if (sigma[i] == -1) continue; ans++; clear(sigma,i); } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << cycnt({0,1,2,3}) << '\n'; // 4 cout << cycnt({0,2,1,3}) << '\n'; // 3 cout << cycnt({3,2,1,0}) << '\n'; // 2 cout << cycnt({0}) << '\n'; // 1 return 0; } ``` 稍微改寫，我們便能在 $O(n!n)$ 的時間內計算 cyclic index $$z_{Sym_n}(t_1,\dots,t_n)$$ 方法如下。 ```cpp= #include <bits/stdc++.h> using namespace std; using ll = long long; vector<int> sigma; ostream& operator<<(ostream& l,const vector<int>& r) { for (int i=0;i<r.size();i++) l << r[i] << " \n"[i==r.size()-1]; return l; } // clear an orbit and return length of orbit int clear(vector<int>& sigma,int i) { int ans = 0; while (sigma[i] != -1) { ans++; int inext = sigma[i]; sigma[i] = -1; i = inext; } return ans; } // cycle count and cycle length count; // ans[i] = count of length i orbit of sigma vector<int> cycnt(vector<int> sigma) { vector<int> ans(sigma.size()+1); for (int i=0;i<sigma.size();i++) { if (sigma[i] == -1) continue; ans[clear(sigma,i)]++; } return ans; } int main() { cin.tie(0)->sync_with_stdio(0); // input n int n = 6; // Sym_{n} cin >> n; sigma.resize(n); map<vector<int>,int> poly; iota(sigma.begin(),sigma.begin()+n,0); do { vector<int> cyc = cycnt(sigma); poly[cyc]++; } while (next_permutation(sigma.begin(),sigma.begin()+n)); // give output ll fact = 1; for (int i=2;i<=n;i++) fact *= i; cout << "\\frac{1}{" << fact << "}\\left("; bool skipplus = true; for (auto& [cyc,coef] : poly) { if (skipplus) skipplus = false; else cout << " + "; if (coef != 1) cout << coef; for (int l=1;l<=n;l++) { if (cyc[l] == 0) continue; if (cyc[l] == 1) cout << "t_{" << l << "}"; else cout << "t_{" << l << "}^{" << cyc[l] << "}"; } } cout << "\\right)\n"; } ``` 比方說，當 $n=3$ 時，我們有 $$ z_3 := z_{Sym_{3}} = \frac{1}{6}(2t_{3} + 3t_{1}t_{2} + t_{1}^{3}) $$ $n=5$ $$ z_5 = \frac{1}{120}(24t_{5} + 20t_{2}t_{3} + 30t_{1}t_{4} + 15t_{1}t_{2}^{2} + 20t_{1}^{2}t_{3} + 10t_{1}^{3}t_{2} + t_{1}^{5}) $$ 當 $n=10$ 時，我們有 $$ \begin{aligned} z_{10} = \frac{1}{3628800}&( 362880t_{10} + 72576t_{5}^{2} + 151200t_{4}t_{6} + \\ &172800t_{3}t_{7} + 50400t_{3}^{2}t_{4} + 226800t_{2}t_{8} + 56700t_{2}t_{4}^{2} + \\ &120960t_{2}t_{3}t_{5} + 75600t_{2}^{2}t_{6} + 25200t_{2}^{2}t_{3}^{2} + 18900t_{2}^{3}t_{4} + 945t_{2}^{5} + \\ &403200t_{1}t_{9} + 181440t_{1}t_{4}t_{5} + 201600t_{1}t_{3}t_{6} + 22400t_{1}t_{3}^{3} + \\ &259200t_{1}t_{2}t_{7} + 151200t_{1}t_{2}t_{3}t_{4} + 90720t_{1}t_{2}^{2}t_{5} + 25200t_{1}t_{2}^{3}t_{3} + \\ &226800t_{1}^{2}t_{8} + 56700t_{1}^{2}t_{4}^{2} + 120960t_{1}^{2}t_{3}t_{5} + 151200t_{1}^{2}t_{2}t_{6} + \\ &50400t_{1}^{2}t_{2}t_{3}^{2} + 56700t_{1}^{2}t_{2}^{2}t_{4} + 4725t_{1}^{2}t_{2}^{4} + 86400t_{1}^{3}t_{7} + \\ &50400t_{1}^{3}t_{3}t_{4} + 60480t_{1}^{3}t_{2}t_{5} + 25200t_{1}^{3}t_{2}^{2}t_{3} + 25200t_{1}^{4}t_{6} + \\ &8400t_{1}^{4}t_{3}^{2} + 18900t_{1}^{4}t_{2}t_{4} + 3150t_{1}^{4}t_{2}^{3} + 6048t_{1}^{5}t_{5} + \\ &5040t_{1}^{5}t_{2}t_{3} + 1260t_{1}^{6}t_{4} + 630t_{1}^{6}t_{2}^{2} + 240t_{1}^{7}t_{3} + \\ &45t_{1}^{8}t_{2} + t_{1}^{10}) \end{aligned} $$ 這個需要 $5$ 秒的計算 (measured with running on background with Apple M2) 注意，當 $n=12$ 時，我們有 $$ \begin{aligned} z_{12} = \frac{1}{479001600}&(39916800t_{12} + 6652800t_{6}^{2} + 13685760t_{5}t_{7} + \\ &14968800t_{4}t_{8} + 1247400t_{4}^{3} + 17740800t_{3}t_{9} + 7983360t_{3}t_{4}t_{5} + \\ &4435200t_{3}^{2}t_{6} + 246400t_{3}^{4} + 23950080t_{2}t_{10} + 4790016t_{2}t_{5}^{2} + \\ &9979200t_{2}t_{4}t_{6} + 11404800t_{2}t_{3}t_{7} + 3326400t_{2}t_{3}^{2}t_{4} + 7484400t_{2}^{2}t_{8} + \\ &1871100t_{2}^{2}t_{4}^{2} + 3991680t_{2}^{2}t_{3}t_{5} + 1663200t_{2}^{3}t_{6} + 554400t_{2}^{3}t_{3}^{2} + \\ &311850t_{2}^{4}t_{4} + 10395t_{2}^{6} + 43545600t_{1}t_{11} + 15966720t_{1}t_{5}t_{6} + \\ &17107200t_{1}t_{4}t_{7} + 19958400t_{1}t_{3}t_{8} + 4989600t_{1}t_{3}t_{4}^{2} + 5322240t_{1}t_{3}^{2}t_{5} + \\ &26611200t_{1}t_{2}t_{9} + 11975040t_{1}t_{2}t_{4}t_{5} + 13305600t_{1}t_{2}t_{3}t_{6} + 1478400t_{1}t_{2}t_{3}^{3} + \\ &8553600t_{1}t_{2}^{2}t_{7} + 4989600t_{1}t_{2}^{2}t_{3}t_{4} + 1995840t_{1}t_{2}^{3}t_{5} + 415800t_{1}t_{2}^{4}t_{3} + \\ &23950080t_{1}^{2}t_{10} + 4790016t_{1}^{2}t_{5}^{2} + 9979200t_{1}^{2}t_{4}t_{6} + 11404800t_{1}^{2}t_{3}t_{7} + \\ &3326400t_{1}^{2}t_{3}^{2}t_{4} + 14968800t_{1}^{2}t_{2}t_{8} + 3742200t_{1}^{2}t_{2}t_{4}^{2} + 7983360t_{1}^{2}t_{2}t_{3}t_{5} + \\ &4989600t_{1}^{2}t_{2}^{2}t_{6} + 1663200t_{1}^{2}t_{2}^{2}t_{3}^{2} + 1247400t_{1}^{2}t_{2}^{3}t_{4} + 62370t_{1}^{2}t_{2}^{5} + \\ &8870400t_{1}^{3}t_{9} + 3991680t_{1}^{3}t_{4}t_{5} + 4435200t_{1}^{3}t_{3}t_{6} + 492800t_{1}^{3}t_{3}^{3} + \\ &5702400t_{1}^{3}t_{2}t_{7} + 3326400t_{1}^{3}t_{2}t_{3}t_{4} + 1995840t_{1}^{3}t_{2}^{2}t_{5} + 554400t_{1}^{3}t_{2}^{3}t_{3} + \\ &2494800t_{1}^{4}t_{8} + 623700t_{1}^{4}t_{4}^{2} + 1330560t_{1}^{4}t_{3}t_{5} + 1663200t_{1}^{4}t_{2}t_{6} + \\ &554400t_{1}^{4}t_{2}t_{3}^{2} + 623700t_{1}^{4}t_{2}^{2}t_{4} + 51975t_{1}^{4}t_{2}^{4} + 570240t_{1}^{5}t_{7} + \\ &332640t_{1}^{5}t_{3}t_{4} + 399168t_{1}^{5}t_{2}t_{5} + 166320t_{1}^{5}t_{2}^{2}t_{3} + 110880t_{1}^{6}t_{6} + \\ &36960t_{1}^{6}t_{3}^{2} + 83160t_{1}^{6}t_{2}t_{4} + 13860t_{1}^{6}t_{2}^{3} + 19008t_{1}^{7}t_{5} + \\ &15840t_{1}^{7}t_{2}t_{3} + 2970t_{1}^{8}t_{4} + 1485t_{1}^{8}t_{2}^{2} + 440t_{1}^{9}t_{3} + \\ &66t_{1}^{10}t_{2} + t_{1}^{12}) \end{aligned} $$ 計算需要 $877$ 秒 (14分鐘多)