Новиков Ф.А. Дискретная математика для программистов (860615), страница 37
Текст из файла (страница 37)
Число сочетанийС(тп, п) находится в ( т + 1)-м ряду на (п + 1)-м месте.12Опостсн Луи Коши (1789-1857).Блез Паскаль (1623-1662).192Глава 5. Комбинаторика'5.3.5. Генерация подмножествЭлементы множества { 1 , . . . , ш } естественным образом упорядочены. Поэтомукаждое n-элементное подмножество этого множества также можно рассматриватькак упорядоченную последовательность. На множестве таких последовательностей определяется лексикографический порядок (см. упражнение 1.8). Следующий простой алгоритм генерирует все n-элементные подмножества ш-элемеитпого множества в лексикографическом порядке.Алгоритм 5.3 Генерация n-элементных подмножеств m-элементного множестваВход: п — мощность подмножества, тп — мощность множества, тп ^ п > 0.Выход: последовательность всех n-элементных подмножеств ш-элемептпогомножества в лексикографическом порядке,for г from 1 to тп doА[г]: = г { инициализация исходного множества }end forif тп = п thenreturn Л[1..п] { единственное подмножество }end ifp : = n { p — помер первого изменяемого элемента }while р ^ 1 doyield A[l..n] { очередное подмножество в первых п элементах массива А }if А[п\ = тп thenр: = р — 1 { нельзя увеличить последний элемент }elseр:=тъ { можно увеличить последний элемент }end ifif р ^ 1 thenfor i from n downto p doA[i}: = A\p] + i — p + 1 { увеличение элементов }end forend ifend whileЗаметим, что в искомой последовательности n-элементпых подмножеств (каждое из которых является возрастающей последовательностью пчисел из диапазона 1..ш) вслед за последовательностью ( a i , .
. . ,а п ) следует последовательность ( b i , . . . , bn) = ( a i , . . . , a p _i, a p + 1, a p + 2 , . . . , a p + n — p + 1), гдеp — максимальный индекс, для которого bn = ар+п—р+1 ^ тп. Другими словами,следующая последовательность получается из предыдущей заменой некоторогоколичества элементов в хвосте последовательности идущими подряд натуральными числами, по так, чтобы последний элемент не превосходил тп, а первыйизменяемый элемент был на 1 больше, чем соответствующий элемент в предыдущей последовательности. Таким образом, индекс р, начиная с которого следуетизменить «хвост последовательности», определяется по значению элемента А[п].Если А[п] < тп, то следует изменять только А[п], и при этом р: = п. Если же ужеА[п] = тп, то нужно уменьшать индекс р : = р— 1, увеличивая длину изменяемогохвоста.•ОБОСНОВАНИЕ,5.3.
Биномиальные коэффициенты193Пример Последовательность п-элемептпых подмножеств га-элемептиого множества в лексикографическом порядке для п = 3 и тп — 4: (1,2,3), (1,2,4), (1,3,4),(2,3,4).ОТСТУПЛЕНИЕДовольно часто встречаются задачи, в которых требуется найти в некотором множестве элемент, обладающий определёнными свойствами. При этом исследуемое множествоможет быть велико, а его элементы устроены достаточно сложно. Если неизвестно заранее, как именно следует искать элемент, то остаётся перебирать все элементы, пока непопадётся нужный (поэтому такие задачи называют переборными).При решении переборных задач совсем не обязательно и, как правило, нецелесообразно строить всё исследуемое множество (пространство поиска) в явном виде. Достаточноиметь итератор (см.
1.3.8), перебирающий элементы множества в подходящем порядке. Фактически, алгоритмы 1.2, 5.2 и 5.3 являются примерами таких итераторов длянекоторых типичных пространств поиска.Чтобы использовать эти алгоритмы в качестве итераторов при переборе, достаточно вставить вместо оператора yield проверку того, что очередной элемент является искомым.5.3.6.
Мультимножества и последовательностиВ 5.1.5 показано, что число n-элемептных подмножеств m-элементного множества равно С(т,п). Поскольку тг-элементные подмножества — это п-элемептпые индикаторы (см. 1.1.4), ясно, что число n-элемептпых индикаторов над тэлемептпым множеством также равно С(т,п).Общее число n-элемептпых мультимножеств [ж™1,..., х^ п ], в которых п\ + . . . ++ п ш = п, над га-элементным множеством X — {х\,..., хт} нетрудно определить,если заметить, что это число способов разложить п неразличимых предметов пога ящикам, то есть число сочетаний с повторениями V(m,n) = С(п + т — 1,п).Пусть задано множество X = {rri,... ,Рассмотрим последовательность Y == (2/1,...
,уп), где У г (yi е X) и в последовательности Y элемент Xi встречается щ раз. Тогда мультимножество X = [ж" 1 ,..., х™"1} называется составомпоследовательности Y. Ясно, что состав любой последовательности определяетсяоднозначно, по разные последовательности могут иметь один и тот же состав.Пример Пусть X = {1,2,3}, Yi = (1,2,3,2,1), У2 = (1,1,2,2,3). Тогда последовательности У] и Y2 имеют один и тот же состав X — [ l 2 ^ 2 ^ 1 ] .ОТСТУПЛЕНИЕИз органической химии известно, что существуют различные вещества, имеющие один итот же химический состав. Они называются изомерами.194Глава 5. Комбинаторика'Очевидно, что все последовательности над множеством X = {х\,... , х т } , имеющие один и ТОТ же состав X = [ж™1,...,имеют одну и ту же длину п = п\ ++ .
. . + n m . Обозначим число последовательностей одного состава С(щ щ,...,пт).ТЕОРЕМАп'C(n;ni,...,nTO) = — — :г.nil. ..пт\Рассмотрим мультимножество X — [х™1,...,которое можно записать в форме последовательности (х\,... ,х\,х2,...,х2,...,хт,...,хт),где элемент Хг встречается щ раз. Ясно, что все последовательности одного состава X получаются из указанной последовательности перестановкой элементов.При этом, если переставляются одинаковые элементы, например, Х{, то получается та же самая последовательность.
Таких перестановок щ\. Таким образом,общее число перестановок ri\\.. .nm\C(n;n\,...,n m ). С другой стороны, числоперестановок п элементов равно п\.•ДОКАЗАТЕЛЬСТВО5.3.7. Мультиномиальные коэффициентыЧисла C ( n ; n i , . . . ,пт) встречаются в практических задачах довольно часто, поскольку обобщают случай индикаторов, которые описываются биномиальными коэффициентами, на случай произвольных мультимножеств. В частности,справедлива формула, обобщающая формулу бинома Ньютона, в которой участвуют числа C ( n ; n i , . . . ,n m ), поэтому их иногда называют мультиномиальнымикоэффициентами.ТЕОРЕМА(XI + .
. . + хт)п=С ( П ; Щ , . . . , П^Т~ПтКni+...+7lm=nДОКАЗАТЕЛЬСТВОИндукция по т. База: при т = 2 по формуле бинома Ньютонаимеем7171г=0Iп\г=0 ^>п\,'тц+п2=пп^С{п\пх,... ,пт-Х)хп^7li + ...+nm_i=7lРассмотрим (х\ + ... + хт)п. Имеем:п(xi + . . . + х т ) п = ((a;i + .
. . + x m _ i ) + х Тп ) п = ^ C ( n , i ) ( x i + . . . +Пусть теперь ( x i + . . . + х ш _1) =•••.=г=0i—0(<!(„_»)!IVVZ,\ni+...+nm_i=t'71m l - . - nm ^ i ! ^х^-'-х^Ах"-*m-l \xm-X), ..n!>!=E„ ^ ^E.»!(n-«)!»i!---n=0 7ll+...+n _l=lmm-i!1m-'m1955.4. Разбиенияп\£Щ +... +Т1т _ 1 +пт=711nil • • - n m _ i ! n m !Im-l n„Хm—l1 XТтп »J•где n m : = п - г.СЛЕДСТВИЕп!=7li+... + nm=nщ ! • • -!пш!ДОКАЗАТЕЛЬСТВОТП=тп(1 + . .
. + L)N =^тп разV—;П1— ^ —7,++Г, —П ^ni+...+n -nГ1''П 1m1П Т=mE—1 i—гn!,_,пniH 1-nm=nПример При игре в преферанс трём играющим сдаётся по 10 карт из 32 карти 2 карты остаются в «прикупе». Сколько существует различных раскладов?С(32; 1 0 , 1 0 , 1 0 , 2 ) = ^32!^=2753294408504640.5.4. РазбиенияРазбиения не рассматривались среди типовых комбинаторных конфигурацийв разделе 5.1, потому что получить для них явную формулу не так просто,как для остальных. В этом разделе отмечаются основные свойства разбиений,а окончательные формулы приведены в 5.6.3.5.4.1.
ОпределенияПусть Ъ = { B i , . . . , Вп} — разбиение множества X из тп элементов на п подмножеств:71Bi с X,( J Bi = X,Bi ф0,Bin Bj = 0при г ф- j.i= 1Подмножества Bi называются блоками разбиения.Между разбиениями с непустыми блоками и отношениями эквивалентности существует взаимно-однозначное соответствие (см. 1.7.1). Если Е\ и Е2 — дваразбиения X, то говорят, что разбиение Е\ есть измельчение разбиения Е2, есликаждый блок Е2 есть объединение блоков Е\. Измельчение является частичнымпорядком па множестве разбиений.196Глава 5.
Комбинаторика'5.4.2. Числа Стирлинга второго родаЧисло разбиений га-элемептпого множества па п блоков называется числом Стирлинга1 второго рода и обозначается S(m,n). По определению положимТЕОРЕМА 1S(m,S(m, rn) = f 1,S(ra, 0) = f 0при m > 0,5(0,0) = f l ,5(ш,п) = f 0при п > га.п)= S{m-1, п -1) + nS(m-1,n).Пусть Ъ — множество всех разбиений множества М : = { 1 , .
. . , га}на п блоков. ПоложимДОКАЗАТЕЛЬСТВОЪц = {Х еЪ\ЗВеХ(В={т})},Ъ2 : = {X е Ъ \ -.ЗВ е X (Б ={ш})},то есть в Ъ\ входят разбиения, в которых элемент т образует отдельный блок, а вЪ2 — все остальные разбиения. Заметим, что Ъ2 = {X е Ъ \ т е X => \Х\ > 1}.Тогда Ъ = BiUB 2 , ®iПВ 2 = 0- Имеем |®i| = S{m-l,n-1),\Ъ2\ = п 5 ( ш - 1 , п ) ,так как все разбиения Ъ 2 получаются следующим образом: берём все разбиениямножества {1,..., га — 1} на п блоков (их S(m— 1, п)) и в каждый блок по очередипомещаем элемент га.
Следовательно,5(m,n) = \Ъ\ = |®i| + |B 2 | = 5 ( m - l , n - l ) + n 5 ( m - l , n ) .ТЕОРЕМА 2S(m,n)=•rn— 1C(m - 1, i)S{i, n - 1).i—n—lПусть Ъ — множество всех разбиений множества М:—{1,...,га}на п блоков. Рассмотрим семейство В: = {В с 2 м | га 6 В}. Тогда Ъ = (J Ве^Ъв,где Ъв: = {X \ X 6 Ъ & В е X}, причём Ъв> П Ъв» = 0, если В'_ф В". ПустьВ еВиЬ: = \В\. Тогда \ЪВ\ = S(m-b,n1). Заметим, что \ {В G В \ Ь= |В|}| == С (га - 1 , 6 - 1 ) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
