Новиков Ф.А. Дискретная математика для программистов (860615), страница 35
Текст из файла (страница 35)
, п } , У = {1,... ,m}, F = (F(l),...,F(n)), 1Сколько существует функций F, удовлетворяющих заданным ограничениям?ЗАМЕЧАНИЕБольшей частью соответствие конфигураций, описанных на «языке ящиков» и на «языке функций», очевидно, поэтому доказательство правильности способа подсчёта (выводформулы) можно провести на любом языке. Если сведение одной модели к другой неочевидно, то оно включается в доказательство.5.1.2. РазмещенияЧисло всех функций (при отсутствии ограничений), или число всех возможныхспособов разместить п предметов по т ящикам, называется числом размещенийи обозначается U(m,n).1815.1.
Комбинаторные задачиТЕОРЕМАU(m,n) = тп.Поскольку ограничений нет, предметы размещаются независимо друг от друга и каждый из п предметов можно разместить га способами.•ДОКАЗАТЕЛЬСТВОЗАМЕЧАНИЕВ комбинаторных задачах часто используются два правила, которые называются правилом суммы и правилом произведения. Неформально эти правила можно сформулироватьследующим образом. Пусть существуют некоторые возможности построения комбинаторной конфигурации. Если эти возможности взаимно исключают друг друга, то их количества следует складывать, а если возможности независимы, то их количества следуетперемножать.Пример При игре в кости бросаются две кости и выпавшие на верхних граняхочки складываются.
Какова вероятность выбросить 12 очков? Каждый возможный исход соответствует функции F: {1,2} —» {1,2,3,4,5,6} (аргумент — номеркости, результат — очки на верхней грани). Таким образом, всего возможно[/(6,2) = б 2 = 36 различных исходов. Из них только один (6 + 6) даёт двенадцатьочков. Вероятность 1/36.5.1.3. Размещения без повторенийЧисло ипъективных функций, или число способов разместить п предметов поm ящикам, пе более чем по одному в ящик, называется числом размещений безповторений и обозначается А(т,п), или [т]п, или (т) п .ТЕОРЕМАТП)А(тп,п) = -/—т.(Ш — 77,)!Ящик для первого предмета можно выбрать тп способами, длявторого — тп- 1 способами и т.
д. Таким образом,тп\А(тп, п) = тп • (тп — 1) •... • (тп — п + 1) =—-.(тп — п)!По определению считают, что А(тп,п) = f 0 при п > тп и А(тп, 0) =f 1.ДОКАЗАТЕЛЬСТВООТСТУПЛЕНИЕПростые формулы, выведенные для числа размещений без повторений, дают повод поговорить об элементарных, но весьма важных вещах. Рассмотрим две формулы:777,!А(тп, п) = тп • (ш — 1) • ... • (m — п + 1) и А(тп,п) =—гт(ш — п)\Формула слева выглядит сложной и незавершённой, формула справа — изящной и «математичпой». Но формула — это частный случай алгоритма. При практическом вычислениилевая формула оказывается намного предпочтительнее правой.
Во-первых, для вычисления по левой формуле потребуется тп—1 умножение, а по правой — 2т — ть — 2 умноженийи одно деление. Поскольку п < т, левая формула вычисляется существенно быстрее. Во-•182Глава 5. Комбинаторика'вторых, число А(тп, п) растёт довольно быстро и при больших т и п может не поместитьсяв разрядную сетку. Левая формула работает правильно, если результат помещается в разрядную сетку.
При вычислении же по правой формуле переполнение может наступить«раньше времени» (то есть промежуточные результаты пе помещаются в разрядную сетку, в то время как окончательный результат мог бы поместиться), поскольку факториал —очень быстро растущая функция.Пример В некоторых видах спортивных соревнований исходом является определение участников, занявших первое, второе и третье места. Сколько возможноразличных исходов, если в соревновании участвуют п участников? Каждый возможный исход соответствует функции F: {1,2,3} —> {l..n} (аргумент — номерпризового места, результат — помер участника).
Таким образом, всего возможноА(п, 3) = п(п - 1)(п - 2) различных исходов.5.1.4. ПерестановкиЕсли |Х| = |У| = п, то существуют взаимно-однозначные функцииf\X—>Y.Число взаимно-однозначных функций, или число перестановок п предметов, обозначается Р{п).ТЕОРЕМАР(п)ДОКАЗАТЕЛЬСТВО=п\.Р(п) = А(п,п) = п-(п-1)•... •(п-п+1) = п- (п-1) •... • 1 = п!.•Пример Последовательность £ = (Ei,..., Ет) непустых подмножеств множества Е (£ с. 2е, Ei с Е, Ei ф 0 ) называется цепочкой в Е, еслиУг € l..(m - 1) {Ei С Ei+l k Ei фЕш).Цепочка £ называется полной цепочкой в Е, если |£| = |Е\.
Сколько существует полных цепочек? Очевидно, что в полной цепочке каждое следующееподмножество Ei+i получено из предыдущего подмножества Е{ добавлениемровно одного элемента из Е и таким образом, \Ei\ = 1, \Е%\ — 2, . . . , \Ет\ ~\Е\ ~ га. Следовательно, полная цепочка определяется порядком, в котором элементы Е добавляются для образования очередного элемента полной цепочки.Отсюда количество полных цепочек — это количество перестановок элементовмножества Е, равное ml.5.1.5. СочетанияЧисло строго монотонно возрастающих функций, или число размещений п неразличимых предметов по тп ящикам не более чем по одному в ящик, то естьчисло способов выбрать из га ящиков п ящиков с предметами, называется числомсочетаний и обозначается C(m,n), илиСили1835.1.
Комбинаторные задачиТЕОРЕМАС(тп,п)=ш !п\(т - п)!'ДОКАЗАТЕЛЬСТВО[Обоснованиеформулы] Сочетание является размещением без повторений неразл и ч и м ы х предметов. Следовательно, число сочетаний определяется тем, какиеящики заняты предметами, поскольку перестановка предметов при тех же запятых ящиках считается одним сочетанием. Таким образом,С(т, п) =A(rri, п)Р(п)гп\п\{т — п)\'[Сведение моделей] Число сочетаний является числом строго монотонно возрастающих функций, потому что любая строго монотонно возрастающая функция F: 1..п —• 1..Ш определяется набором своих значений, причём 1 ^ F( 1) << ... < F(n) ^ т. Другими словами, каждая строго монотонно возрастающаяфункция определяется выбором п чисел из диапазона 1 ..т. Таким образом, числострого монотонно возрастающих функций равно числу n-элементных подмножеств га-элементного множества, которое, в свою очередь, равно числу способоввыбрать п ящиков с предметами из га ящиков.•По определению C(m, п) = f 0 при п > т.Пример В начале игры в домино каждому играющему выдаётся 7 костей изимеющихся 28 различных костей.
Сколько существует различных комбинацийкостей, которые игрок может получить в начале игры? Очевидно, что искомое число равно числу 7-элементных подмножеств 28-элемептпого множества.Имеем:С ( 2 8 7)6 ( 2 8 , 7 )28!__ 28.27.26.25-24.23.22 _" 7!(28-7)! ~7.6.5.4.3.2.1~1 184040'5.1.6. Сочетания с повторениямиЧисло монотонно возрастающих функций, или число размещений п неразличимых предметов по т ящикам, называется числом сочетаний с повторениямии обозначается V{m,n).ТЕОРЕМАV(m,п)= С(п+ га -1, п ) .Монотонно возрастающей функции / : 1..п —• l..m однозначносоответствует строго монотонно возрастающая фуикция / ' : l..n —> l..(n + т - 1).Это соответствие устанавливается следующей формулой: f'(k) = f(k) + k— 1.•ДОКАЗАТЕЛЬСТВО184Глава 5.
Комбинаторика'Пример Сколькими способами можно рассадить п вновь прибывших гостейсреди га гостей, уже сидящих за круглым столом? Очевидно, что между га сидящими за круглым столом гостями имеется га промежутков, в которые можнорассаживать вновь прибывших. Таким образом, число способов равно,(га + п - 1)!члI/(га, п) — СЧга + п - 1,п) = —-гт-.пит — 1)!5.2. ПерестановкиДля вычисления количества перестановок в 5.1.4 установлена очень простая формула: Р(п) = п\. Применяя эту формулу при решении практических задач, песледует забывать, что факториал — это очень быстро растущая функция, в частности, факториал растёт быстрее экспоненты. Действительно, используя известнуюиз математического анализа формулу Стирлингаппу/Ъгп,е-п< п! < ппу/Ъгп,нетрудно показать, что5.2.1.
Графическое представление перестановокВ 2.2.5 рассматриваются взаимно-однозначные функции (перестановки), которые удобно задавать таблицами подстановки.В таблице подстановки нижняя строка (значения функции) является перестановкой элементов верхней строки (значения аргумента). Если принять соглашение,что элементы верхней строки (аргументы) всегда располагаются в определённомпорядке (например, по возрастанию), то верхнюю строку можно не указывать —подстановка определяется одной нижней строкой. Таким образом, подстановки(таблицы) взаимно-однозначно соответствуют перестановкам (функциям). Напомним (см. 2.2.5), что множество перестановок образует группу относительносуперпозиции.Перестановку / (и соответствующую ей подстановку) элементов 1,...
,п будемобозначать (а\,... ,ап), где а* — все различные числа из диапазона 1 ..п.Иногда перестановки удобно представлять в графической форме, проводя стрелки от каждого элемента х к элементу f(x).ПримерГрафическое представление перестановки (см. 2.2.5)/ =показано на рис. 5.1.1855.2. ПерестановкиGDGDРис. 5.1. Графическое представление перестановкиЕсли задана перестановка / , то циклом называется последовательность элементовх о , . . . , Xk, такая, чтоxi+i,0 ^ i < к,=XQ,г — к.Цикл длины 2 называется транспозицией.ЗАМЕЧАНИЕИз графического представления перестановки наглядно видно происхождение термина«цикл».5.2.2. ИнверсииЕсли в перестановке / = (а\,..., ап) для элементов а^ и a,j имеет место неравенство at > aj при i < j, то пара (а г , а3) называется инверсией. Обозначим 1 ( f ) —число инверсий в перестановке / .ТЕОРЕМАПроизвольную перестановку f можно представить в виде суперпозиции 1 ( f ) транспозиций соседних элементов.Пусть f — ( a i , .
. . , 1 , . . . , a n ). Переставим 1 на первое место, меняя её местами с соседними слева элементами. Обозначим последовательностьэтих транспозиций через t\. При этом все инверсии (и только они), в которыхучаствовала 1, пропадут. Затем переставим 2 на второе место и т. д. Таким образом, / о t\ О . . . о tn = е и по свойству группы / = t~l о . . . о г" 1 , причёмДОКАЗАТЕЛЬСТВО|tl| + M+ . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
