Ок умница

Меня давно тревожил вопрос про комбинаторику, лишь то, сколько комбинаций можно составить из определенных чисел. Ну например узнать, сколько реприз можно составить из фразы «ты тупой конченый лох», ведь можно еще:
лох тупой конченый ты
ты конченый тупой лох
ты лох конченый тупой
лох конченый тупой ты

и т.д. Но вопрос меня такой мучит в основном только когда я далеко от википедии, компа или вообще чего-нибудь, с помочью чего об этом можно сразу узнать, но, как и полагается, я забываю об этом сходу. Но вот вчера! Не было света, и я мигом вспомнил про репризы и стал лепить умняка: записывал комбинации на листочек и искал зависимости. Например из двух чисел, неповторяющаяся комбинация без повторения этих же чисел, есть только две комбинации: 12 и 21, а из трех (123): шесть! (123 312 132 321 213 231), ну а дальше еще больше: двадцать четыре

Нарисовал я, значится, таблицу из комбинаций до 4-го колена и стал искать закономерности. Например нашел, что 6 — это 2³-2, или же 3² – 3, или 2²+2, для 4-го колена(24 комбинации) подходит 3³-3 (3³=27). Я еще смешно обводил всякие группы, находил закономерности в некоторых группах, например самая простая перестановка это в 2 колена: 12 и 21, в 3-м колене уже есть закономерность, на каждую первую цифру есть по два колена: 123, 132; 213, 231; 312, 321. В 4-м уже на каждую цифру есть по шесть групп по два колена, то есть по одной группе из 3-го колена, и так далее. И вот сижу я с этими обведенными, почти доказал теорему Ферма, и понимаю, что нужна мне для конечной формулы некая фигня, которая действует как сумма(Σ), но только умножает, а не суммирует. Как раз вовремя появились роднюни в хате, и я стал расспрашивать, помнит ли кто, существует ли такой знак такой операции, конечно же, все помнили и знали, и одобрительно кивали, приговаривая «не помню, не знаю». Загрустила моя сущность и приступила к туплению в листик с данными. Стал я смотреть на числа «1, 2, 6, 24" и вдруг заметил, что 2 больше единицы в 2 раза, а 6 больше двойки в 3 раза! А 24 больше шестерки в 4 раза. И тут меня осенило, что я тупая мокрица: это же факториал! То есть, что бы посчитать количество комбинаций знаков (что б знаки не повторялись), нужно всего лишь факториал вывести из количества знаков! То есть 4! = 24, 5! = 120, да-да! всего 120 комбинаций с вариантами 12345, 13245 и т.д!

Но этого мне оказалось мало, я еще решил повелосипедничать и посчитать количество комбинаций с повторениями символов, то есть из числа “12” можно вывести 4 комбинации: 11,12,21,22. Тоже без группочек не обошлось, там заметно больше записывать пришлось, и дважды я не то записывал, какие-то 1,8,1024; 1,4,27,256. Не знаю что я во что возводил, но когда включили свет, я написал (ыхыхыхыхыхых) небольшой скрипт, который тупо перебирал числа и показывал мне количество итераций, потому как очень много писать на листике приходилось, в общем, выяснилось, что в пятом колене 3125 комбинаций! Но тут я прохавал быстрее: чтобы посчитать количество итераций, нужно посчитать количество символов в заданном числе и возвести это число в такую же степень

Итак, повторим наш урок от мистера Математика:

Количество реприз без повторения символов (12,21): n!
Количество реприз с повторением символов (11,12,21,22): nⁿ

Jan. 27, 2010 // 17:23