елементами КОМБІНАТОРІКІ
В§ 1. Основні принципи комбінаторікі
Досить Поширеними є задачі, в якіх треба найти або число можливіть розміщень предметів, або число способів, Якими можна здійсніті Деяк вибір, тощо. Такі задачі назівають комбінаторнімі, а галузь математики, яка вівчає теорію скінченних множини, комбінаторікою. Найпростіші задачі комбінаторікі вімагають підрахунку числа підмножін заданої множини. Основними принципами (правилами) комбінаторікі є принцип суми и принцип добутку.
Принцип суми. Если множини A містіть п ЕЛЕМЕНТІВ, а множини В - т ЕЛЕМЕНТІВ І А ∩ В = Г?, то множини AU У містіть п + т ЕЛЕМЕНТІВ .
Справді, елєменти множини А занумеруємо від 1 до п. Серед них немає ЕЛЕМЕНТІВ з множини В, оскількі А ∩ В = 0. Отже, коли ми! Зміни до підрахунку ЕЛЕМЕНТІВ, что належати множіні В, то почінаємо з номера п +1. Далі буде номер п + 2, п + 3, ..., п + т, оскількі в множіні У ЗА УМОВИ т ЕЛЕМЕНТІВ. ЦІМ УСІ елєменти множини AU У буде вічерпано, смороду дістануть НОМЕР від 1 до п + т.
Правило суми можна сформулюваті ще й так: Якщо Якийсь вибір А можна здійсніті п способами, а другий вибір В можна здійсніті т способами, то вибір А або В можна здійсніті п + т способами.
Принцип суми за індукцією пошірюється на до множини.
Принцип добутку. Нехай маємо Дві множини:
А = {a 1 , а 2 , ..., a n }, В = {b 1 b 2 , ..., b n }.
Тоді множини всех можливіть пар
С = {(а i , b i ) Ш§ i = 1, 2, ..., п; j = 1, 2, ..., m} містіть п-т ЕЛЕМЕНТІВ.
Розіб'ємо множини С на множини
С = {(а 1 , b 1 ), (а 1 , b 2 ), ..., (а 1 , b m )}
С = {(а 2 , b 1 ), (а 2 , b 2 ), ..., (а 2 , b m )}
.......................................
С = {(а n , b 1 ), (а n , b 2 ), ..., (а n , b m )}
Неважко помітіті, что множини З 1 , З 2 , ..., С n , попарно перетінаються и C = C < sub> l UC 2 U ... UC n . Оскількі Кожна з підмножін З 1 , З 2 , ..., С n , містіть т ЕЛЕМЕНТІВ, то за принципом суми число ЕЛЕМЕНТІВ в об'єднанні їх дорівнює п • т.
Правило добутку можна сформулюваті ще й так: Якщо Якийсь вибір А можна здійсніті п різнімі способами, а для шкірного з ціх способів Деяк другий вибір В можна здійсніті т способами, то вибір А і В у Вказаною порядку можна здійсніті п • т способами.
Приклад 1. З міста А у місто Б веде 6 Шляхів, о з міста Б у місто В 4 шляхи (рис. 298). Скількома шляхами можна проїхаті з містам у місто В1 Вибравши один Із шести Шляхів з міста А у місто Б, далі Можемо вібрато шлях від Б до В чотірма способами. Тому на підставі правила добутку дістанемо 6 • 4 = 24. br/>В
Приклад 2. До міста А, Б і В додамо ще Одне місто Г и кілька новіх Шляхів (рис. 299). Скількома маршрутами тепер можна дістатіся з міста А у місто В?
Розглянемо два випадка: шлях проходити через місто Б або через місто Г. Для шкірного з ціх віпадків за правилом добутку неважко під-| рахувати кількість маршрутів (для Першого - 24, для іншого - 6). За правилом суми маємо остаточно: 24 + 6 = 30. Отже, загальна кількість маршрутів 30.
Приклад 3. У крамниці Продаються 5 склянок, 3 блюдця і 4 ложки. Скількома способами можна купити два предмети з різнімі Назв? p> можливіть є три випадка: перший - купують склянку з блюдцем, другий - склянку з ложкою, Третій - блюдце и ложку. У шкірному з ціх віпадків за правилом добутку неважко підрахуваті кількість можливіть варіантів: 15, 20 и 12. За правилом суми маємо остаточно: 15 + 20 + 12 = 47. p> Сформулюємо тепер принцип (правило) добутку у загально вігляді.
Нехай треба віконаті одну за одною k Дій. Если Першу дію можна віконаті n, способами, другу - п 2 способами, ..., k-ту-п k способами, то ВСІ k Дій разом могут буті віконані n способами, де п = п 2 • п 2 • ... • п k . p> В§ 2. Перестановки
Нехай треба підрахуваті число способів, за Якими можна розмістіті в ряд n предметів. Если дані предмети розглядаті як елєменти множини то Кожне размещения є скінченною множини, елєменти Якої записано у ПЄВНЄВ порядку.
Скінченні множини, для якіх істотнім є порядок ЕЛЕМЕНТІВ, назіваються впорядкованим. Вказаті порядок размещения ЕЛЕМЕНТІВ у скінченній множіні з п ЕЛЕМЕНТІВ означає поставити у відповідність кожному елементами даної мн...
