Примирил всех официант, обратившийся к ним с такой речью:
– Молодые друзья мои, оставьте ваши пререкания. Сядьте за стол, как кому придется, и выслушайте меня.
Все сели как попало. Официант продолжал:
– Пусть один из вас запишет, в каком порядке вы сейчас сидите. Завтра вы снова явитесь сюда пообедать и разместитесь уже в ином порядке. Послезавтра опять сядете по-новому и т. д., пока не перепробуете всех возможных размещений. Когда же придет черед вновь сесть так, как вы сидите здесь сегодня, тогда – обещаю торжественно – я угощу вас всех бесплатно самым изысканным обедом!
Предложение понравилось. Решено было ежедневно собираться в этом ресторане и перепробовать все способы размещения за столом, чтобы поскорее воспользоваться бесплатным обедом.
Однако им не пришлось дождаться этого дня. И вовсе не потому, что официант не исполнил обещания, а потому, что число всех возможных размещений за столом чересчур велико. Оно равняется ни мало ни много – 3628800.
Такое число дней составляет, как нетрудно сосчитать, 9942 года (без малого), т. е. почти 10000 лет. Слишком долгий срок ожидания одного бесплатного обеда…
II
Может быть, вам кажется невероятным, чтобы 10 человек могли размещаться таким большим числом различных способов? В таком случае проверьте этот расчет сами. Но раньше надо научиться определять число перестановок. Для простоты начнем вычисление с небольшого числа предметов – с трех. Назовем их А, Б и В.
Мы желаем узнать, сколькими способами возможно переставлять их один на место другого. Рассуждаем так. Если отложить пока в сторону вещь В, то остальные две можно разместить только двумя способами:
Теперь будем присоединять вещь В к каждой из этих пар. Мы можем сделать это трояко:
1) поместить В п о з а д и пары,
2) поместить В в п е р е д и пары,
3) поместить В м е ж д у вещами пары.
Других положений для вещи В, кроме этих трех, очевидно, быть не может. А так как у нас две пары, АБ и БА, то всех способов разместить вещи у нас имеется 2 x 3 = 6. Способы эти следующие:
Теперь пойдем дальше – сделаем расчет для 4 вещей. Пусть у нас 4 вещи: А, Б, В и Г. Опять отложим пока в сторону одну вещь, например Г; а с остальными тремя вещами сделаем все возможные перестановки. Мы уже знаем, что число этих перестановок – 6. Сколькими же способами можно присоединить четвертую вещь Г к каждой из 6 троек? Очевидно, четырьмя:
1) поместить Г п о з а д и тройки;
2) поместить Г в п е р е д и тройки;
