§ 3. Определения и формулы

Примеров, рассмотренных в двух предыдущих параграфах, вполне достаточно, чтобы заметить некоторые общие закономерности и поставить общие задачи. Заметим прежде всего, что во всех рассмотренных примерах нам приходилось иметь дело с некоторыми конечными множествами и различными их подмножествами.

Нас интересовало или число всех возможных подмножеств (пример 5 из § 2), или число подмножеств, обладающих определенным количеством элементов (примеры 4, 7 из § 1, примеры 1, 2, 3, 6

из § 2). В других случаях нужно было рассматривать упорядоченные подмножества, в которых элементы были расположены определенным образом (примеры 3, 6 из § 1, пример 4 из § 2). Здесь нам нужно было знать число различных упорядоченных подмножеств, считая различным образом упорядоченные подмножества различными. Наконец, встречалась и задача, в которой нужно было определить количество различных способов упорядочить данное конечное множество, то есть расположить его элементы в определенном порядке (пример 2, § 1). Все эти задачи можно теперь рассмотреть в общем виде.

Рассмотрим прежде всего точное определение упоминавшегося выше термина упорядоченное множество.

Конечное множество, состоящее из элементов, называется упорядоченным, если его элементы каким-либо образом занумерованы, числами

«Номера», которые при этом приписываются элементам множества, позволяют мыслить элементы этого множества «расположенными» в каком-то «порядке»: первый элемент «предшествует» второму (а второй «следует» за первым), второй предшествует третьему и т. д.

Одно и то же конечное множество можно, разумеется, упорядочить разными способами. Например, множество учеников данного класса можно упорядочить по росту (опять-таки двумя противоположными способами), по весу, по возрасту, по алфавиту фамилий и т. д. и т. п.

Не следует, однако, думать, что каждый такой «порядок» связан непременно с каким-либо «естественным правилом» упорядочения. Скажем, множество шахматных фигур (каждого цвета по отдельности или все 32) можно, конечно, упорядочить слева направо в порядке их расстановки на доске или по силе (а фигуры одинаковой силы — слева направо или еще как угодно), но можно считать «упорядочением» и «беспорядочную» последовательность, в которой мы случайно поставили их на доску для данной партии. А можно было бы их просто расставить в ряд в произвольном «порядке». Аналогично множество учеников данного класса можно считать упорядоченным в соответствии с тем (в достаточной мере случайным!) порядком, в котором они сегодня пришли в школу.

Короче говоря, «нумерация», о которой говорится в определении упорядоченного множества, не предполагает, вообще говоря, никакого заранее известного «закона» — упорядочивая конечное множество, мы просто приписываем каким-либо образом номера его элементам. И если в приведенных примерах легко было все же указать некоторые «естественные» способы упорядочения, то для упорядочения, например, множества муравьев в муравейнике или рыб в озере трудно указать более «естественный» способ, чем переловить их всех по очереди и перенумеровать в порядке попадания их в банку или на удочку...

Таким образом, речь, как правило, идет лишь о теоретическом, мысленном упорядочении, которое для конечного множества всегда возможно.

В отличие от соглашений, принятых нами выше (Введение, п. 1 и п. 6) для множеств неупорядоченных, упорядоченные множества мы будем считать совпадающими (или равными) лишь тогда, когда они не только состоят из одних и тех же элементов, но и упорядочены (расположены, занумерованы и т. одинаковым образом.

Говоря о различных упорядоченных множествах, состоящих из одних и тех же элементов, мы уже несколько раз называли их различными упорядочениями какого-либо множества. Этим термином нам будет удобно пользоваться и в дальнейшем.

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

Множество (безразлично — конечное или бесконечное) называется упорядоченным, если между его элементами установлено некоторое отношение, называемое отношением предшествования, обладающее следующими свойствами.

1) Для любых двух различных элементов а и данного множества либо а предшествует либо предшествует а.

2) Для любых элементов и с данного множества из того, что а предшествует , а предшествует с, следует, что а предшествует с.

Примером упорядоченного множества может служить множество натуральных чисел, «естественным» образом упорядоченное по величине: мы считаем, что предшествует если (можно, конечно, было бы выбрать и упорядочение, обратное «естественному», то есть считать, что предшествует когда Точно так же упорядочивается множество всех действительных чисел. Множество К комплексных чисел, не обладающее никаким «естественным» порядком, можно, например, упорядочить, положив, что предшествует если а при если Все эти множества можно, разумеется, упорядочить и иными способами.

Введем теперь следующее

Определение 1. Пусть дано конечное множество М, состоящее из элементов. Размещением из элементов по элементов называют всякое упорядоченное подмножество множества М, состоящее из элементов.

Из этого определения следует, что и что различные размещения отличаются друг от друга составом входящих в них элементов или порядком их расположения. Как видно из предыдущих параграфов, в комбинаторных задачах требуется знать число различных размещений из элементов по элементов. Это число принято обозначать символом (А — первая буква французского слова arrangement, что означает размещение, приведение в порядок).

Теорема 1. Число различных размещений из элементов по элементов равно произведению последовательных натуральных чисел, начиная от и до включительно:

Доказательство. Формула (1) была уже получена нами при разборе примера 4 в § 2. Здесь мы дадим вывод этой формулы, основанный на методе полной математической индукции. Индукцию будем вести по индексу

Пусть дано множество М, состоящее из элементов. Очевидно, что число различных подмножеств этого множества, содержащих по одному элементу, равно числу элементов М, то есть (подмножества из одного элемента автоматически упорядочены, так как содержат только первый элемент).

Далее, из каждого размещения по одному элементу можно получить различные размещения по два элемента, присоединяя к выбранному первому элементу второй. Так как для выбора второго элемента мы имеем уже возможностей (один из элементов уже использован!), то

Предположим теперь, что для некоторого значения справедлива формула

и докажем, что такая же формула имеет место и для . Пусть образованы все размещения из элементов по элементов. Размещения по элементу могут быть получены присоединением к каждому из полученных еще одного элемента на место.

Из одного размещения по элементов получится столько размещений по элементу, сколько различных элементов можно присоединить, то есть Все получающиеся размещения будут различными, так как они отличаются последним элементом. Размещения по элементу, получающиеся из различных размещений по элементов, также не могут совпасть, поскольку их первые элементов не совпадают. Остается добавить, что таким способом будут получены все размещения по элементу. Отсюда следует, что число размещений по элементу удовлетворяет равенству

Воспользовавшись предположенной по индукции формулой для найдем:

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

Определение 2. Перестановками из элементов называют различные упорядочения данного конечного множества, состоящего из элементов.

Таким образом, различные перестановки отличаются друг от друга лишь порядком элементов. Число возможных различных перестановок из элементов обозначается символом (от французского слова permutation — перестановка, перемещение).

Теорема 2. Число различных перестановок из элементов равно произведению всех последовательных целых чисел, начиная от и до

1 включительно:

Доказательство этой теоремы окажется излишним, если мы заметим, что перестановки являются частным случаем размещений, а именно, при Значит, согласно формуле (1),

Впрочем, нетрудно доказать эту теорему и независимо от понятия размещения. Рассмотрим всевозможные перестановки из элементов и подсчитаем, сколько из них начинаются одним и тем же определенным элементом. Если поставить выделенный элемент перед каждой из перестановок из остальных элементов, то мы получим все возможные перестановки, начинающиеся данным элементом. Следовательно, число всех перестановок из элементов, начинающихся одним определенным элементом, равно Но тогда для числа всех возможных перестановок из элементов находим:

так как любой из элементов может оказаться выделенным.

Формулу (3) можно использовать для доказательства нашей теоремы, пользуясь индукцией по числу элементов множества. Очевидно, что так как один элемент может находиться только на первом месте. Допустим, что формула (2) верна для множества, содержащего элемент, то есть что

На основании формулы (3) найдем, что

Таким образом, формула (2) верна для любого

Упражнения

(см. скан)

Как было указано выше, число перестановок можно получить из числа размещений. Можно сделать и обратное, выразив число размещений через число перестановок.

Теорема 3. Число различных размещений из элементов по элементов равно числу перестановок из элементов, деленному на число перестановок из элементов:

Доказательство. Формулу (4) легко получить из формул (1) и (2). Действительно,

Это доказательство, несмотря на простоту и очевидность, часто вызывает чувство неудовлетворенности, так как сводится к формальным выкладкам и не показывает существа дела. Поэтому мы приведем еще одно доказательство, опирающееся только на определения размещений и перестановок.

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

Следовательно, каждое размещение из элементов по элементов порождает столько перестановок по элементов, сколькими различными способами к нему можно присоединить оставшихся элементов. Так как это можно сделать различными способами, то общее число перестановок из элементов равно

откуда и следует равенство (4).

Упражнения

(см. скан)

Определение 3. Пусть дано конечное множество состоящее из элементов. Сочетанием из элементов по элементов называется любое подмножество содержащее элементов.

Таким образом, сочетания являются неупорядоченными подмножествами, и различные сочетания различаются между собой только составом элементов. Число всех возможных сочетаний из элементов по обозначают через (от французского combinaison — сочетание, комбинация), а также через или

Теорема 4. Число всех возможных сочетаний из элементов по элементов равно произведению последовательных натуральных чисел от до деленному на произведение последовательных натуральных чисел от до 1:

Доказательство этой теоремы сводится к доказательству следующего утверждения: число сочетаний из элементов по элементов равно числу размещений из элементов по элементов, деленному на число перестановок из элементов. В самом деле, из этого утверждения, пользуясь формулами (1) и (2), легко получаем формулу (5).

Чтобы доказать теперь это утверждение, заметим, что каждое размещение из элементов по элементов может быть получено из такого же сочетания путем различных перестановок его элементов. Следовательно, каждое сочетание порождает столько размещений

сколько возможно различных перестановок его элементов. Отсюда следует, что или

что и требовалось доказать.

Формулу (5) обычно приводят к более удобному для записи симметричному виду, умножая числитель и знаменатель на произведение всех натуральных чисел от до 1 включительно. Тогда мы приходим к формуле:

Формула (7) означает, что

Рекомендуем читателю самостоятельно разобраться в комбинаторном смысле этого равенства, доказавши его непосредственно, исходя лишь из определения перестановок и сочетаний.

Упражнения

(см. скан)

Как было указано в формулировке теоремы 4, символ имеет смысл при и означает количество подмножеств множества М, содержащих ровно по элементов. Ясно, что это следует и из формулы (5), но формулу (7) в этом случае применить нельзя, так как она будет содержать бессмысленный символ Для общности принято полагать . В этом случае формула (7) дает для то же значение 1.

Удобно также ввести в рассмотрение символ что означает число пустых подмножеств множества М, то есть . То же самое получится и из формулы (7), если воспользоваться принятым условием

Принимаемое условие имеет на самом деле более глубокий смысл, чем просто возможность вычислять или по формуле (7).

Более существенное основание для того, чтобы считать выражение 0! равным единице, состоит в следующем. Выражение можно рассматривать

бать как функцию, определенную лишь Для натурального аргумента . В своей области определения она удовлетворяет функциональному уравнению справедливость которого легко проверяется для всех натуральных Действительно, Если же в этом равенстве положить то мы получим

Однако все эти соображения являются не слишком убедительными, так как нельзя быть уверенным в том, что нам не встретится другая формула, в которой будет удобно полагать 0! равным какому-нибудь другому числу. Окончательное решение можно получить, идя вот каким путем. Естественно поставить вопрос: можно ли построить непрерывную функцию, определенную для всех значений х, и такую, которая для целых значений аргумента совпа дает с то есть доопределить функцию расширив ее область определения? Напомним, что в математическом анализе такое расширение производится, например, для показательной функции которая вначале была определена лишь для натурального показателя степени.

Поставленный вопрос был решен Эйлером и Гауссом. С помощью различных формул (Эйлер — через интеграл, а Гаусс — через бесконечное произведение) они определили функцию, обладающую нужным свойством, и доказали единственность такой функции при некоторых естественных предположениях. Эта функция называется гамма-функцией и обозначается Она определена для всех и удовлетворяет функциональному уравнению для натуральных принимает значения

Обе формулы, определяющие функцию имеют смысл при и определяют значение Но в силу равенства под выражением следует понимать именно значение

Все выведенные нами в настоящем параграфе формулы для числа размещений, перестановок и сочетаний фактически уже неоднократно выводились нами ранее для различных частных конкретных случаев при рассмотрении примеров в § 1, 2. Рассмотрим еще некоторые свойства сочетаний, которые потребуются в дальнейшем.

Теорема 5. Число сочетаний из элементов по элементов равно числу сочетаний из элементов по элементов:

Доказательство. Формально равенство (9) легко получить из формулы для числа сочетаний, записанной в виде (7). Действительно,

Комбинаторный смысл этого равенства также достаточно ясен. Каждому подмножеству из элементов соответствует единственное определенное подмножество из элементов — именно, тех, которые не вошли в первоначальное. Поэтому количество тех и других возможных подмножеств одинаково. При рассмотрении примеров (см. примеры 3 и 6 из § 2) мы фактически уже пользовались этим соображением.

Равенство (9) позволяет сокращать вычисления в тех случаях, когда

Теорема 6. Число сочетаний из элементов по элементов равно сумме числа сочетаний из элементов по элементов и по элементов:

Доказательство, как и в предыдущем случае, проведем двумя различными способами. Прежде всего, пользуясь формулой (7) для числа сочетаний, находим:

Второе доказательство состоит в следующем. Выделим некоторый фиксированный элемент а множества М и рассмотрим сочетания из элементов по элементов, содержащие или не содержащие этот элемент. Число сочетаний по элементов, не содержащих элемента а, равно, очевидно, так как здесь рассматриваются подмножества по элементов, образованные из элементов множества, содержащего элемент (множество М без элемента а). Сочетания, содержащие а, можно получить так: образовать всевозможные сочетания по элементу из того же множества М без элемента а и к каждому из них присоединить а. Отсюда ясно, что число таких сочетаний равно . Так как каждое сочетание по элементов либо содержит данный элемент а, либо не содержит его, то оно принадлежит либо одной, либо другой группе. Поэтому

что и утверждалось

Размещения, перестановки и сочетания вместе часто называют одним словом — соединения.