数学问题：不同排列的数量
这更像是一个数学问题，而不是编程问题，但我认为这里很多人都非常擅长数学！ :)
我的问题是：给定一个 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 个相同的数字，则此方法不起作用。
我已经有一段时间没有研究这些东西了，我想不出一种方法来解决它，我很感激任何人可以提供的帮助。
This is more of a maths question than programming but I figure a lot of people here are pretty good at maths! :)
My question is: Given a 9 x 9 grid (81 cells) that must contain the numbers 1 to 9 each exactly 9 times, how many different grids can be produced. The order of the numbers doesn't matter, for example the first row could contain nine 1's etc. This is related to Sudoku and we know the number of valid Sudoku grids is 6.67×10^21, so since my problem isn't constrained like Sudoku by having to have each of the 9 numbers in each row, column and box then the answer should be greater than 6.67×10^21.
My first thought was that the answer is 81! however on further reflection this assumes that the 81 numbers possible for each cell are different, distinct number. They are not, there are 81 possible numbers for each cell but only 9 possible different numbers.
My next thought was then that each of the cells in the first row can be any number between 1 and 9. If by chance the first row happened to be all the same number, say all 1s, then each cell in the second row could only have 8 possibilites, 2-9. If this continued down until the last row then number of different permutations could be calculated by 9^2 * 8^2 * 7^2 ..... * 1^2. However this doesn't work if each row doesn't contain 9 of the same number.
It's been quite a while since I studied this stuff and I can't think of a way to work it out, I'd appreciate any help anyone can offer.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
想象一下，拿 81 张空白纸条，并在每张纸条上写下 1 到 9 的数字（每个数字 9 个）。洗牌，然后开始将牌放在 9x9 网格上。
你可以创造 81 个！如果您认为每张纸条都是独一无二的，则可以使用不同的图案。
但相反，您希望将所有 1 视为等效。
对于任何特定配置，该配置将重复多少次
因为 1 全部相等？答案是 9！，九张写有 1 的纸条可以有多少种排列顺序。
这样排列总数就减少到 81!/9!。 （除以无法区分的排列的数量。想象一下只有 2 个无法区分的排列，而不是 9 个！无法区分的排列。您可以将计数除以 2，对吗？所以规则是，除以无法区分的排列的数量。）
啊，但是您还希望 2 相等，3 相等，依此类推。
排列数量
出于同样的原因，这减少了斯特林近似的 ，即大约为 5.8 * 10^70。
Imagine taking 81 blank slips of paper and writing a number from 1 to 9 on each slip (nine of each number). Shuffle the deck, and start placing the slips on the 9x9 grid.
You'd be able to create 81! different patterns if you considered each slip to be unique.
But instead you want to consider all the 1's to be equivalent.
For any particular configuration, how many times will that configuration be repeated
due to the 1's all being equivalent? The answer is 9!, the number of ways you can permute the nine slips with 1 written on them.
So that cuts the total number of permutations down to 81!/9!. (You divide by the number of indistinguishable permutations. Instead of 9! indistinguishable permutations, imagine there were just 2 indistinguishable permutations. You would divide the count by 2, right? So the rule is, you divide by the number of indistinguishable permutations.)
Ah, but you also want the 2's to be equivalent, and the 3's, and so forth.
By the same reasoning, that cuts down the number of permutations to
By Stirling's approximation, that is roughly 5.8 * 10^70.
首先，我们从 1 到 81 的 81 个数字开始。其排列数为
81P81或81!。够简单的。然而，我们有九个
1，它们可以排列成9!无法区分的排列。与2、3等相同。所以我们得到的是棋盘排列的总数除以所有数字的所有不可区分的排列，即
81！ /（9！** 9）。First, let's start with 81 numbers, 1 through 81. The number of permutations for that is
81P81, or81!. Simple enough.However, we have nine
1s, which can be arranged in9!indistinguishable permutations. Same with2,3, etc.So what we have is the total number of board permutations divided by all the indistinguishable permutations of all numbers, or
81! / (9! ** 9).