主題
Search

迴圈指標


j_k(alpha) 表示置換 permutation alpha 表示為不相交迴圈的乘積時,長度為 k 的迴圈的數量。階數為 m=|X|,次數為 dpermutation group X 的迴圈指標 Z(X) 是一個關於 d 個變數 x_1, x_2, ..., x_d 的多項式,由以下公式給出

 Z(X)=1/(|X|)sum_(alpha in X)product_(k=1)^dx_k^(j_k(alpha)).
(1)

permutation group X 的迴圈指標實現為CycleIndexPolynomial[perm, {x1, ..., xn}],它返回一個關於 x_i 的多項式。對於任何 permutation alpha,數字 j_k=j_k(alpha) 滿足

 1j_1+2j_2+...+dj_d=d,
(2)

因此構成整數 d 的一個 partition。值集 j_k 通常表示為 j_i=(j_1,...,j_d)_i,其中 i 遍歷所有滿足方程 (2) 的 d-vectors

最重要置換群(symmetric group S_palternating group A_pcyclic group C_pdihedral group D_ptrivial group E_p)的公式由以下給出

Z(S_p)=1/(p!)sum_((j))(p!)/(product_(k=1)^(p)k^(j_k)j_k!)a_1^(j_1)a_2^(j_2)...a_p^(j_p)
(3)
Z(A_p)=1/(p!)sum_((j))(p![1+(-1)^(j_2+j_4+...)])/(product_(k=1)^(p)k^(j_k)j_k!)a_1^(j_1)a_2^(j_2)...a_p^(j_p)
(4)
Z(C_p)=1/psum_(k|p)phi(k)a_k^(p/k)
(5)
Z(D_p)=1/2Z(C_p)+{1/2a_1a_2^((p-1)/2) for p odd; 1/4(a_2^(p/2)+a_1^2a_2^((p-2)/2)) for p even
(6)
Z(E_p)=a_1^p,
(7)

其中 k|p 表示 p 可以被 k 整除,而 phi(k)尤拉函式(Harary 1994,第 184 頁)。


另請參閱

Alternating Group, Cycle Graph, Cycle Polynomial, Permutation Cycle, Cyclic Group, Dihedral Group, Permutation Group, Pólya Enumeration Theorem, Simple Graph, Symmetric Group, Symmetric Polynomial

使用 探索

WolframAlpha

更多嘗試

參考文獻

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 第 181 和 184 頁,1994年。

在 中被引用

迴圈指標

請引用為

Weisstein, Eric W. “迴圈指標。” 來自 Web 資源。 https://mathworld.tw/CycleIndex.html

學科分類