Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
2) для любых f, j (i^j) множества и $$ не пересекаются, т. е. П Ш i = Л.
Пример. Е = (д,, д2, д3}. Разбиениями будут {(«1, д2, ДзН, {{ail, {д2) д3}}, ИйгК й3}}, {{да}, {дь д2)}, Па,}, {д2), {а3}}.
Существует мпого других типов комбинаторных объек-* тов. Например: покрытия конечного множества, блок-схемы, булевы функции, системы частично упорядоченных множеств и т. п. Сведепия о них можно найти
Ч. 11. йиИНэННАТиЛ'НЫИ лнл.ша
в [29, 30, 32]. Во многих из них комбинаторная сторона играет не основную роль (например, булевы функции), потому их естественно включать в другие разделы диск-
ретной математики.
Наряду с классами комбинаторных объектов рассматриваются и
(Ш)
Рис. 1
(2,2,2)
Рис. 2
так называемые комбинаторные числа, характеризующие число объектов в данном классе и зависящие от некоторых параметров.
§ 2. Простейшие свойства комбинаторных объектов и чисел
Здесь изучаются свойства, которые легко усматриваются из «комбинаторных» соображений.
1. Подмножества множества Е=* {ах, а2,..ап}. В качестве комбинаторного числа, связанного с обычно берут мощность т. е. величину !@„1. Пусть <8 е<?п. Сопоставим <8 взаимнооднозначным образом двоичный набор (а1? аг, ..., а„):
[1, если ~ [О, если а,- ф
Отсюда получаем, что
|(|г.| = |?;|-2".
С другой стороны, отсюда же получается простой алго-
’Л. га* пи1йВИПА1и1'ПШ1 АДАЛИД
ритм порождения (перечисления) всех подмиожеств. Для этого строим все наборы (аь ..., аЛ) исходя из (0, 0),
на каждом шаге прибавляя 1 к соответствующему двоичному числу.
2. Размещения элементов из Е по к. Обозначим’ число таких размещений через (п)ь. При построении конкретного размещения на 1-е место можно поставить любой из п элементов, на 2-е место — любой из п — 1 оставшихся элементов и т. д. Поэтому
(л)Л = п {п — 1) ... (п — к + 1) при (1)
Считаем
(л)\ = 0 при к>п,
поскольку при к > п не существует размещений из п по к. Кроме того, полагаем
(0). = («) о — 1.
Для чисел (п)’А выполняются тождества
(п)к = п(п- 1)*_„
(«)* = («)&-! (п-к + 1)',
Используя первое из них, с линейной сложностью строим таблицу 1.
3. Перестановки элементов множества Е. Перестановка из элементов — частный случай размещения при к = п. Поэтому для числа перестановок имеем
(п)п~п(п — 1) ...2 ? 1 — л!
Как обычно, считаем 0! = 1. Числа пI в табл. 1 расположены по диагонали.
Далее мы приводим сведения о числе е и неравенствах, связанных с числом е, а также оценки для п\ Число е. В дальнейшем это число будет часто встречаться. Дадим его определение. Покажем, что существует
^ (?***""»)? Пусть аи = ^1 + ^ . Очевидно,
в'‘ = 1 + (")«+(”)^+ +
- 1 + 1 + (* - г) Г2+ • • • +['Ч) ?? • ??
Ч. И. КОМБИНАТОРНЫЙ АНАЛИЗ 175
Таблица 1
п к
0 1 2 3 4 ^ 1 6 7 8 9-
0 4 . . .
1 1 1
2 X 2 2 0
3 1 3 6 6 * .V *
4 1 4 12 24 24
5 1 5 20 00 120 120
6 1 6 30 120 360 720 720
7 1 7 42 210 840 2 520 5 040 5 040
8 1 8 56 336 1680 6 720 20 160 40 320 40 320
9 1 9 72 504 3024 15 120 60 480 181 440 362 880 362 880
Сравним это число с ап+У:
°п+1 = 4 + 1 + ^1 — 7Г+т) Г2 + ? * * + (1 ~ * ‘ *
.. 1 ?? + /!__М...^1-—У-.-___________*.__________.
* ^ л4“1у^и2*.,#*гс ^ л 1 у ^ йт 1 у112 * * *. * (п+1)
Члены, входящие в ап+1, соответственно не меньше чле-_ нов из ап.
Отсюда ап < яп+1 и {ап} — монотонно возрастающая последовательность. Кроме того, так как
ап=1 + 1 + (1-1)7^ + _ + ^1-1)
1.2.;.;.я< 1 +1 + 4" +р + ... <31
176
Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ
то эта последовательность ограничена сверху. Поэтому она имеет предел — его и обозначают через е, т. е,
е = Нш (Ч + -Мч «~«Л п)
Из доказательства следует, что при п > 1 2<
(1 + 4)л<^<з
и, в частности,
п In + ~ j < 1.
Для последующего важно и другое неравенство
(л + ~) ln (l+ !)>!.
(2)
(3)
№
которое может быть получено из рассмотрения графика \
функции У = — (рис. 3). Сравнивая площади фигур,
первая из которых ограничена осью х, прямыми х = л,
х = л + 1 и графиком у = 1/х, вторая — осью х, прямыми х = = л, х = л 4-1 и касательпой
, 1
к кривой в точке X = Л -Р * имеем
71+1
J
->
или
(в+4) ь (i+4)>i.
Оценки для л! Приведем две грубые оцепки для л!, использующие элементарные доказательства.
Первое неравенство
л! >(л/е)\
(5)
Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ 177
Доказываем но индукции. При п — 1 имеем 1 > 1/а. Индуктивный переход:
(» ?И)1>|Ч-1)(т)'-Ч1.'>*^1 " \ ~
где использовано неравенство пп>[п + 1)п/е (сы. (2)). Второе неравенство
2
Доказательство использует хорошо известное неравенство УаЬ =? (а + Ъ)/2 (для положительных а и Ь): п! = «[(!•(«- 1))(2Чп-2)),,.]<
<2(т)[Й'(т)‘-]-2(тГ
4. Сочетания элементов из Е по к. Сочетание отличается от размещения тем, что в нем не учитывается порядок. Поэтому каждому сочетанию соответствует &! размещений. Отсюда получается формула для числа сочетаний из п элементов по к (0 < к ^ я):
И* п (л — 1) ... (я — а-Н) п\
М_ _ .... ... _..........
\к) к\ к\ АЦь—АД*
Из данной формулы вытекает, что
(7)
Иногда удобно выражение Ку доопределить и для случая к > п:
