ПЕРЕСТАНОВКИ
Теория. (Для понимания природы вещей.)
ПЕРЕСТАНОВКИ
Здесь мы хотим рассмотреть вопрос о числе способов расположения
n различных объектов какой-то группы.
Расположение
n различных объектов в заданном
порядке называется перестановкой этих
n объектов.
Сначала рассмотрим случай, когда имеется три объекта a, b и с. Возможные
перестановки этих трех объектов можно представить в виде путей на дереве, как
это показано на рисунке
Каждый путь изображает одну возможную перестановку, и всего таких путей шесть.
Мы можем также перечислить эти перестановки:
abc, bса, acb, cab, bac, cba.
Построив такое дерево для n Фиг. 76
объектов, мы бы нашли, что для получения общего числа путей надо перемножить числа
n, n — 1,
n — 2 и т. д. до
числа 1. Число, получаемое таким образом, встречается столь часто, что
заслуживает специального обозначения: его записывают символом
n!, который
читается «n факториал».
Например, 3! = 3 • 2 • 1 =6, 4! = 4 • 3 • 2 • 1 = 24 и
т. д. По причинам, которые станут ясны позднее (см. упр. 2 и
9 из § 5), мы полагаем 0! = 1. Таким образом, имеется
n! различных перестановок
и отличимых один от другого объектов.
Пример 1. Предположим, что мы имеем семь карточек, на каждой из которых написана
одна буква, и мы хотим с их помощью образовать все слова из семи букв. Если эти
семь букв все различны, то мы должны рассмотреть 7! = 5040 разных «слов»
(большинство из которых, разумеется, будут бессмысленными).
Пример 2. Вратарь десять раз выбрасывает мяч в игру. Предположим, что тренер
рекомендовал ему подавать мяч каждый раз другому игроку своей команды. Сколько
возможных вариантов может выбрать вратарь? Поскольку v— футбольная команда
состоит из 11 игроков (т. е., помимо
вратаря, имеется еще 10 игроков команды), то вратарь может выбрать любой из 101
= 3628800 порядков выбрасывания мяча.
Пример 3. Сколькими способами могут расположиться за круглым столом п человек?
При такой постановке вопроса обычно подразумевается, что два расположения
считаются различными тогда и только тогда, когда в этих двух случаях хоть один
из сидящих за столом людей имеет с какой-либо стороны (например, слева от себя)
разных соседей. Зафиксируем положение одного человека. Тогда остальные могут
расположиться (n— 1)! способами. Теперь мы учли все расположения, которые
считаются различными. Почему?
Общий принцип. Существует много комбинаторных задач, в которых невозможно
указать простую формулу для числа допускаемых задачей логических возможностей.
Во многих из таких задач единственный способ подсчета числа возможностей состоит
в построении соответствующего дерева (см. упр. 4). В некоторых задачах
оказывается полезным следующий общий принцип:
Пусть некоторый выбор может быть
сделан в точности r различными способами; для каждого из этих способов некоторый
второй выбор может быть сделан в точности s различными способами; для каждой
пары первых двух выборов некоторый третий выбор может быть сделан в точности t
способами и т. д. Тогда число способов для последовательности этих выборов
получается перемножением соответствующих чисел, т. е. равно r-s-t....
Справедливость этого общего принципа можно проверить, представив себе дерево
всех возможных способов, какими может быть сделана данная последовательность
выборов. Из начального положения должно отходить r ветвей. От каждой такой ветви
должно отходить s новых ветвей, от каждой из них t ветвей, и т. д. Число путей на этом дереве равно произведению) г
* s*t... .
«Математическое доказательство представляет собой не
просто какое-то нагромождение силлогизмов: это силлогизмы, р а с п о л о ж е н н
ы е в известном порядке, причем этот порядок
расположения элементов оказывается гораздо более важным, чем сами элементы.
Если я обладаю чуиством, так сказать, интуицией этого порядка, так- что могу
обозреть одним взглядом все рассуждение к целом, то мне но приходится опасаться,
что я забуду какой-нибудь один из элементов: каждый из них займет назначенное
ему место без всякого усилия с моей стороны» ''.
Пуанкаре А.О. О науке С.311
Предложениями и замечаниями обращаться по адресу- vova1001@yandex.ru
