Перестановки, размещения, сочетания

Характерная примета в задачах из области комбинаторики – вопрос в них обычно можно сформулировать так, чтобы он начинался со слов: «Сколькими способами...».

Первые задачи такого типа встречались уже, например, в древней и средневековой Индии.

«О друг, назови число различных ожерелий, которые можно получить из бриллиантов, сапфиров, изумрудов, кораллов и жемчугов» (Махавира, IX в.). Условие этой задачи, возможно, не очень понятно; судя по решению, здесь речь идет об ожерельях, которые бы отличались не по количеству или расположению камней одного и того же типа, а по наличию тех или иных камней – например, ожерелье из бриллиантов, из бриллиантов и кораллов, из бриллиантов, изумрудов и жемчугов и т. д.

Решение

«Повар готовит различные блюда с шестью вкусовыми оттенками: острым, горьким, вяжущим, кислым, соленым, сладким. Друг, скажи, каково число всех разновидностей» (Шридхара, IX–X вв.).

Решение

Классическими понятиями комбинаторики являются перестановки, размещения и сочетания.

Перестановкой называется какой-либо способ упорядочения данного множества. Чтобы найти число всех перестановок множества из n предметов (это число обозначается Pn, от французского permutation – перестановка) – например, число способов, которыми можно расставить n томов на книжной полке, – обычно рассуждают таким образом. Первым можно поставить любой из n предметов, вторым – любой из (n – 1) оставшихся предметов, третьим любой из (n – 2) оставшихся предметов и т. д. В результате число перестановок будет равно произведению n множителей n (n – 1) (n – 2) ... ∙ 3 ∙ 2 ∙ 1.

Рис. 1. Перестановки (варианты размещения четырех предметов по четырем ячейкам)


Упорядоченная совокупность m предметов, выбираемых из исходных n предметов, называется размещением из n по m. С помощью рассуждений, аналогичных предыдущим, нетрудно найти, что число размещений из n по m (оно обозначается , от французского arrangement – размещение) равно произведению m множителей
n (n – 1) (n – 2) ... (n – m + 2) (n – m + 1).

 

Рис. 2. Размещения (варианты размещения четырех предметов по трем ячейкам)


Наконец, неупорядоченная совокупность m предметов, выбираемых из исходных n предметов, называется сочетанием из n по m. Число сочетаний обозначается , от французского combinaison – сочетание. Поскольку одному и тому же сочетанию соответствует Pm размещений (получаемых с помощью различных перестановок одного и того же набора m элементов), число сочетаний из n по m меньше числа размещений из n по m в Pm раз:

 

Рис. 3. Сочетания (неупорядоченные размещения)


Впервые понятия перестановки, размещения и сочетания в их взаимосвязи появились в написанной на древенееврейском языке арифметике (1321 г.) жившего в Провансе (Юго-Восточная Франция) Льва Герсонида, или Леви бен Гершона, однако его труд не был известен большинству последующих европейских математиков. В основном элементы комбинаторики были открыты и упорядочены математиками XVII и начала XVIII вв.

Например, термин permutation – перестановка – появился в учебнике «Теория и практика арифметика» (1656 г.) у работавшего в Лувене и Антверпене (ныне Бельгия) преподавателя математики Андре Таке, учебники которого получили большое распространение в XVII–XVIII вв. Понятие размещений и равенство вновь появились только у Я. Бернулли, давшего наиболее полное изложение комбинаторики во второй части «Искусства предположений», изданного в 1713 г. спустя четыре года после смерти автора и ставшего фундаментальной работой по теории вероятностей.

А вот история сочетаний, как мы сейчас убедимся, более давняя: а именно, числа сочетаний – оказывается, ни что иное, как давно знакомые нам биномиальные коэффициенты, которые мы (вслед за Эйлером) обозначали

Дело тут вот в чем: число – это коэффициент при an – mbm в разложении выражения (a + b)n. Когда бином (a + b) возводится в n-ую степень, т. е. перемножаются n выражений (a + b), множитель bm получается из m выражений (a + b), а an – m – из оставшихся (n – m) таких же выражений. Коэффициент равен числу, указывающему, сколько раз произведение an – mbm появляется в этом разложении, т. е. сколько раз можно выбрать m из n множителей. Слово combinaison – сочетание – употреблял уже Б. Паскаль, который, как уже было указано, уделил большое внимание свойствам биномиальных сочетаний, образующих треугольник Паскаля.

Соответственно, на числа сочетаний переносятся все уже известные свойства биномиальных коэффициентов, в частности, свойство

Это свойство можно доказать новым способом, исходя из комбинаторного смысла чисел . Сумма – это совокупное число, которым можно выбрать последовательно из n имеющихся элементов: ноль элементов (это можно сделать только одним способом), один элемент (это, разумеется, можно сделать n способами), два элемента и т. д., наконец, n элементов (снова одним способом). Каково же это суммарное число? Обратимся к способу решения вышеприведенной задачи об ожерельях! В данном сочетании первый элемент либо присутствует, либо нет – две возможности. Независимо от первого, второй либо присутствует, либо нет – значит, для присутствия или отсутствия первого и второго четыре возможности. Независимо от первого и второго, третий может присутствовать, может не присутствовать – итого 8 возможностей и т. д. Всего получается 2n всевозможных сочетаний, где каждый элемент может присутствовать, а может и отсутствовать, вплоть до одновременного отсутствия всех n элементов (единственный возможный вариант сочетания из n по 0): правда, индийская задача как раз этот – единственный – случай и исключала: ожерелье вовсе без камней – вообще не ожерелье.

Также по-новому, исходя из комбинаторного определения сочетаний, можно доказать и свойство , гарантирующее, вместе с очевидными равенствами , что числа сочетаний можно найти с помощью треугольника Паскаля. Попробуйте!

Доказательство

Т. н. мультипликативное представление биномиальных коэффициентов

 = (n (n – 1) (n – 2) ... (n – m + 2) (n – m + 1)) / (m (m – 1) (m – 2) ... ∙ 3 ∙ 2 ∙ 1)

впервые (после Леви бен Гершона) установил парижский преподаватель математики П. Эригон (1634 г.), но широкую известность оно получило благодаря работе Паскаля «Трактат об арифметическом треугольнике», опубликованной в 1665 г. после смерти автора. Пожалуй, проще всего этот результат доказывается с помощью равенства . Впрочем, мы сейчас обычно записываем «мультипликативное представление» несколько иначе, с помощью знака факториала. Факториалом натурального числа n называется произведение всех натуральных чисел от 1 до n. Факториалом 0 считается 1. Термин «факториал» впервые предложил французский математик Л. Ф. А. Арбогаст (1800 г.). Факториал числа n обозначается n! Это обозначение ввел в 1808 г. немецкий математик К. Крамп. Итак, n! = 1 ∙ 2 ∙ 3 ∙ ... ∙ n, 0! = 1. В этих обозначениях

Pn = n!,


Что касается самого слова «комбинаторика», то оно восходит к «Рассуждению о комбинаторном искусстве» двадцатилетнего Лейбница (1666 г.), которое положило начало этому разделу математики как самостоятельной науке. «Рассуждение» Лейбница содержало ряд теорем о сочетаниях и перестановках, но, кроме того, автор провозглашал весьма широкую применимость новой науки к таким разнообразным предметам, как замки, органы, силлогизмы, смешение цветов, стихосложение, логика, геометрия, военное искусство, грамматика, юриспруденция, медицина и богословие. В дальнейшем Лейбниц продолжил вынашивать грандиозный замысел комбинаторики, полагая, что, как обычная математика занимается большим и малым, единым и многим, целым и частью, так комбинаторика должна заниматься одинаковым и различным, похожим и непохожим, абсолютным и относительным местоположением. Лейбниц предвидел приложения комбинаторики к кодированию и декодированию, к играм, статистике, теории наблюдений. Следует отметить, что, хотя ныне мы понимаем комбинаторику более узко, тем не менее, предвидения Лейбница относительно развития математических теорий, относящихся к указанным предметам, ныне вовсе не выглядят такими беспочвенными, какими казались в его время.