Пятнашки

[e7e5]

Уважаемые участники форума!
Интересует следующее в игре в "Пятнашки":
1) Известно, что решение возможно, когда исходная позиция содержит четную перестановку (число инверсий четно); число решаемых позиций $15!/2$.
Можно построить таблицу для $N=15$ элеметов, в которой в строке записываем число перестановок, имеющих определенное число $m$ инверсий (число инверсий $0,1,2,3,...$ разместим в названии каждого столбика).
Находим, вероятность $P_m(N)$, что число инверсий равно $m$. Строим график. Исключаем случаи нечетных инверсий (т.к. не существует решения позиции).

2) В учебнике Феллера по теории вероятности, утверждается, что для перестановок с большим числом элементов $N$ распределение инверсий будет подчиняться нормальному закону.

3) Используя асимптотическое разложение ЦПТ, находим функцию распределения для конечного числа $N$ с требуемой точностью.
Как теперь учесть только четные перестановки, которые дают позиции, имеющие решения?

[provincialka]

e7e5 в сообщении #1364443 писал(а):

Как теперь учесть только четные перестановки, которые дают позиции, имеющие решения?

А для чего учесть? Задача-то какая?

[e7e5]

Для легальных позиций построить функцию распределения инверсий, используя асимптотическое разложение ЦПТ для конечного числа элементов. Формула есть для всех позиций, но только половина из них имеет решение.