Елементи комбінаторики. Початки теорії ймовірностей

У цьому параграфі розглянемо теореми про поводження суми великої кількості випадкових величин. Виявляється, що за деяких порівняно загальних умов сумарна

Елементи комбінаторики. Початки теорії ймовірностей

Методическое пособие

Математика и статистика

Другие методички по предмету

Математика и статистика

Сдать работу со 100% гаранией

ЕЛЕМЕНТИ КОМБІНАТОРИКИ

 

§ 1. Основні принципи комбінаторики

 

Досить поширеними є задачі, в яких треба знайти або число можливих розміщень предметів, або число способів, якими можна здійснити деякий вибір, тощо. Такі задачі називають комбінаторними, а галузь математики, яка вивчає теорію скінченних множин, комбінаторикою. Найпростіші задачі комбінаторики вимагають підрахунку числа підмножин заданої множини. Основними принципами (правилами) комбінаторики є принцип суми і принцип добутку.

Принцип суми. Якщо множина A містить п елементів, а множина В - т елементів і А ∩ В = Ø, то множина A U В містить п + т елементів.

Справді, елементи множини А занумеруємо від 1 до п. Серед них немає елементів з множини В, оскільки А ∩ В = 0. Отже, коли ми переходимо до підрахунку елементів, що належать множині В, то починаємо з номера п +1. Далі буде номер п + 2, п + 3 , ..., п + т, оскільки в множині В за умовою т елементів. Цим усі елементи множини A U В буде вичерпано, вони дістануть номери від 1 до п + т.

Правило суми можна сформулювати ще й так: якщо якийсь вибір А можна здійснити п способами, а другий вибір В можна здійснити т способами, то вибір А або В можна здійснити п + т способами.

Принцип суми за індукцією поширюється на к множин.

Принцип добутку. Нехай маємо дві множини:

 

А={a1, а2, ..., an}, В={b1 b2, ..., bn}.

 

Тоді множина всіх можливих пар

 

С={(аi, bi)ا i=1, 2, ..., п; j = 1, 2, ..., m} містить п-т елементів.

Розіб'ємо множину С на множини

 

С={(а1, b1), (а1, b2), …, (а1, bm) }

С={(а2, b1), (а2, b2), …, (а2, bm) }

…………………………………

С={(аn, b1), (аn, b2), …, (аn, bm) }

 

Неважко помітити, що множини С1, С2, ..., Сn, попарно не перетинаються і C = Cl UC2 U … UCn. Оскільки кожна з підмножин С1, С2, ..., Сn, містить т елементів, то за принципом суми число елементів в об'єднанні їх дорівнює п т.

Правило добутку можна сформулювати ще й так: якщо якийсь вибір А можна здійснити п різними способами, а для кожного з цих способів деякий другий вибір В можна здійснити т способами, то вибір А і В у вказаному порядку можна здійснити п т способами.

 

Приклад 1. З міста А у місто Б веде 6 шляхів, а з міста Б у місто В 4 шляхи (рис. 298). Скількома шляхами можна проїхати з містам у місто В1 Вибравши один із шести шляхів з міста А у місто Б, далі можемо вибрати шлях від Б до В чотирма способами. Тому на підставі правила добутку дістанемо 6 4 = 24.

 

 

Приклад 2. До міста А, Б і В додамо ще одне місто Г і кілька нових шляхів (рис. 299). Скількома маршрутами тепер можна дістатися з міста А у місто В?

Розглянемо два випадки: шлях проходить через місто Б або через місто Г. Для кожного з цих випадків за правилом добутку неважко під-| рахувати кількість маршрутів (для першого - 24, для другого - 6). За правилом суми маємо остаточно: 24 + 6 = 30. Отже, загальна кількість маршрутів 30.

Приклад 3. У крамниці продають 5 склянок, 3 блюдця і 4 ложки. Скількома способами можна купити два предмети з різними назвами?

Можливими є три випадки: перший - купують склянку з блюдцем, другий - склянку з ложкою, третій - блюдце і ложку. У кожному з цих випадків за правилом добутку неважко підрахувати кількість можливих варіантів: 15, 20 і 12. За правилом суми маємо остаточно: 15 + 20 + 12 = 47.

Сформулюємо тепер принцип (правило) добутку у загальному вигляді.

Нехай треба виконати одну за одною k дій. Якщо першу дію можна виконати n, способами, другу - п2 способами,..., k-ту- пk способами, то всі k дій разом можуть бути виконані n способами, де п = п2п2 ... пk.

 

§ 2. Перестановки

 

Нехай треба підрахувати число способів, за якими можна розмістити в ряд n предметів. Якщо дані предмети розглядати як елементи множини то кожне розміщення є скінченною множиною, елементи якої записано у певному порядку.

Скінченні множини, для яких істотним є порядок елементів, називаються впорядкованими. Вказати порядок розміщення елементів у скінченній множині з п елементів означає поставити у відповідність кожному елементу даної множини певне натуральне число від 1 до п .

Дві впорядковані множини називаються рівними, якщо вони складаються з тих самих елементів і однаково впорядковані. З цього випливає, що множини (а, b, с) і (b, с, а) - це різні впорядковані множини.

Означення. Будь-яка впорядкована множина, що складається з п елементів, називається перестановкою з п елементів.

Перестановки з п елементів складаються з одних і тих самих елементів, а відрізняються одна від одної лише порядком.

Наприклад, з елементів множини А = {1, 2, 3} можна утворити шість перестановок: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).

Число перестановок у множині з п елементів позначають Рп .

Доведемо, що

 

Рп=n!, (1)

 

де п! = 12 ... п .

Для доведення застосуємо метод математичної індукції.

1. Якщо п = 1, маємо Рп =1 = 1!; тобто формула (1) виконується.

2. Припустимо, що для n = 1 рівність Рк = k! виконується (п і k - натуральні числа).

Доведемо, що для п = k +1 виконуватиметься рівність

 

Рk+1=(к + 1)!

 

На перше місце можемо поставити будь-який з k + 1 елементів множини. Тоді k місць, які залишилися, можна задавати будь-якою перестановкою з k елементів. Число таких перестановок Рk . Таким чином, перестановку з k + 1 елемента даної множини можна розглядати як пару: на першому місці - елемент множини, на другому - перестановка з k елементів, що залишились (таких перестановок Рk). На підставі принципу добутку число всіх перестановок (всіх таких пар)

 

Рk+1=(к + 1) Рk , (1)

 

З формули (2) дістаємо

 

Рk+1=(к + 1) Рk = Рk (к + 1) =k! (k+1)=12…k (k+1)=(k+1)!

 

Приклад 1. Скількома способами можна розмістити в один ряд червону, синю, чорну та зелену фішки?

 

Р4 = 4! = 1234 = 24.

 

Приклад 2. Скількома способами можна розмістити за столом 10 чоловік?

Р10=10! = 12345678910 = 3628800.

 

§ 3. Розміщення

 

Нехай деяка множина складається з п різних елементів.

Означення. Розміщеннями з п елементів по k називаються підмножини, що мають k елементів, вибраних з даних п елементів і розміщених у певному порядку (k<п).

Розміщення можуть відрізнятися одне від одного або самими елементами, або порядком їх розміщення.

Наприклад, нехай маємо три елементи: 1, 2, 3. Тоді розміщення з трьох елементів по два мають вигляд: (1, 2), (1, 3), (2, 1), (3, 1), (2, 3), (З, 2). Розміщення (1, 2) і (2, 1) відрізняються лише порядком. Вони утворюють два різних числа 12 та 21. Розміщення (1, 2) і (1, 3) відрізняються самими елементами. Вони утворюють два різних числа 12 і 13.

Кількість розміщень з даних п елементів по k позначають через Аkn, = k < п.

Доведемо, що

 

Аkn = n(n-1)(n-2)...(n-(k-1)). (1)

 

Якщо множина містить п елементів, то при утворенні розміщень по одному елементу таких розміщень буде п (стільки, скільки елементів у множині). Отже, Аkn = п.

Утворимо тепер розміщення з п елементів по два. Для цього візьмемо п розміщень по одному елементу і до кожного розміщення допишемо кожний з решти п -1 елементів даної множини. Таким чином, Аkn = n(n-1).

Застосуємо метод математичної індукції. Припустимо, що для А2n правильною є формула (1). Розміщення з п елементів по k + і можна розглядати як пару: на першому місці будь-яке розміщення з п елементів по k (їх кількість Аkn ), на другому - будь-який елемент з решти п - k елементів. За правилом добутку дістанемо

 

А n k +1= А n k (n-k). (2)

 

Користуючись формулою (1), маємо

 

А n k +1=п(п-1)(п-2)...(п-(k-і))(п-k) = = n(n - 1)(n - 2)...(n- (k -1))(n-(k +1-1)).

 

Оскільки

 

 

то формулу (1) можна записати ще так:

 

. (3)

 

Приклад 1. Скількома способами можна вибрати з 10 кандидатів три особи на три різні посади?

Для розв'язування задачі треба знайти число розміщень з 10 елементів по три. Отже, за формулою (1) маємо

A310 =1098 = 720.

Приклад 2. Скільки трицифрових чисел з різними цифрами можна утворити з цифр 0, 1, 2, 3, 4?

Загальна кількість трицифрових чисел з різними цифрами є кількістю

розміщень з 5 елементів по три, тобто А35 = 5 4 3 = 60. Проте із загальної кількості чисел треба відкинути числа, що починаються з нуля. Таких чисел стільки, скільки можна утворити розміщень з чотирьох цифр по два без нуля, тобто А24 =43 = 12. Отже, шукана кількість трицифрових чисел дорівнює 60 - 12 = 48 .

 

§ 4. Комбінації

 

Означення. Будь-яка підмножина з k елементів даної множини, яка містіть п елементів, називається комбінацією з п елементів по k.

З одного елемента можна утворити тільки одну комбінацію. З двох елементів а і b можна утворити дві комбінації по одному елементу і тільки одну комбінацію з двох елементів.

З трьох елементів a, b, c можна утворити такі комбінації:

 

{a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}.

 

Комбінації з п елементів даної множини по k можна також розглядати як розміщення з п елементів по k, які відрізняються принаймні одним елементом. Виникає запитання, як ви

Похожие работы

1 2 3 4 5 > >>