С.В. Яблонский - Введение в дискретную математику (1060464), страница 27
Текст из файла (страница 27)
3 1. Комбинаторные объекты и комбииаторные числа $. Система подмножеств множества Е. Пусть Е (а„..., а„) — конечное множество. Рассматриваются все его подмножества. Эту систему обоаначнм через 6 . Пример. Е (а„а„а,). Система его подмножеств имеет внд: (3, = (А, (а,), (а,), (а,), (ао а,), (ао а,), (аэ а,), (а„а„авП.
2. Размещения элементов из Е по Й. Пусть Е * (а„... ..., а.). Размещением алементов из Е по й называется упорядоченное подмножество из Й элементов, принадлежащих Е. Пример. Е (а„а„а,) и й 2. Выпишем все размещения из этого множества по 2: (а„ а,), (а„ а,), (а„ а,), (а„ о,), (о„ а,), (а„ а,). 3. Перестановки элементов множестваЕ. Пусть Е=* (а„..., а„). Перестановками называются упорядоченные подмножества из и элементов мнолсества Е. ' 172 ч. 1ь комвггньтоэнын АнАлиз Пример.
Е (а„а„а,). Перестановками мноя<ества Е будут (а„аз, а,), (а„а„аз), (а„а„аз), (а„аз, а,), (а„а„аз), (аз, а„а,). Очевидно, что перестановки — частный случай размещений элементов из Е по Й, когда Й = гг. 4. Сочетания элементов пз Е по й. Сочетанием алементов нз Е по й называется неупорядоченное подмножество нз й элементов, принадлежащих Е. Пример.
Е=(а„а„а,) и й 2. Сочетаниями из Е по 2 будут (а„а,), (а„а,), (а„а,). б. Сочетания с повторениями элементов из Е по Й. Сочетанием с повторениями элементов из Е по й является неупорядоченная система из Й элементов, принадлежащих Е, в которой допускается повторение элементов. Пример. Е = (а„а„а,) и й = 2. Сочетаниями с повторениями из Е по 2 будут (а„а,), (а„а,), (а„а,), (аз, а,), (аз, а,), (аз, аз). 6. и-мерный куб размера Й (Й>2). Совокупность всех наборов (а„..., сг.) (упорядоченных сочетаний с повторениями) из мпоя<ества Е, (О, 1, ..., й — 1) по и называется п-мерным кубом размера Й и обозначается через Еь (Еь - Ед х...
х Ез). к раз Пример 1. 3-мерный куб размера 2. Е, (О, 1). Мы имеем следующую совокупность наборов: (О, О, 0), (О, О, 1), (О, 1, 0), (О, 1, 1), (1, О, 0), (1, О, 1), (1, 1, 0), (1, 1, 1). Эти наборы мозкпо рассматривать как вершины единичного 3-мерпого куба (см. рис. 1). Пример 2. На рис. 2 изображен 3-мерный куб размера 3. 7. Разбиения множества Е. Разбиением мвон<ества Е называется неупорядоченная система из не<густых подмножеств (д'о Ю„..., юз) множества Е, обладающая двумя свойствамн: 1) Ю~О...ОЮз Е; 2) для лгобых 1, ) (г чь !) множества 8» и»о'» не пересекаются, т.
е. Е»ОЕ»=Л. П р и м е р. Е (а„а„а,). Разбиениями будут На, а„ а,Н, Па,), (а„ а,Н, ((а,), (а„ а,И, ((а,), (а„ а,И, ((а,5, (а,), (а,Н. Существует много других типов комбппаторпых объев тов. Папрнмер: покрытия конечного множества, блоксхемы, булевы функция, системы частично упорядочеяных мпоя<еств и т. и. Сведения о пих можно найти Ч. П.
КОМБПНАТОРНЫИ АНАЛИЗ в [29, 30, 32]. Во многих нз них комбннаторная сторона играет не основную роль (например, булевы функции), потому их естественно включать в другие разделы дискретной математики. Наряду с классами (г,гд комбинаторных объектов рассматриваются и йю,с 6 со ф2,6 (СР,О Ф,св аД6 кда (д0,0! йт,йгр Рис. 2 Рис. $ так называемые комбинаторные числа, характеризующие число объектов в данном классе и аависящне от некоторых параметров. $2. Простейшие свойства комбинаторных объектов и чисел Здесь изучаются свойства, которые легко усматриваются из «комбниаторных» соображений.
1. Подмножества множества Е (а„аю..., ни). В качестве комбинаторного числа, связанного с 6, обычно берут мощность 6„, т. е. величину !6„!. Пусть 8'ж6„. Сопоставим Ю взаимнооднозначным образом двоичный набор (ио аь ..., и.): !| ~ ~|~ ~ ! » г, если а; ен ег, О, если а;фР. Отсюда получаем, что ! 6„! = ! Е.", ! = 2".
С другой стороны, отсюда же получается простой алго- ч. П..комвпнАтогный Аналпз ритм порождения (перечисления) всех подмножеств. Для этого строим все наборы (в„..., а.) исходя из (О, ..., 0), на каждом шаге прибавляя 1 к соответствующему двоичному числу.
2. Равмещеипя эчементов ив Е по й. Обозначим число таких раэмещений через (в)„. При построении конкретного размещения ва 1-е место можно поставить любой из в элементов, па 2-е место — любой иэ в — 1 оставшпхся элементов и т. д.
Поэтому (в)а в(в — 1) ... (в — й+1) при 1~й<в. (!) Считаем (в)а=О при й>в, поскольку при й) в не существует размещений пз в по й. Кроме того, полагаем (0), (в), = 1. Для чисел (в), выполняются тождества (в)а в(в — 1)х „ (в) „(в) „, (в - й+ 1). Испольвуя первое иа них, с линейной сложностью строим таблицу 1. 3. Перестановки элементов множества Е. Перестановка из элементов — частный случай размещения при й в. Поэтому для числа перестановок имеем ствует ( 1)а Пусть а„(1 + — „) . Очевидно, ..-1+(",)-„'+(",) — ',+ ... +(„") — '„- -1+1+(1- -„') —,'а+ „, +(! — '„) .. (1 — '=„" —,,, ' .„ (в)„в(в — 1) ...2 1 в! Как обычно, считаем О! 1.
Числа в! в табл. 1 расположены по диагонали. Далее мы приводим сведения о числе е и неравенствах, свяаанных с числом е, а также опенки для в! Число е В дальнейшем ато число будет часто встречаться. Дадим его определение. Покажем, что суще- ч. 1ь комвпньтогпый Анализ 175 Таблааа 1 0 1 2 3 4 5 6 ~ 7 ~ 8 ~ 9 О 120 720 720 2 520 5 040 5 040 20 160 40 320 6 720 362 880 181 440 60 480 Сравним зто число с а.+~.' а„+, 1+1+($ — „+ ) — + ...
+(х — „+ ) " ('-:=') "-"('- — ') ('-.— ')"-" . Члены, входящие в а,+„соответственно не меньше членов иа а„. Отсюда а„( а„+, и (а„) — монотонно возрастающая последовательность. Кроме того, так как а„) + ) + () — — ) — + ... + () — — ) "( л — 11 1 1 — — — <)+7+ —,+ — + ...<Э л ~ 1 2 ... а 2 1тв ч, и. комвпнлтогпып АнАлиз е - Йгп (1+ — ), Из доказательства следует, что при п ~ 1 2< ~1+ — ) <е. 3 и, в частности, г и!п ~1+ -) (1.
и) (3) Для последующего ваягно и другое неравенство (4) которое моягет быть получено из рассмотрения графика 1 функции у — (рпс. 3). Сравнивал площади фигур, перван из которых ограничена осью х, прямыми х и, х =я+ 1 и графиком р 1/х, вторая — осью х, прямыми х и, х = и+ 1 и касательпой 1 к кривой в точке х = и + — ,, 2 имеем и+1 или гт л л+ — лиг а (и + т ) )п11+ — ) )1. 1 1~ / 2 л/ Рис. 3 Оценки для и ! Приведем две грубые оценки для и!, испольаующне элементарные доказательства. Первое неравенство (5) то зта последовательность ограпичепа сверху.
Поэтому она имеет предел — его н обозпача1от через е, т. е. Ч. П. КОМБ1П!ЛТОРПЫВ ЛПАЛКЗ (')(') -(:)(::) (8) если О -- гк ! <л. Доказываем по индукции. Прв и =1 имеем 1> 1/е. Ин- дуктивный переход: (и + 1)! ) (л + Ц ( — ) = — л л" >— /л !л л+! л л+! (л+!) -( —.)" где использовано неравенство и" >(и+ 1) "/е (см.
(2) ). Второе неравенство л(<2( —,",) . (О) Доказательство использует хорошо нзвестпое неравенство )аЬ~(а+Ь)/2 (для положительных а и Ь): и! л((1 (л — 1))(2 (и — 2))...)я:;, ~2(з)[(~~ (л) ...~ 2(~) . 4. Сочетания элементов из Е по Й. Сочетание отлича- ется от размещения тем, что в нем не учитывается по- рядок. Поэтому каждому сочетанию соответствует Й! раз(л1 мещений. Отсюда получается формула для числа ( «) сочетаний из и элементов по Й (О < Й ~ и): ()-' (")А л (л — !) ... (л — «+ !) л! «/ «! «! «! (л — «)!' Из данкой формулы вытекает, что (') -(') -( ) ='(:) -( -'.) (л1 Иногда удобно выражение («) доопределить и для слу- чая Й>ил („") -О, поскольку при Й> и не существует сочетаний из и по Й.
В дальнейшем, если не будет специальных оговорок, счи- таем, что Й~ и. Отметим одно тождество, которое легко получается иа (7) ч. и. комвннйтогныи йнйлиэ (78 По аналогии с понятием унимодальпой функции [1] введем понятие унимодальной последовательности (а„), где й = О, 1, ..., и. О п р е д е л е н и е. Последовательность (а,) действительных чисел называется унимодальной, если существует такое Й„, что ар ( а, <... < аз„~ аь„+г ) аь„+з > )... )а„, т.ел 1) последовательность строго возрастает на отрезке [О, й„] при й.
) О; 2) последовательность строго убывает на отрезке [й„ + 1, и] при й„ + 1 ( п; 3) максимальное аначение принимается не более чем в двух точках: Й„и, быть может, Й„+ 1 ь). У лМ Теорема 1. Последовательность чисел «» ]], й О, 1, ..., и, унимодальна, и й„=[и/2]. При четном и максимум достигаетсв в точке й„[и/2] и/2, а ири нечетном и — в двух точках: й„[и/2]=(и — 1)/2 и й„+ +1-(и+1)/2.
Доказательство. Оценим отношение двух соседних членов последовательности (» д~» )= а) При й ~ [и/2], т. е. Й((и+1)/2, имеем (и — й+ +1)/й>1. Поэтому ~»)/(» ",))1. ил-( б) При Й вЂ” (~и — [и/2], т. а. й — 1)и —— в, имеем ", (1. Поэтому (")/( " )<1. Теорема доказана. /н1 Следствие. Максимальное аначеиие ~ » / при фиксированном и равно ~ „/8[) Обозначим через 6„., множество всех сочетаний из (а„..., а„) по Й и через 6„ь,(6„...) — множество всех сочетаний из (а„..., а„,) по Й (соответственно по й — 1). Так как каждому сочетанию из 6„,„, если оно содержит элемент а„, соответствует сочетание из 6„, „„ а если оно не содержит а„, соответствует сочетание иэ ь) См.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
