数学问题 : number of different permutations

Question

这与其说是编程问题，不如说是数学问题，但我认为这里的很多人都非常擅长数学! :)

我的问题是:给定一个 9 x 9 的网格(81 个单元格)，其中必须包含数字 1 到 9，每个数字恰好出现 9 次，可以生成多少个不同的网格。数字的顺序无关紧要，例如第一行可以包含九个 1 等。这与数独有关，我们知道有效数独网格的数量是 6.67×10^21，所以由于我的问题不受约束像数独游戏一样，每行、每列和每个方框都必须有 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

想象一下，拿 81 张空白纸条并在每张纸条上写下 1 到 9 的数字(每个数字九个)。洗牌，然后开始将纸条放在 9x9 网格上。

你可以创造 81!如果您认为每张纸条都是独一无二的，则可以使用不同的图案。

但相反，您想将所有 1 都视为等价的。

对于任何特定配置，该配置将重复多少次由于 1 都是等价的？答案是 9!，即您可以将 9 张纸条上写有 1 的排列方式的数量。

这样一来，排列总数就减少到了 81!/9!。 (你除以不可区分排列的数量。假设只有 2 个不可区分排列，而不是 9!不可区分排列。你会将计数除以 2，对吗？所以规则是，你除以不可区分排列的数量。)

啊，但是您还希望 2 和 3 等价，等等。通过同样的推理，将排列的数量减少到

81!/(9!)^9 

通过 Stirling's approximation ，大约是 5.8 * 10^70。