數學問題：不同排列的數量

Question

這比編程更像一個數學問題，但我認爲很多人在這裏都很擅長數學！ :)

我的問題是：給定一個9×9的網格（81個單元格），它必須包含數字1到9，每個正好9次，可以生成多少個不同的網格。數字的順序並不重要，例如第一行可以包含九個1等。這與數獨有關，並且我們知道有效的數獨網格的數量是6.67×10^21，因爲我的問題沒有受到限制就像Sudoku一樣，每個行，每列和每個盒子中的9個數字都應該大於6.67×10^21。

我的第一個想法是，答案是81！然而在進一步的反思中，假定每個單元可能的81個數字是不同的，不同的數字。他們不是，每個單元有81個可能的數字，但只有9個可能的不同的數字。

我的下一個想法是，第一行中的每個單元格可以是1到9之間的任何數字。如果碰巧第一行碰巧是全部相同的數字，比如全部是1，那麼每個單元格第二排只能有8個可能，2-9。如果這繼續下去直到最後一行，則可以通過9^2 * 8^2 * 7^2 ..... * 1^2來計算不同排列的數量。但是，如果每行不包含9個相同數字，則這不起作用。

自從我研究這些東西已經有一段時間了，我想不出一種方法來解決問題，我會很感激任何人都可以提供的幫助。

Answer 1

想象一下，在每張單據上（每個數字中有9個），記錄81張空白單據和1到9的數字。洗牌，並開始將滑道放在9x9網格上。

你可以創建81！不同的模式，如果你認爲每一個滑動是獨特的。

但相反，你要考慮所有的1是等價的。

對於任何特定的配置，由於1的全部等效配置，該配置將重複多少次 ？答案是9！，可以排列9個單據的方式的數量，其中1個寫在單據上。

這樣可以將排列的總數減少到81！/ 9 !. （除以不可區分的排列的數量，而不是9！不可區分的排列，假設只有2個不可區分的排列，您可以將計數除以2，對嗎？所以規則是，除以不可區分排列的數量。

啊，但你也希望2的等價物和3的等等。 通過同樣的道理，即減少了置換到

81!/(9!)^9 

數通過Stirling's approximation，也就是大約5.8 * 10^70。

Answer 2

首先，讓我們從81個數字開始，1到81.排列的數量是81P81或81!。夠簡單。

但是，我們有九個1 s，可以排列在9!不可區分的排列。與2,3等相同

所以我們有什麼是板排列的總數除以所有數字的所有不可區分的排列或81!/(9! ** 9)。

>>> reduce(operator.mul, range(1,82))/(reduce(operator.mul, range(1, 10))**9) 
53130688706387569792052442448845648519471103327391407016237760000000000L