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

 

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

n! = 1

2 …. 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

1 2 3	1 2 4	1 3 4	2 3 4
1 3 2	1 4 2	1 4 3	2 4 3
2 1 3	2 1 4	3 1 4	3 2 4
2 3 1	2 4 1	3 4 1	3 4 2
3 1 2	4 1 2	4 1 3	4 1 3
3 2 1	4 2 1	4 3 1	4 3 1

Теорема. Число различных размещений, взятых из 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 элемента, все такие части можно вписать в следующую таблицу:

 

{1, 2},	{1, 3},	{1, 4},	…,	{1, n},
	{2, 3},	{2, 4},	…,	{2, n},
		{3, 4},	…,	{3, n},
		……………
				{n-1, n}.

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

 

{1, 2},	{1, 3},	…,	{1, n},
{2, 1},	{2, 3},	…,	{2, n},
…………………….
{n-1, 1},	{n-1, 2},	…,	{n-1, n},
{n, 1},	{n, 2},	…,	{n, n-1}.

 

В этой таблице каждая пара выписана 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 равно:

 =   или при k

0 = .

Пример 

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

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

=

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

   — n =

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

 

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

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

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

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

Пример

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

aabbc	aabcb	aacbb	ababc	abacb
abbac	abbca	abcab	abcba	acabb
acbab	acbba	baabc	baacb	babac
babca	bacab	bacba	bbaac	bbaca
bbcaa	bcaba	bcaba	bcbaa	caabb
cabab	cabba	cbaab	cbaba	cbbaa

 

Теорема. Число различных перестановок с повторениями из элементов {a, b, …, c}, в которых элементы a, b, …, c повторяются соответственно α, β, …, γ раз, равно:

 

Пример 

Дано p + q + r различных предметов; сколькими способами можно разбить эти предметы на 3 группы так, чтобы первая группа содержала р предметов, вторая q предметов, а третья r предметов?

Решение. Расположим все данные предметы в каком-нибудь определенном порядке:

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

2  1  2  3 ... 1

означает, что первый предмет  попал во вторую группу, второй в  первую, третий во вторую и т. д., последний  в первую. Всякому распределению  предметов по группам взаимно  однозначно соответствует перестановка из чисел 1, 2, 3, в которой 1 встречается p раз, 2 встречается q раз и 3 встречается r раз. Число возможных способов распределения предметов равно:

 

 

2.1.6. Размещения с повторениями

Термином «размещение  с повторениями», составленным из данных элементов:

, , … ,

по k в комбинаторике называется всякая конечная k-членная последовательность, членами которой являются данные элементы (а).

Два размещения с повторениями:

, , … ,   и , , … ,

одинаковы б том и только в том случае, когда на одинаковых местах находятся одни и те же элементы:

= ,  = , … , =.

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

Пример 

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

111 112 121 211 113 131 311 114 141 411 222 221 212 223 232

322 224 242 422 333 331 313 133 332 323 134 343 433 444 441

414 144 442 424 244 123 124 213 214 132 334 443 434 344 312

314 142 143 412 413 241 243 421 423 431 432 342 341 321 324

231 234 122  233

 

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

.

Пример 

Имеется n различных книг, каждая в р экземплярах; сколькими способами можно сделать выбор книг из числа данных?

Решение. Перенумеруем в каком-либо порядке n данных книг. Если первая книга берется в экземплярах, вторая в экземплярах и т. д. n-я в экземплярах, то указанному выбору соответствует размещение с повторениями:

, , … ,

из р+1 чисел 0, 1, 2, ..., р, взятых по n (если = 0, то i-я книга не берется вовсе). Таким образом получается различных комбинаций, по числу размещений с повторениями из р+1 элементов по n. Исключив из рассмотрения комбинацию 0, 0, ..., 0, означающую, что не берется ни одна книга, мы получим — 1 различных способов выбора книг.

 

2.1.7. Сочетания с повторениями

Пусть а, b, с,..., d — данное конечное множество, содержащее n элементов. Поставим в соответствие каждому элементу этого множества некоторое целое неотрицательное число, называемое кратностью данного элемента. Это соответствие определяет функцию, для которой значениями аргумента являются данные элементы, а значениями функции — целые неотрицательные числа — кратности элементов. Пусть α — кратность элемента а, β — кратность элемента b, γ — кратность элемента с и т. д. Для обозначения рассматриваемого соответствия выписывают символ, обозначающий данный элемент столько раз, какова его кратность, если эта кратность положительна, если же кратность данного элемента равна нулю, то соответствующий символ не выписывается. Символы, обозначающие элементы, можно писать в каком угодно порядке, лишь бы каждый из них был написан столько раз, какова кратность соответствующего элемента. Так, например, записи