ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 16647
Скачиваний: 202
26
2 Элементы комбинаторики
2.1 Вводные замечания
Впервые термин «комбинаторный» появился в работе «Об искусстве
комбинаторики», опубликованной 1666 г. немецким языковедом, философом и
математиком Готфридом Вильгельмом Лейбницем (1646–1716). Именно с этого
времени комбинаторику стали рассматривать как самостоятельное направление
в науке [42, с. 140], хотя многие комбинаторные задачи были сформулированы
ещё в древности.
В литературе толкование различными авторами термина «комбинатори-
ка» является почти одинаковым:
«Комбинаторика – раздел дискретной математики, изучающий всевоз-
можные сочетания и расположения предметов» [36, с. 280].
«Комбинаторика – [от лат.
combinare
– соединять, сочетать] раздел мате-
матики, изучающий приёмы нахождения числа различных соединений (комби-
наций): перестановок, размещений, сочетаний, составляемых при определён-
ных условиях из данных предметов» [43, с. 311].
«Комбинаторика – раздел математики, в котором рассматриваются раз-
личного вида совокупности (соединения) образов из элементов некоторого
множества
M
, содержащего
n
различных элементов. Виды соединений: разме-
щения, перестановки, сочетания» [41, с. 219].
Исходным в комбинаторике является понятие
выборки
как набора
m
эле-
ментов из
n
заданных, причем наборы могут быть как упорядоченными, так и
неупорядоченными, с повторениями элементов и без повторений [33, с. 131].
Понятие выборки не требует уточнения, вполне достаточно пояснения близки-
ми по смыслу словами, такими как расстановки, комбинации, соединения.
Согласно [33, с. 130], в комбинаторике различают две задачи. Одна из
них –
пересчёт
, другая –
перечисление
. Если требуется ответить на вопрос
«Сколько?», то это задача пересчёта. Например: «Сколько существует пя-
тизначных двоичных чисел, в каждом из которых содержится точно два нуля и
каждое число начинается с единицы?». Ответом является число 6. Если же тре-
буется найти все выборки, удовлетворяющие заданным условиям, то это будет
задача перечисления. Например: «Найдите все пятизначные двоичные числа, в
каждом из которых содержится точно два нуля и каждое число начинается с
27
единицы?». Ответом является не число 6, как в предыдущей формулировке этой
задачи, а перечень вида: 11100, 11010, 11001, 10110, 10101, 10011.
В настоящее время комбинаторика в той или иной мере применяется во
многих науках. Можно даже утверждать, что очень непросто найти научное
направление, где бы комбинаторные понятия совсем не применялись. В связи с
этим комбинаторика включена в данное пособие как важнейшая составляющая
курса дискретной математики, имеющая большое прикладное значение.
2.2 Факториал
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Факториал
– это функция аргумента n, представляющая
собой произведение всех натуральных чисел от
1
до n без пропус-
ков, где каждое число встречается точно один раз:
n
!
=
1·2·3·4·…·(
n –
1)
n.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Название функции, согласно [43], произошло от лат.
factor
(делающий,
производящий), а согласно [42, с. 310] – от англ.
factor
, что в переводе обозна-
чает «сомножитель».
Переменная
n
может принимать любые значения из натурального ряда, но
не всякое целое число может быть значением функции
n
!.
Например, число 100 невозможно представить в виде произведения чисел
натурального ряда от 1 до
n
без пропусков и не содержащего повторяющихся
чисел, поэтому оно не может быть значением функции
n
!.
Запишем функцию
n
! в виде
f
=
n
! = (
n
– 1)!
n
.
При
n
= 1 имеем:
f
= (1 – 1)!·1 = 0!·1 = 1!,
откуда следует, что 0! = 1.
Рассмотрим несколько примеров.
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.1
· · · · · · · · · · · · · · · · · · · · · · ·
Записать со знаком факториала:
2·3·4·5·5·6.
В заданном произведении число 5 встречается два раза. Кроме того, в за-
писи отсутствует единица. Добавим её. Тогда получим:
2·3·4·5·5·6 = 1·2·3·4·5·5·6 = 6!·5.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
28
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.2
· · · · · · · · · · · · · · · · · · · · · · ·
Записать со знаком факториала: 1·3·5·6·7·8.
Умножим и разделим на 2 и 4 все выражение:
1·3·5·6·7·8 =
4
2
8
7
6
5
4
3
2
1
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
.
После сокращения на 8 находим ответ:
1·3·5·6·7·8 = 7!.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.3
· · · · · · · · · · · · · · · · · · · · · · ·
Упростить:
! (
1)!
.
(
2)!
k
k
N
k
+
−
=
−
(2.1)
Представим выражение (2.1) в виде
1 2 3 ... (
2)(
1)
1 2 3 ... (
2)(
1)
.
1 2 3 ... (
2)
⋅ ⋅ ⋅ ⋅
−
−
+ ⋅ ⋅ ⋅ ⋅
−
−
=
⋅ ⋅ ⋅ ⋅
−
k
k
k
k
k
N
k
В числителе вынесем за скобки 1·2·3·…·(k – 2):
[
]
1 2 3 ... (
2) (
1)
(
1)
.
1 2 3 ... (
2)
⋅ ⋅ ⋅ ⋅
−
−
+
−
=
⋅ ⋅ ⋅ ⋅
−
k
k
k
k
N
k
После сокращения получаем ответ:
N = (k – 1)k + k – 1 = k
2
– 1.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.4
· · · · · · · · · · · · · · · · · · · · · · ·
Упростить:
.
!
)
2
(
!
)
2
(
!
)
1
(
!
2
2
−
−
−
+
=
n
n
n
n
K
В числителе вынесем за скобки выражение
1 2 3 ... (
2) 1 2 3 ... (
2).
n
n
⋅ ⋅ ⋅ ⋅
−
⋅ ⋅ ⋅ ⋅ ⋅
−
Сократим его со знаменателем, тогда получим:
K = n
4
– 2n
3
+ n
2
+ n –1.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
29
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1.
Запишите произведения с использованием знака факториа-
ла:
1) 1·2·3·4·5·6·7·8;
3) 1·2·3·…·(k – 1);
2) 1·1·3·4·6·7·8·9·10;
4) 1·2·5·6·7·8·9·10·11·12.
2.
Вычислите при n = 31:
1)
)!
2
)(
4
3
(
2
!
4
)!
1
(
3
−
+
+
−
n
n
n
n
;
2)
3
!
)!
1
(
)!
1
(
!
n
n
n
n
n
+
−
.
3.
Найдите значение функции при n = 2:
1) f = (n–2)!(n–1)n
3
;
2) f = (n–3)!(n–2)(n–1)n.
4.
Какими цифрами не может оканчиваться число n!?
5.
Какими цифрами может оканчиваться число n! при n >
3?
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
2.3 Правило произведения в комбинаторике
Правило произведения является основным в комбинаторике. Его форму-
лировка: если один элемент из некоторого множества может быть выбран n
способами, а второй после него – m способами, то выбор того и другого эле-
ментов в заданном порядке может быть осуществлен N способами:
N = nm.
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.5
· · · · · · · · · · · · · · · · · · · · · · ·
Сколько существует двузначных чисел шестеричной системы счисления,
в каждом из которых нет повторов цифр и нет нулей?
Запишем шестеричные цифры, исключив нуль: 1, 2, 3, 4, 5. Одну цифру из
них можно выбрать n = 5 способами. Так как повторы запрещены, то вторую
цифру можно выбрать m = 4 способами. Следовательно, выбор двух цифр с
учётом порядка их записи возможен 5·4 = 20 способами. Это числа:
12, 13, 14, 15, 21, 23, 24, 25, 31, 32, 34, 35, 41, 42, 43, 45, 51, 52, 53, 54.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.6
· · · · · · · · · · · · · · · · · · · · · · ·
В урне пять шаров, пронумерованных шестеричными цифрами вида 1, 2,
3, 4, 5. Все номера разные. Наугад вынимают один шар и записывают его но-
30
мер. Шар возвращают в урну и наугад снова выбирают один шар и его номер
записывают справа от первой цифры. Получится двухразрядное число. Сколько
возможно таких различных чисел?
Очевидно, что задача сводится к вопросу о том, сколько существует
двухразрядных чисел, которые можно составить из цифр множества {1, 2, 3, 4,
5} при условии, что повторы цифр разрешены. Так как шаров 5, то на первое
место можно поставить одну из пяти цифр. Следовательно, n = 5. Выбор второй
цифры возможен также пятью способами. Таким образом, m = 5. Тогда искомое
число nm = 5·5 = 25. Среди всех этих 25 выборок (в отличие от предыдущего
примера) существуют пары с одинаковыми цифрами.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.7
· · · · · · · · · · · · · · · · · · · · · · ·
Условие предыдущего примера, но шары извлекают три раза. Сколько
получится трехзначных чисел?
На первом месте может стоять одна цифра из пяти, на втором – также од-
на из пяти, и на третьем – одна из пяти. Следовательно, число выборок равно
5·5·5 = 125.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.8
· · · · · · · · · · · · · · · · · · · · · · ·
Сколько существует трехразрядных чисел семеричной системы счисле-
ния, не начинающихся с нуля? Повторы цифр в числах возможны.
В семеричной системе счисления семь цифр: 0, 1, 2, 3, 4, 5, 6. Первую
цифру можно выбрать шестью способами, поскольку нуль не используем: по
условию его запрещено ставить на место старшего разряда. Вторая цифра мо-
жет быть любой, в том числе и нулем, следовательно, для её выбора существует
7 вариантов. То же самое относится и к цифре младшего разряда. Искомое чис-
ло равно 6·7·7 = 294.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.9
· · · · · · · · · · · · · · · · · · · · · · ·
Сколько существует четырёхзначных симметричных чисел восьмеричной
системы счисления, то есть таких чисел, которые одинаково читаются как слева