Элементы комбинаторики

Елементи комбінаторики

1. Правило суми і добутку

Стислі теоретичні відомості

Правило суми

Класичне

формулювання

Якщо якийсь елемент множини A можна вибрати n способами, а елемент множи-

ни B — m способами, то вибір елемента із множини A або із множини B можна зробити n+ m способами­ .

Формулювання в термінах теорії множин

Якщо множина A складається з n елементів, а множина B — з m елементів, то ви­ брати елемент із множини A

або із множини B можна n+ m способами.

Приклад. У коробці 5 кольорових олівців і 7 фломастерів. Скількома способами можна вибрати один олівець або один фло­ мастер?

Розв’язання

	I способ		II способ
Один олівець із 5 можна вибра-			Множина олівців складаєть-
ти 5 способами, а один флома­			ся з 5 елементів, а множина
стер — 7 способами. За прави-			фломастерів — із 7 елементів.
лом суми один предмет можна			Вибрати предмет із множини
вибрати 5+ 7 = 12 способами­		.	олівців або із множини флома­
			стерів можна 12 способами.
	Правило добутку

Класичне

формулювання

Якщо якийсь елемент множини A можна вибрати n способами, після кожного такого вибору­ елемент із множини B — m способами, то пару елементів із множин A і B можна вибрати m n ­способами.

Формулювання в термінах теорії множин

Нехай є дві множи-

ни: A = {a1,a2,...,an}

і B= {b1,b2,...,bm} . Парою називається об’єкт вигляду (ai,bj ) ,

де i = 1,…,n , j = 1,…,m.

14

Елементи комбінаторики

Зрозуміло, що в таких задачах порядок розташування елементів не важливий.

Якщо множина A складається з n елементів, а множина B — із m елементів, то мож-

на скласти рівно n m пар

вигляду­ (ai,bj ) , вважаючи,

що (ai,bj ) = (bj,ai ), i = 1,…,n , j = 1,…,m.

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

Розв’язання

I способ		II способ
Із першої коробки один олівець		Множина олівців складаєть-
можна вибрати 5 способами		ся із 5 елементів, а множина
і кожному вибраному олівцю		фломастерів — із 7 елементів.
можна взяти до пари будь-		За правилом добутку скласти
який із 7 фломастерів. Отже,		пару із одного олівця і одного
за правилом добутку маємо		фломастера можна 5 7 = 35
5 7 = 35 способів.		способами.

Наслідок із правила добутку

Якщо якийсь елемент множини A1 можна вибрати n1 способами, після цього елемент із множини A2 можна вибрати n2 способами, ..., елемент

із множини Ak −− nk способами, то групу елементів, яка складається з одного елемента множини A1 , одного елемента множини A2 , ..., одного елемента множини Ak , можна скласти n1 n2 … nk способами.

Якщо множина A1 складається з n1 елементів, множи-

на A2 — із n2 елементів, ..., множина Ak — із nk елементів, то число груп вигляду

(ai1 ,ai2 ,...,aik ) , де a1 A1 , a2 A2 , ..., ak Ak ,

дорівнює n1 n2 n3 … nk .

15

Елементи комбінаторики

Приклад. У коробці 5 олівців, 7 фломастерів і 10 листівок. Скількома способами можна скласти із одного олівця, одного фломастера і однієї листівки­ подарунок для першокласника?

Розв’язання

I способ	II способ
Один олівець можна вибрати	Множина олівців складається
5 способами, кожному обра-	із 5 елементів, множина флома­
ному олівцю до пари можна	стерів — із 7, множина листі-
7 способами вибрати флома­	вок — із 10 елементів. Складати-
стер, кожній парі одну листівку	мемо різні «трійки», у яких один
можна дібрати 10 способами.	предмет — із множини олівців,
Разом маємо 5 7 10 = 350 спо-	другий — із множини фломас-
собів.	терів, а третій — із множини
	листівок. За правилом добутку
	це можна зробити 5 7 10 = 350
	способами.

Приклади розв’язування задач

Приклад 1. У групі 10 дівчаток і 15 хлопчиків. Скількома способами із цієї групи можна вибрати: а) одного хлопчика; б) одного хлопчика або одну дівчинку;

в) одного хлопчика і одну дівчинку?

Розв’язання

а) Із 15 хлопчиків одного можна вибрати 15 способами; б) за правилом суми дівчинку або хлопчика можна вибрати

10+ 15 = 25 способами; в) за правилом добутку пари «дівчинка і хлопчик» можна ви­

брати 10 15 = 150 способами.

Відповідь: а) 15; б) 25; в) 150.

Приклад 2. У країні Чудес є три міста — А, Б і В. Із міста А до міста Б веде 6 доріг, а з міста Б до міста В — 4 дороги. Скількома способами можна проїхати з міста А до міста В?

Розв’язання. З А до В можна дістатися, пройшовши 2 частини шляху: з А до Б, що можна здійснити 6 способами, і з Б до В, що можливо зробити 4 способами. Скласти пари доріг: з А до Б й із Б до В можна 6 4 = 24 способами.

Відповідь: 24.

16

Елементи комбінаторики

Приклад 3. У країні Чудес (див. приклад 2) побудували ще одне місто — Г і нові дороги: з А до Г — 2 дороги, із Г до В — 3 дороги. Скількома способами тепер можна дістатися з А до В?

Розв’язання. Щоб дістатися з А до В, існує два варіанти: через місто Б, що можна зробити 6 4 = 24 способами, або через місто Г, що можливо здійснити 2 3 = 6 способами.

За правилом суми всього способів 24+ 6 = 30 .

Відповідь: 30.

Приклад 4. Скількома способами можна вибрати одну голосну й одну приголосну зі слова: а) «цукат»; б) «телефон»?

Розв’язання

а) Множина голосних букв слова «цукат» складається з двох букв {у,а} ; множина приголосних — із трьох: {ц,к, т} . Складаючи різні пари цих множин, одержимо 2 3 = 6 способів;

б) множина голосних: {е,о} , приголосних: {т, л, ф,н} . Разом: 2 4 = 8 способів.

Відповідь: 8.

Приклад 5. Складають автомобільні номери, що містять чотири цифри. Скільки таких номерів можна скласти, якщо:

а)	використовувати 10 цифр;
б) використовувати тільки непарні цифри?
Розв’язання
а)	I способ		II способ
Першу цифру можемо вибрати			Складатимемо різні «четвір-
10 способами, після чого дру-			ки» цифр, кожну з яких виби-
гу — так само 10 способами,			раємо з 10-елементної мно-
потім третю і четверту — теж			жини. За правилом добутку
10 способами. Усього маємо			маємо 10 10 10 10 = 104 но-
10 10 10 10 = 104 способів.			мерів.

б) Аналогічно маємо 54 = 625 способів.

Відповідь: а) 104 ; б) 625.

Приклад 6. Скількомаспособамиіз5конвертів,4марокі6листівок можна вибрати два предмети з різними назвами?

Розв’язання. Марку і конверт можна вибрати 5 4 = 20 способами, марку і листівку — 4 6 = 24 способами, конверт і листівку — 5 6 = 30 способами. Одну пару — або другу, або третю — за правилом суми можна вибрати 20+ 24+ 30 = 74 способами.

Відповідь: 74.

17

Елементи комбінаторики

Приклад 7. Монету кидають тричі. Скільки різних послідовно­ стей орлів або решок можна при цьому одержати?

Розв’язання. Складатимемо різні «трійки» результатів підкидання монети. Кожний елемент цієї «трійки» вибираємо із двох­ елементної множини {орел, решка}. За правилом множення маємо 2 2 2= 23 = 8 послідовностей.

Відповідь: 8.

Приклад 8. Підкидають одночасно два гральні кубики. Скільки різних варіантів випадання цифр може при цьому вийти?

Розв’язання. Для кожної із шести цифр першого кубика можлива будь-яка із шести цифр другого кубика. За правилом добутку маємо 6 6 = 36 варіантів.

Відповідь: 36.

Приклад 9. Алфавіт племені мумбо-юмбо складається з трьох літер: м, ю, б. «Словом» є будь-яка послідовність, що складається не більше ніж із 4 літер. Скільки «слів» у мові племені мумбо-юмбо?

Розв’язання. «Не більше ніж» означає, що «слово» може бути одно-, двох-, трьох- і чотирьохлітерним. «Слів», що складаються з однієї літери,— 3, із двох літер — 3 3 = 9 , із трьох — 3 3 3 = 27 , із чотирьох — 34 = 81. Кількість усіх «слів» становить

3+ 9+ 27+ 81= 120 .

Відповідь: 120.

Приклад 10. На фермі є 20 овець і 24 свині. Скількома способами можна вибрати одну вівцю й одну свиню? Якщо такий вибір уже зроблено, скількома способами його можна зробити ще раз?

Розв’язання.	Перша частина задачі розв’язується прос-
то — 20 24 = 480	способів. Після першого вибору залишилося

19 овець і 23 свині, і тепер аналогічний вибір можна зробити 19 23 = = 437 способами.

Відповідь: 437.

Приклад 11. У прикладі 10 вибрали одну тварину. Скількома способами після цього можна вибрати одну вівцю й одну свиню?

Розв’язання. У першому випадку могли вибрати або вівцю, або свиню. Якщо вибрали вівцю, що можна зробити 20 способами, то із решти тварин пару можна вибрати 19 24 = 456 способами. Якщо ж спочатку вибрали свиню, то після цього пару можна вибрати 20 23 = 460 способами. Усього маємо 456+ 460 = 916 способів.

Відповідь: 916.

18

Елементи комбінаторики

Задачі для самостійного розв’язування

1.У букеті 10 троянд і 12 хризантем. Скількома способами можна вибрати із букета:

а) або одну троянду, або одну хризантему; б) одну троянду або одну хризантему; в) одну троянду й одну хризантему?

2.Умагазиніпосудує5видівчашокі7видівблюдець.Скількома способами можна вибрати пару блюдець і чашку?

3.У магазині посуду із задачі 2 є ще 6 видів чайних ложок. Скільки існує способів скласти набір із чашки, блюдця і ложки?

4.У глядацькому залі кінотеатру всього 6 дверей. Скільки ­існує способів:

а) увійти до глядацького залу і вийти з нього; б) увійти до залу і вийти, але так, щоб вхід і вихід здійснюва-

лися через різні двері?

5.У глядацькому залі із задачі 4 існує ще двоє дверей до кімнати кіномеханіка. Скількома способами кіномеханік може потрапити на робоче місце?

6.У класі 30 учнів. Щодня призначається один черговий. Скількома способами можна скласти графік чергування на 5 днів так, щоб ніхто не чергував більше одного разу?

7.Скільки існує різних телефонних номерів, якщо вважати, що кожний номер складається із 7 цифр (телефонний номер може починатися з нуля)? Як зміниться розв’язок задачі, якщо телефонні номери можуть бути як семи-, так і шестицифровими?

8.Кидають дві монети. Скільки різних варіантів випадання «орел — решка» може при цьому вийти?

9.Гральний кубик кидають тричі. Скільки різних послідовностей чисел може при цьому вийти?

10.Кожна літера азбуки Морзе — це послідовність крапок

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

а) 5 символів;

б)   не більше ніж 5 символів?

11. Скількома способами можна вказати на шахівниці: а) два білих квадрати;

б) білий і чорний квадрати, якщо вони не лежать на одній горизонталі або одній вертикалі?

19

Елементи комбінаторики

12.У кошику 10 яблук і 12 апельсинів. Іван вибирає або яблуко, або апельсин, після чого Надя вибирає із фруктів, що залишилися, апельсин. Скільки можливостей такого вибору?

13.Скільки можна скласти із цифр 0, 1, 2, 3, 4, 5:

а) різних трицифрових чисел; б) різних трицифрових чисел, якщо цифри в них не повторю-

ються; в) різних трицифрових чисел, що діляться на 5?

14. Чотири учні одержують оцінки 2, 3, 4, 5.

а) Скількома способами можна поставити їм оцінки?

б) Скількома способами можна поставити оцінки так, щоб жодні два учні не одержали однакових?

в) Скількома способами можна поставити оцінки так, щоб усі одержали 4 або 5?

20

Елементи комбінаторики

2. Розміщення

Стислі теоретичні відомості

Поняття факторіала

•• Факторіаломнатуральногочислаnназиваєтьсядобутокусіхнатуральнихчиселвід1доn.Позначення: n! =n (n−1)(n−2) … 2 1.

Наприклад, 6! =6 5 4 3 2 1=720 . Очевидно, що n! =n (n−1)! . Прийнято, що 0! =1.

Із визначення: 1! =1 ; 2! =2; 3! =6; 4! =24; 5! =120 ; 6! =720

і т. д.

Приклади

а)

б)

в)

г)

д)

5!6! = 65!5! =6 .

10! = 1 2 3 4 5 6 7 8 9 10 =8 9 10 =720 ; 7! 1 2 3 4 5 6 7

20!	=19 20 =380				20!			=	18! 19 20		;
18!					18!				18!
n!		=		n (n− 1)!	=n ;
(n− 1)!				(n− 1)!
(n+ 1)!			=	(n+ 1)n(n− 1)!				=n(n+1) .
(n− 1)!				(n− 1)!

21

Елементи комбінаторики

Розміщення

•• Нехай дано множину A ={a1,a2,…,an} .

Кожну її впорядковану підмножину, що складається із m різних елементів, називають розміщенням із n елементів по m елементів.

Позначення: Anm .

Читають: «розміщення з nелементів по mелементів» або «число розміщень із n елементів по m елементів».

Число розміщень із n елементів по m обчислюють за фор­ мулами

Anm =n(n−1)(n−2) … (n−m+1) ;				(1)
Anm =	n!		.	(2)
	(n−m	)!

Формула (1) застосовується у випадку, якщо можна знайти результат, а формула (2) — якщо результат важко обчислити через великі числа або у випадку використання в задачі літерних змінних­ .

Приклад. У коробці 7 кольорових олівців. Складатимемо різні впорядковані підмножини із 3 олівців, причому будь-які дві підмножини, що відрізняються порядком черги олівців, вважаємо різними. Такий вибір і є розміщенням із 7 елементів по 3, і таких можливостей вибору буде A73 =7 6 5 =210 .

(Очевидно, що у цій задачі застосовується формула (1).)

Приклади розв’язування задач

Приклад 1. У класі 30 учнів. Скількома способами можна в ньому вибрати старосту і його заступника?

Розв’язання. Тут важливо, хто із двох обраних буде старостою, а хто — його заступником, тобто важливий порядок. Маємо розміщення із 30 по 2.

A302 =30 29 = 870 способів.

Відповідь: 870.

22

Елементи комбінаторики

Приклад 2. Прапор складається із 4 горизонтальних смуг різного кольору.

а) Скільки таких прапорів можна одержати, маючи у своєму розпорядженні смуги 7 кольорів (перестановки будь-яких двох кольорів дають новий прапор)?

б) Скільки таких прапорів можна одержати зі смуг 7 кольорів, якщо в усіх прапорів нижня смуга має бути однакового кольору?

Розв’язання

а) A74 = 7 6 5 4 = 840 прапорів;

б) розв’язання зводиться до складання триколірних прапорів, причому кількість кольорів зменшилася до шести. Маємо A63 = 6 5 4 = 120 прапорів.

Відповідь: а) 840; б) 120.

Приклад 3. У чемпіонаті країни з футболу беруть участь 16 команд. Скількома способами можна скласти трійку призерів?

Розв’язання. Оскільки на одному місці може опинитися тільки одна із команд, то маємо

A163 = 16 15 14 = 5360 .

Відповідь: 5360.

Приклад 4.

а) Чемпіонат країни з футболу, в якому беруть участь 16 команд, проводиться у два кола (кожна команда двічі зустрічається з кожною з інших). Яка кількість зустрічей буде в чемпіонаті?

б) Скільки буде зустрічей, якщо чемпіонат проводитиметься в одне коло?

Розв’язання

а) У кожній зустрічі одну з команд назвемо «гостем», а другу — «хазяїном». Очевидно, кількість зустрічей дорівнює кількості впорядкованих пар «хазяїн — гість», «гість — хазяїн», що обираються із 16 команд.

Усього A162 = 16 15 = 240 зустрічей;

б) у чемпіонаті в одне коло нам потрібні тільки пари «хазяїн — гість». Тобто кількість зустрічей буде у два рази менша. Ра-

зом A162 12 = 120 зустрічей.

Відповідь: а) 240; б) 120.

23