Совершенно недавно мы столкнулись с очень интересной задачей.

Сидели мы и рассуждали, что информатикам не нужно запоминать решения диффуров, а математика все методы сортировки. Так и возникло воспоминанине у одного из нас, что однажды было задание по программирование - рассказать группой про один из методов сортировки. Вот и проспал один из студентов все, в результате чего пришел к преподу с этой проблемой. "Меня никто не берет в группу, потому что уже все у всех сделано", - говорит студен. Препод подумал-подумал и дал ему в задание рассказать про "болотную" сортировку.

Суть болотоной сортировки заключается в том, что у нас имеется массив чисел, в котором мы каждый шаг проверяем, не отсортирован ли он, а затем, в случае неупорядоченности, меняем два случайных элемента местами. Возможно вы уже слышали о нем, он так же имеет название Bogo-sort.

И вот отсюда один зажегся и начал писать эту сортировку, а другой - с помощью графов искать вероятность того,  что мы прийдем к отсортированному массиву. Спустя некоторое время и несколько ошибок, мы все таки пришли к тому, что для 3х элементов массива шанс для n, стремящегося к бесконечности, шагов равняется 1.

Меня же эта идея очень заинтересовала. На следующий день я построил граф для 4х элементов массива, чтобы понять закономерность. А дальше попал в тупик. Я - ранее был студентом факультета математики и информатики, однако отчислился, хотя даже не жалею, ведь был не на той специальности, на которой хотел, да и пропустил уже много к тому моменту и не мог продолжать учиться. Однако математика - единственное, что заставляет меня выпасть из жизни и размышлять над задачами, пока летят часы.

Вот и задача - рассчитать формулу вероятности получения отсортированного массива для n элементов. Я с радостью буду заниматься этим параллельно, однако дается мне это тяжко, в силу незнания многих "приемов" для решения комбинаторных задач.

Так же я прикрепляю нарисованный мною граф для 4х элементов, возможно он поможет вам в решении.