Как найти количество вариантов заполнения латинского квадрата?

Question

[user111222]

Латинский квадрат - квадрат N×N, в каждой клетке которого стоит число от 1 до N так, что выполняются следующие условия: в каждой строке и столбце каждая цифра встречается один раз.

На вход подается квадратная матрица, в некоторых клетках заполнены числа. Нужно определить, сколькими способами можно дозаполнить матрицу таким образом, чтобы выполнялось условие латинского квадрата.

Comments

[Владимир Олохтонов]

Из близкого - задача о беспорядках https://ru.m.wikipedia.org/wiki/%D0%91%D0%B5%D1%81...

Answer 1

[Владимир Олохтонов]

Кажется похоже на правду получилось:
Число перестановок первой строки * число перестановок строк со второй по n.

n! * (n-1)!

Доказательство корректности: поскольку нам требуется составить n строк таким образом, что каждый из столбцов имеет ровно по 1 вхождению каждого из чисел, то справедливо рассматривать строки как циклы длины n. Рассмотрим всевозможные перестановки первой строки, их n!, для каждой из перестановок построим n циклов, это можно сделать 1 способом, зафиксируем положение первой строки, остальные перемешаем всевозможными способами, их (n-1)!, итого n!*(n-1)! вариантов. Дублей среди них нет, поскольку первая строка уникальна. В каждой строке все числа, поскольку это циклы, в каждом столбце тоже все числа, поскольку каждая строка - одна из всевозможных циклических перестановок.