Вопрос по математике: количество различных перестановок

Question

Это больше вопрос математики, чем программирование, но я думаю, что многие здесь очень хорошо разбираются в математике! :)

Мой вопрос: учитывая сетку 9 x 9 (81 ячейка), которая должна содержать числа от 1 до 9, каждое ровно 9 раз, сколько разных сеток может быть создано. Порядок чисел не имеет значения, например, первая строка может содержать девять единиц и т. Д. Это связано с судоку, и мы знаем, что число допустимых сеток Судоку составляет 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 !, количество способов, которыми вы можете переставить девять бланков с 1 написанным на них.

Таким образом, общее количество перестановок сокращается до 81! / 9 !. (Вы делите на число неразличимых перестановок. Вместо 9! Неразличимых перестановок представьте, что было только 2 неразличимых перестановки. Вы бы поделили счет на 2, верно? Так что правило состоит в том, что вы делите на количество неразличимых перестановок.)

Ах, но вы также хотите, чтобы 2 были эквивалентны, а 3 и так далее. По тем же соображениям это сокращает количество перестановок до

81!/(9!)^9 

По приближению Стирлинга , что примерно равно 5,8 * 10 ^ 70.

Answer 2

Во-первых, давайте начнем с 81 числа, от 1 до 81. Количество перестановок для этого составляет 81P81 или 81!. Достаточно просто.

Однако у нас есть девять 1 с, которые можно упорядочить в 9! неразличимых перестановок. То же самое с 2, 3 и т. Д.

Итак, мы имеем общее количество перестановок на доске, деленное на все неразличимые перестановки всех чисел, или 81! / (9! ** 9).

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