---
# System prepended metadata

title: Way to Pólya Counting Theory

---

# 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分鐘多)