可重圓排列問題的方案數？

問題來自於許胤龍《組合數學引論》第二版第四章習題23。事先聲明，這不是作業，老師也說這道題很麻煩不會留作業更不會考。但我就是想知道下面這個公式怎麼證，自己摳了6h沒摳出來，所以想尋求各路知友大神的幫助。

為了讓知友們不必翻箱倒櫃找教材，我把公式的背景簡單敘述一遍：

問題：求集合S={1..m}的長度為n的可重圓排列的方案數。集合S的每個元素可以取無限多次。

設{a[1]..a[n]}是一個長度為n的不可重圓排列，將其分別從n個位置斷開，即可得到與之相應的n個不同的線排列。

然而，一個長度為n的可重圓排列在n個位置斷開後形成的n個線排列則未必互異。例如，當n能被d整除時，由不重複的{a[1]..a[d]}重複n/d次構成圓排列，再從n個位置斷開後只能形成d個不同的線排列。（#1）

如果一個圓排列可以由長度為k的線排列重複若干次形成，則這樣的k的最小值稱為圓排列的周期。一個圓排列中元素的個數（計重複）稱為它的長度。

設由集合S中的元素形成的長度與周期都是c的圓排列的個數為M(c)。結合論據（#1）來考慮，若n能被c整除,則周期為c的全部n可重圓排列對應的n可重線排列的總數為cM(c)。

對所有可能的周期求和，得

等號右邊的pow(m,n)代表S的n可重線排列數。對上式應用Mobius反演可得

設T(n)為集合S的長度為n的可重圓排列數，則

問：如何將T(n)化簡為

好吧，沒人來，我自問自答了。我記錄這些內容，不僅僅是為了記錄這個證明本身，而是想從裡面提煉一些解決數學問題的方法論，在面對其他問題時不至於寸步難行。

首先要知道的是，Euler函數可以分解成Mobius函數的和，這種分解又叫Divisor Sum。它的證明方法在很多組合數學教材上都有，這裡直接給結論：

回到正題，證明

# 1. 評估難度，選擇方向

首先根據Dirichlet product的性質，把等號左邊變成

這一步的目的是什麼呢？因為 太初等了，只會越化越繁，不能再化簡了，而 是可以化簡的。

# 2. 偷梁換柱（非常關鍵）

然後設 ，以及 為 的質因數的集合。考慮如下過程：

1) 從 中取 個元素相乘得到 ；

上述過程等價於

1) 從 中直接取 個質因數相乘得到 ；

因此有

經過這樣的偷梁換柱，內層求和就簡單多了。

# 3. 配湊係數，使用Divisor sum

這一步就是套公式、配係數，不解釋了直接上過程：

證畢。