Факториал (математика №1)

Началось все, как водится, с удивления чужому поведению. У нас тут в Вайбере (будь он проклят) есть чат на 200 человек, которые живут в Нячанге. Люди иногда постоянно развлекают себя флудом, и вот, кто-то кидает в качестве шутки примерно такое сообщение:

Ну все загудели конечно, – «Да ты что, да чему тебя в школе учили, да иди на калькуляторе проверь». Началось жуткое бурление говн, потому что гуманитарии вообще не в курсе, что математики трогают своими ручонками их восклицательный знак. Потом, конечно, кто-то написал, что 4!=24, но и это оставило половину участников чата за бортом понимания.

Итак, встречайте: факториал!

Сегодня именно о нем пойдет речь. Суть факториальной функции проста, как три копейки. Кстати, если у вас три копейки, то 3! (читается, как «три факториал») равно 6, а именно 1 х 2 х 3 = 6. Дальше – только больше вплоть до самого n.

То есть, n! это произведение всех натуральных чисел от 1 до этого самого n. Используется факториал в самых богатых на разрывы шаблона областях математики: в комбинаторике и теории чисел, ну и в остальном более скучном матане, коненчно.

Поговорим про лотерею

Попользовавшись немного знаниями о факториалах, мы легко раз и навсегда разберемся, как работают вероятности в «задачах с перебором», таких как лотерея. Например нам предлагается угадать 6 чисел из 36. Сколько же тут вариантов?

Когда мы выбираем первое число, у нас есть 36 вариантов. Когда мы выбираем второе число, у нас одно «уже занято», и вариантов осталось только 35, для третьего – 34 и так далее.

Итого, общее число комбинаций по 6 чисел из 36 равно:

36 х 35 х 34 х 33 х 32 х 31

Но в условиях лотереи нам не важно, в каком порядке стоят числа, то есть если мы выбрали числа от 1 до 6, то они могут стоять в любом порядке. Значит из общего количества вариантов нам нужно убрать все «одинаковые» наборы. Поступим ровно таким же способом, если у нас есть какие-то 6 чисел, которыми нужно заполнить 6 позиций, то при выборе первого у нас 6 вариантов, при выборе второго – 5 (одно из чисел мы уже выбрали как первое) и так далее. Для последней, шестой, позиции у нас останется только один незанятый вариант. То есть получается, что общее число повторов для каждых конкретных шести чисел будет равно:

6 х 5 х 4 х 3 х 2 х 1 = 6!

Из общего числа вариантов убираем повторы с помощью деления.

Получается 1 947 792. То есть шанс угадать, чуть лучше, чем 1 из 2 миллионов. Какие события происходят с такой регулярностью? Например, по самым скромным оценкам, в год погибают 6000 человек (из 7 миллиардов) от удара молнией, а это почти вдвое чаще, чем угадывание шести цифр из шести. То есть в принципе, до тех пор пока вы сорвете джекпот, вас убьет молнией дважды (шутка).

Перейдем к игральным картам

В колоде 52 карты. Если они есть у вас под рукой, то, чтобы прочувствовать момент, не поленитесь их достать. Перемешайте колоду и теперь – внимание! У вас в руках находится колода с такой последовательностью карт, которой никогда не было ни у кого за все время существования игры. Вероятность этого настолько велика, что я зуб даю!

Насколько же много комбинаций из 52 карт может существовать? Вы уже догадались, что записать это очень просто: 52!. Это, конечно даже не близко к числу Грэма, например, но за то это можно попробовать представить. Итак, 52! равно:

Если отбросить «мелочь» после запятой, то примерно 8 умножить на 10 в 67-й степени, неплохо.

Переведу небольшой кусочек великолепного объяснения масштаба бедствия, описанного Скоттом Чепилем (Scott Czepiel) вот тут. Скотт предлагает следующий мысленный эксперимент:

Нужно взять таймер, заведенный на 52! секунд, запустить его, встав в любое место на экваторе и… подождать миллиард лет. Затем сделать шаг и подождать еще миллиард лет, потом еще один и так далее. После того, как вы вернетесь в ту же точку (даже если вы плоскоземец!), возьмите одну каплю воды из Тихого океана и куда-нибудь перелейте. И так на каждом следующем круге вдоль экватора забирайте по капле.

Через какое-то время вы вычерпаете Тихий океан до дна. В этот момент положите рядом с собой лист бумаги, налейте океан обратно, подождите миллиард лет и сделайте шаг, подождите…

В итоге, вы будете добавлять один лист бумаги, каждый раз, когда океан заканчивается. Не останавливайтесь, пока стопка не вырастет на расстояние от Земли до Солнца. Если теперь вы взглянете на показания таймера, то окажется, что три самые левые цифры в числе оставшихся секунд даже не изменились!

Of course, in reality none of this could ever happen. Sorry to break it to you. The truth is, the Pacific Ocean will boil off as the Sun becomes a red giant before you could even take your fifth step in your first trek around the world.

«Конечно, на самом деле ничего такого не может случиться. Простите, что вывалил это на вас. Правда в том, что Тихий океан закипит, когда Солнце станет красным гигантом, прежде чем вы сможете даже сделать свой пятый шаг в первой кругосветке.»

В качестве постскриптума

Внимательный читатель мог заметить некоторую странность, почему, при расчете факториала, умножать мы начинаем не с нуля, а с единицы. Во-первых так очень скучно, а во вторых само определение факториала говорит о числах натуральных. Но в то же время, математики договорились, что 0! = 1. Понять это можно из комбинаторики. Если у вас есть n чего-то, то вы можете расставить это n! способами. А если у вас ни черта нету, то на самом деле у вас есть один единственный, способ расставить это «ничерта». Мяу!