Основы дискретной математики В.А. Осипова (552659), страница 17
Текст из файла (страница 17)
которой а1 элементов первого типа, пз элементов второго типа, ..., а„элементов и-го типа. Следовательно, число решений равно С„'. В частности, число целочисленных решений уравнения 3.1. Комбннаторные схемы и! Сь(а — ь) а!( а ) ~ ~а. 10! А = Сззз = = 2520 2!3!5! 8! 1У(3, 4, 1) = ...
= 280. п| п1ае 'аа и1 из '''пй. (3.4) 92 Глава 3. ОСНОВНЫЕ ПОНЯТИЯ КОМБИНАТОРИКИ 3 а м е ч а н и е 1. Задачу о числе разбиений можно интерпретировать следующим образом. Сколькими способами можно разложить п предметов по й ящикам так, чтобы в первом ящике оказался п1 предмет, во втором — пз,..., в Й-и — пь предметов, где п1+пз+ . +па = и? Число способов равно 1у(пм пз, ..., пь). 3 а м е ч а н и е 2.
Число ?У(пм пз, ..., пе) равно числу перестановок с повторениями из п элементов, среди которых п1 равных между собой, пз равных между собой, ..., пе равных между собой и п1 + из+ + пе = и. Пример 3.6. 1) Сколькими способами можно раскрасить восемь комнат дома так, чтобы три комнаты были окрашены в желтый цвет, четыре в голубой и одна в серый? Множество комнат Х состоит из восьми элементов, каждое раскрашивание разбивает Х на три подмножества Хм Хз, Хз, где Х1 подмножество комнат, окрашенных в желтый цвет, Хз — в голубой и Хз — в серый. Число раскрашиваний равно 2) При игре в домино четыре игрока делят поровну 28 костей. Сколькими способами это можно сделать? 28! Ответ; Ф(7, 7, 7, 7) = = 472518347558400.
7!7!7!7! Формулу (3.2) для числа разбиений можно использовать при определении коэффициентов полиномиалъной формулы: (х1+хз+' ' '+хь) =,~ Са1ах п~,х1 хз хь . (З.З) и1-+а2+-.+па=а Раскрывая скобки в левой части этого равенства с использованием закона дистрибутивности видим, что число одночленов в которых х1 встречается п1 раз, хз встречается пз раза, ..., хь встречается пь раз, где п1+из+ +пь = п, совпадает с числом способов, которым мы можем разбить п элементов множества на подмножества из им пз, ..., пе элементов, т.
е., используя формулу (3.2) Формула бинома Ньютона является частным случаем поли- номиальной формулы и имеет вид: (а+ 5) = ~Сса — ~5 й=о аа + С а~-~5+ С аа ~5 + " + С~~ — 1а~ь — 1 + ~ласб (3 5) поскольку в формуле (3.3) в данном случае Пример 3.7. Найти коэффициент А в одночлене АхЯхз~, полученном после приведения подобных членов в выражении (х1+ хз+ хз)1е. В соответствии с формулой (3.4) 3.1.4. Хлассифицирование.
'Уриовые схемы Под классифицированием понимают распределение объектов из некоторого множества по классам так, что каждый объект может принадлежать только одному классу (причем некоторые классы могут быть пустыми). В комбинаторике часто интерпретируют класснфицирование как размещение (распределение) объектов по ячейкам. При этом объекты могут быть различимыми и неразличимыми, упорядоченными и неупорядоченными, ячейки — различимыми и неразличимыми, упорядоченными и неупорядоченными. Рассмотрим некоторые типы распределений объектов по ячейкам. 1. с1исло распределений т различимых и неупорядоченных объектов по и различимым и неупорядоченным ячейкам равно и'. Действительно, пусть т объектов перенумерованы от 1 до т. Объект с номером 1 можно поместить в п ячеек ровно п способами, объекты с номерами 1 и 2 — пз способами, ..., все т объектов — и" способами.
2. Число распределений т различимых и неупорядоченных объектов по и различимым и неупорядоченным ячейкам так, 95 3.2. Некоторые методы пересчета т! Ж(тих, ...,т )= т1 !тз ! тп! 94 Глава 3. ОСНОВНЫЕ ПОНЯТИЯ КОМБИНАТОРИКИ что т: попадают в первую ячейку, та — во вторую, ..., тп — в и-ю ячейку, где т1+то+ . +т„= т, равно Это следует из Замечания 1 к Утверждению 3.4. 3.
Число распределений т неразличимых объектов по и различимым и неупорядоченным ячейкам равно С„". Действительно, расположим т объектов на одной строке и между ними поставим и — 1 черточку, соответствующую распределениям на ячейки. Тогда число способов расставить эти и — 1 черточки между т объектами равно Ст 1 „, т. е. С„'. 4. Число распределений т различимых и упорядоченных объектов по и различимым и неупорядоченным ячейкам равно т!С„'.
Разместим т неразличимых объектов по и различимым и неупорядоченным ячейкам. Затем рассмотрим объекты как различимые и переставим их. Число способов перестановки объектов равно т!. С учетом п. 3 по правилу произведения общее число искомых распределений равно т!С,",. В теории вероятностей рассматриваются комбинаторные схемы, использующие терминологию выбора т шаров из урны с и шарами.
Рассмотрим некоторые случаи. 1. Упорядоченный выбор без возвращения т шаров из урны с и различными шарами (т < и). Число способов выбора равно числу упорядоченных (и, т) выборок без повторений элементов и.' А"„= (и — т)! 2. Неупорядоченный выбор без возвращения т шаров из урны с и различными шарами (т < и). Число способов выбора равно числу неупорядоченных (и, т) выборок без повторений и! С„' = т! (и — т)! 3. Упорядоченный выбор с возвращением т шаров из урны с и различными шарами, Число способов выбора равно числу упорядоченных (и, т) выборок с повторением Ат — ит 4. Неупорядоченный выбор с возвращением т шаров из урны с и различными шарами.
Число способов выбора равно числу неупорядоченных (и, т) выборок с повторением Сп Сп+т-1' Задачи и упражнения 1. В первенстве участвуют 19 команд. Сколькими способами могут распределиться золотые, серебряные и бронзовые медали? 2. На панель сейфа нанесено двенадцать букв. Шифр (кодовое слово) состоит из четырех букв. Сколько можно сделать попыток отгадать код? 3. Код азбуки Морзе использует пятизначные шифры из точки и тире. Почему для кодировки русских слов нельзя обойтись меньшим числом знаков? 4. Из колоды, состоящей из 52 карт выбрали 8 карт. В скольких случаях среди них окажутся: а) ровно один туз; б) хотя бы один туз; в) ровно два туза? 5. Имеется 20 монет достоинством 1, 5 и 10 копеек.
Сколькими способами можно составить из них комбинации из трех монет по одной копейке, пяти монет по пять копеек и двенадцать монет по десять копеек? 6. Найти коэффициент А в одночлене Аазбзс4, полученном после приведения подобных членов в выражении (а+ 5+с)~(а~+ + бт+ с2)4 3.2. Некоторые методы пересчета 3.2.1. Формула включений и исключений Рассмотрим некоторый общий метод пересчета, основанный на следующем принципе: с любым свойством Г некоторых объектов, составляющих множество А, можно связать разбиение множества А на подмножество А1 объектов, обладающих свойством Р, и подмножеством объектов, не обладающих свойством Р. Пусть Х вЂ” конечное множество, Хы Хз, ..., Մ— его подмножества такие, что Х = ! ! Х,.
Тогда число элементов т=1 ~Х~ множества Х можно выразить через число элементов !Х;~ 97 3.2. Некоторые методы пересчета 96 Глава 3. ОСНОВНЫЕ ПОНЯТИЯ КОМБИНАТОРИКИ подмножеств Хдп т' = 1, ..., н по следующей формуле включений и исключений Теорема 3.1 (форлтула включений и исключений). ~Х~ = ~ХД ОХ, О" ОХп~ = (~ХД~+ ~Х2~+" + (Хп~)- — ((Хд Л Х2) + (Хд Л Хз) + + )Х д Л Хп!)+ +(1х лх лх ~)+" +(!Х„2лх„длх„!) — " " +( — 1)"+')Хд ЛХ,Л" ЛХп~. (З.б) Доказательство проведем индукцией по числу подмножеств и.
При и = 2 очевидно, что ~хд о Х2| = ~хд(+ ~Х2~ — ~хд л х2(. Предположим, что утверждение верно для и — 1-подмножеств, докажем его для п > 3 подмножеств. Разобьем подмножества множества Х на две группы: к первой отнесем подмножества Хд, Х2, ..., Хп д, ко второй— Хп. Используя закон дистрибутивности, получим: ~ХдОХ2О" ОХп~= ~(ХдОХ2О" ОХп,) ОХп)= = !Хд ох,о" ох„д~+)х„)— — )(Хд ОХ2О" ОХп д) Лхп! = = (хд ох2о "ох„д(+)х„)- — /(Хд Л Хп) О (Х2 Л Хп) О " О (Хп, Г1 Хп) /. (3.7) По индуктивному предположению ~хд о х, о " о хп, ) = ~(х, о х, о " о хп, ~ = = (~хд~+ )Х2~+" + ~х„д))— — ()Хд Лхг!+!Хд ЛХз!+ + )Хп — 2 ЛХп д!) + ' ' + ( — 1) 1Х! л Х2 Г1 ' ' ' л Хп — д 1. (3.8) Применим индуктивное предположение к и — 1 подмножеству вида Хд Л Хп, Х2 Л Хп, ..., Хп д Л Хп.
Тогда ~(Хд л Хп) о (Х, л Хп) о о (Хп, л Хп)~ = = )Хд Г1 Хп! + )Х2 Л Хп ! + + )Хп д Г1 Хп)— — (/Хд Л Х2 Л ХЗ() + " + ()Хп 2 Л Хп д Л Хп )) — " . " +( — 1)"~х, гдх,л" лх„~. (з.9) Из соотношения (3.7) с учетом (3.8) и (3.9) получим искомую формулу (3.6). О лед от в и е. Пусть Х вЂ” конечное множество, Хд, Хэ, ... ..., Х вЂ” система его подмножеств.
Тогда (Х~(хд ОХ2О "Охп)! = )Х! — )Хд( —" — )Хп(+ + ~ХД Л Х2~ + "+ ~Х„Д Л Х„+ " "+ (-1)")Хд Л Х2 Л " Л Х„!. (3.10) Рассмотрим множество Х = Хдд(хд О Х2 О -. О Хп). Тогда Х = (ХдОХ2О'''Ох )Г1Х ХЛ(хдОХ2О' 'ОХ ) = а и )Х! = )Хд О Х2 О О Х„(+ (Х(. Отсюда ~ХД,(ХД ОХ2О "ОХп)~ = ~Х! — ~ХД ОХ2О "ОХ„~. Применяя формулу (3.6) к множеству ЛдОХ2О.
ОХп, получим искомую формулу (3.10). Приведем следуюшую интерпретацию следствия к формуле включений и исключений. Пусть, элементы подмножества Х; множества Х обладают свойством Р;, г = 1, ..., и (т. е. на Х заданы одноместные предикаты Г;, и Х; — область истинности предиката Р;). ОбознаЧИ' Чвр Ад;т,е 21 22 2 ЧИ О ЭЛЕМЕНТОВ Х, КОтОрЫЕ Обладают свойствами Р;д, Р;2, ..., Рдь и не обладают свойствами дд, 22, ..., д,. Тогда из (3.10) следует, что число элементов, не обладающик ни одним свойством Рд, Р2,, Га равно Ад2 „-=!Х~ — Ад — — Ап+ Аде+ Аьз+ " +Ап,п —" +( — 1)пАив „. (З.П) 99 98 Глава 3.
ОСНОВНЫЕ ПОНЯТИЯ КОМБИНАТОРИКИ 3.2. Некоторые методы пересчета Пример 3.8. а) На множестве Х = (О, 1, ..., 10) заданы три свойства: Гл — «х Н Х и х — четное», Г2 — «х Е Х и х > 6», Гз — «х е Х и 2 < х < 8». Подсчитаем число элементов, не обладающих ни одним свойством А12з = ~Х~ — Ал — Аз — Аз+ Алз+ Алз+ Азз — Алзз Отсюда А12з = 11 — 6 — 4 — 5+ 2+ 2+ 1 — 0 = 1. Действительно, единственный элемент множества Х не обладающий ни одним из указанных свойств, это число 1. б) В деканат даны сведения о 45 студентах, в том числе, о 38 сдавших сессию в срок. 20 студентов дополнительно занимаются английским языком, в том числе 18 сдавших сессию в срок. Спортом занимаются 25 студентов, из них 16 сдавших сессию в срок.
Среди 13 спортсменов, занимающихся английским, 11 сдавших сессию в срок. Почему данные сведения неверны? Рассмотрим три свойства: Гл — сдать сессию в срок; Гз — дополнительно заниматься английским, Гз — заниматься спортом. Число студентов, не обладающих ни одним из этих свойств АИз — — 45 — 38 — 20 — 25+ 18+ 16+ 13 — 11 = — 2 < О. Отрицательным числом ответ быть не может, следовательно, в данных сведениях содержится внутреннее противоречие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
