Избранные комбинаторные задачи

     Пример

     Ниже  выписаны всевозможные перестановки из четырех элементов: 

 

     Теорема. Число всевозможных перестановок, которые могут быть образованы из п элементов, равно:

     n! = 12 …. n.

     Пример 

     Сколько различных чисел можно составить  из цифр

     0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

     причем:

     a) каждая цифра в обозначении  числа встречается один раз 

     b) цифра 0 не должна занимать первое место?

     Решение. Если не принимать во внимание условие b), то из 10 цифр можно составить 10! различных чисел, в которых каждая цифра содержится один раз. Из общего количества полученных чисел 9! чисел начинаются цифрой 0. Следовательно, искомое количество чисел равно:

     10!- 9! = 9 9! = 1 2 3 4 5 6 7 8 = 3 265 920. 

     2.1.3. Размещения

     Определение. Размещением из n элементов по k называется всякая упорядоченная часть данного множество n элементов, содержащая k элементов.

     Два различные размещения из данных n элементов, взятых по k, различаются либо составом входящих в них элементов, либо при одном (и том же составе элементов порядком их расположения.

     Число различных размещений, взятых из n элементов по k обозначается символом .

     Пример 

     Ниже  выписаны всевозможные размещения, составленные из четырех элементов по 3

     Теорема. Число различных размещений, взятых из n элементов по k, выражается формулой:

     = n(n — 1)(n — 2) … (n — k + l) = .

     Пример 

     Сколько различных натуральных чисел  можно составить из цифр 0, 1, 2, 3, 4, если в обозначении каждого числа каждая из данных цифр входит не более одного раза?

     Решение. Из пяти данных цифр можно составить = 5! различных размещений; эти размещения дадут всевозможные пятизначные числа за исключением тех размещений, которые начинаются нулем. Количество этих последних размещений равно . Таким образом, из данных цифр можно составить:

       —  = 5 4 3 2 1 — 4 3 2 1 = 96

различных пятизначных чисел. Количество различных четырехзначных чисел, которые можно составить из цифр 0, 1,  2, 3, 4, равно за вычетом количества тех размещений, которые начинаются нулем, т. е.

       —  = 5 4 3 2 — 4 3 2 = 96.

     Аналогично  количество различных трехзначных, двузначных и однозначных чисел  будет равно соответственно

       —  = 48      — = 16   и   4

Всего получится 260 натуральных чисел. 

     2.1.4. Сочетания

     Пусть µ  некоторое конечное множество, состоящее из n элементов:

     {a, b, …, c}.

     Определение. Сочетанием из n элементов, взятых по k, называется всякая часть, содержащая k элементов данного множества µ, состоящего из n элементов.

     Два различные сочетания из данных n элементов, взятых по k, отличаются составом входящих в них элементов: именно, если два сочетания различны, то в одном из них содержится хотя бы один элемент, не содержащийся в другом.

     Пример 

     Ниже  выписаны всевозможные сочетания, составленные из 5 элементов 1, 2, 3, 4, по 3:

     123, 124, 125, 134,135, 145

     234, 235, 245

     345

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

     1, 2, 3, ..., n.

     Это множество натуральных чисел  будет служить представителем класса конечных множеств, содержащих n элементов.

     Символом  обозначается число различных сочетаний из n элементов, взятых по k.

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

       =n.

     Далее, есть число частeй рассматриваемого множества, содержащих по 2 элемента, все такие части можно вписать в следующую таблицу:  

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

      

     В этой таблице каждая пара выписана 2 раза, так, например, взяв элемент 1, присоединив к нему элемент 2, получим {1, 2} ту же пару {2, 1} получим, взяв элемент 2 и присоединив к нему 1. Число всех строк таблицы равно n, число столбцов n-1, общее число всех пар n(n-1), из которых различными являются пар, следовательно:

      = .

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

     = 1.

     Другая  несобственная часть есть пустое множество, не содержащее элементов, поэтому считаем:

     =1.

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

     Если  m — натуральное число, отличное от 1, то символом m! обозначается произведение всех натуральных чисел, не больших m;

     m! = 1 2 ... m.

Если  m = 1, то считаем 1! = 1.

Если  m = 0, то считается 0! = 1.

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

     Теорема. Число сочетаний из n элементов по k, где 0 k n равно:

       =   или при k0 = .

     Пример 

     Найти число диагоналей n-угольника.

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

      =

     отрезков, из которых n отрезков являются сторонами многоугольника, а прочие

         — n =

его диагоналями. 

     2.1.5. Перестановки с повторениями

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

     Пусть {a, b, …, c} — некоторое данное множество (конечное) элементов.

     Определение. Перестановкой с повторениями, в которой элемент а повторяется α раз, элемент b повторяется β раз и т. д., элемент с повторяется γ раз, где α, β, …, γ — данные числа, называется всякое размещение с повторениями, составленное из данных элементов, в котором каждый из элементов повторяется указанное число раз. Число m = α + β + ... + γ называется порядком перестановки.

     Пример

     Ниже  выписаны все перестановки, в которых  элементы a, b и с повторяются 2, 2 и 1 раз (соответственно)