Maths Question: number of different permutations

Question

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.

Answer 1

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

81!/(9!)^9 

By Stirling's approximation, that is roughly 5.8 * 10^70.

Answer 2

First, let's start with 81 numbers, 1 through 81. The number of permutations for that is 81P81, or 81!. Simple enough.

However, we have nine 1s, which can be arranged in 9! indistinguishable permutations. Same with 2, 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).

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