Комбінації (сполучення)

Комбінації (сполучення).

Нехай дано множину X з елементів x₁, x₂,..., x_п-1, x_n.

Комбінацією (сполученням) з n елементів по m (m ≤ n) називають будь-яку під множину Yмножини X; причому дві такі підмножини вважають різними, якщо вони відрізняються складом.

Кількість комбінацій з n елементів по m позначають С^m_n. Для обчислення С^m_n використовують формулу:

Наприклад, 

Приклад. У вазі 6 червоних і 4 білих троянди. Скількома способами з вази можна вибрати: 1) три троянди; 2) дві червоні і одну білу троянду?

Розв’язання. 1) Оскільки порядок вибору не має значення, то вибрати три троянди з 10 можна С³₁₀ способами.

2) Дві червоні троянди можна вибрати С²₆ способами, а одну білу – C¹₄ способами. Тому вибрати дві червоні і одну білу троянди можна способами. Маємо

Якщо в комбінаторній задачі необхідно вибрати т елементів з n, то важливим є питання необхідно враховувати порядок слідування елементів чи ні. Від цього залежить яку формулу (комбінаторну схему) необхідно використовувати:

якщо порядок має значення, то використовуємо А^m_n, якщо ні — то С^m_n. Пропонується наступназадача-схема.

В класі 20 учнів. Скількома способами з цього класу можна вибрати...
старосту й його заступника	двох чергових
Обов’язки різні! Порядок має значення.	Обов’язки однакові! Порядок не має значення.



Отже, упорядкована сукупність з nелементів 

називається перестановкоюз n елементів.

Число всіх можливих перестановок з n елементів позначається Р_n і обчислюється за формулою: Р_n = n ∙ (n - 1) ∙ (n - 2) ∙ … ∙ 2 ∙ 1. Такий добуток скорочено записується як n!.

Зверніть увагу! Одиниця факторіал дорівнює одиниці; нуль факторіал дорівнює одиниці.

Число всіх можливих перестановок з n елементів дорівнює Р_n = n!.

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

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

Число всіх можливих розміщень з n елементів до m дорівнює добутку чисел, починаючи з числа n, наступними такими, що кожне з наступних на одиницю менше від попереднього і закінчуючи числом, що на одиницю більше від різниці чисел n і m.

Сукупність з m елементів, які вибрані з даних n елементів, називаєтьсякомбінацією з m елементів до n.

Зверніть увагу! Дві комбінації з n елементів до m є різними тоді і тільки тоді, коли вони відрізняються хоча б одним елементом. Порядок елементів значення не має.

Число всіх можливих сполучень з n елементів до m дорівнює відношенню числа розміщень з n елементів до m до числа перестановок з m елементів.

Правило додавання

Якщо деяку елементарну дію А можна виконати т способами, а другу дію Вможна виконати n способами, то дію «або А, або В» можна виконати m + nспособами.

Правило множення

Якщо деяку елементарну дію А можна виконати m способами, а після цього виконати другу дію Вn способами, то дію «спочатку А, потім В» можна виконати m∙ n способами.

Зверніть увагу! При розв’язуванні комбінаторних задач спочатку треба визначити, про яке сполучення йдеться в задачі, а потім використовувати відповідну формулу.

Задачі комбінаторики

Завдання 1:

У магазині «Все для чаю» є 8 різних чашок і 5 різних блюдця. Скількома способами можна купити 2 чашки з 2 блюдцями?

Завдання 2:

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

Завдання 3:

У Країні Чудес є три міста: А, Би і В. Із міста А в місто Б веде 7 дорогий, а з міста Б в місто В - 8 доріг. Скількома способами можна проїхати від А до В?

Завдання 4:

У Країні Чудес є чотири міста: А, Би і В і Г. Із міста А в місто Б веде 8 дорогий, а з міста Б в місто В - 5 дорогі, З міста А в місто Г - дві дорогі, і з міста Г в місто В - теж дві дорогі. Скількома способами можна проїхати від А до В?

Завдання 5:

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

Завдання 6:

Назвемо натуральне число «симпатичним», якщо в його записі зустрічаються тільки непарні цифри. Скільки існує 4-значних «симпатичних» чисел?

Завдання 7:

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

Завдання 8:

Кожну клітку квадратної таблиці 2х2 можна пофарбувати в чорний або білий колір. Скільки існує різних розфарбовувань цієї таблиці?

Завдання 9:

Скількома способами можна заповнити одну картку в лотереї «Спорт-прогноз»? (У цій лотереї потрібно передбачити підсумок тринадцяти спортивних матчів. Підсумок кожного матчу - перемога однієї з команд або нічия; рахунок ролі не грає).

Завдання 10:

Алфавіт племені Мумбо-юмбо складається з трьох букв А, Би і В. Словом є будь-яка послідовність, що полягає не більш, ніж з 4 букв. Скільки слів в мові племені Мумбо-юмбо? Вказівка. Злічіть окремо кількості одно-, двух-, трьох- і чотирьохбуквених слів.

Завдання 11:

У футбольній команді (11 чоловік) потрібно вибрати капітана і його заступника. Скількома способами це можна зробити?

Завдання 12:

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

Завдання 13:

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

Завдання 14:

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

Завдання 15:

Скільки існує тризначних чисел, в записі яких цифри 1, 2, 3 зустрічаються рівно по одному разу?

Завдання 16:

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

Завдання 17: Слово - будь-яка кінцева послідовність букв  алфавіту. З'ясуєте, скільки різних слів можна скласти із слів

а) «ВЕКТОР»;

б) «ЛІНІЯ»;

в) «ПАРАБОЛА»;

г) «БІСЕКТРИСА»;

д) «МАТЕМАТИКА»;

Завдання 22:

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

Завдання 23:

Скільки діагоналей в опуклому n-косинці?

Завдання 24:

Намиста - це кільце, на яке нанизані намистини. Намиста можна повертати, але не перевертати. Скільки різних намист можна зробити з 13 різноколірних намистин?

Завдання 25:

Припустимо тепер, що намиста можна і перевертати. Скільки тоді різних намист можна зробити з 13 різноколірних намистин?

Завдання 26:

Скільки існує 6-цифрових чисел, в записі яких є хоч би одна парна цифра?

Завдання 27:

У алфавіті племені Бум-Бум шість букв. Словом є будь-яка послідовність з шести букв, в якій є хоч би дві однакові букви. Скільки слів в мові племені Бум-Бум?

Завдання 28:

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

Завдання 29:

Скількома способами можна вибрати голосну і приголосну букви із слова «КРУЖОК»?

Завдання 30:

На дошці написано 7 іменників, 5 дієслів і 2 прикметників. Для пропозиції потрібно вибрати по одному слову кожній з цих частин мови. Скількома способами це можна зробити?

Завдання 31:

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

Завдання 32:

Скільки існує 6-значних чисел, всі цифри яких мають однакову парність?

Завдання 33:

Треба послати 6 термінових листів. Скількома способами це можна зробити, якщо для передачі листів можна використовувати трьох кур'єрів і кожен лист можна дати будь-якому з кур'єрів?

Завдання 34:

Скількома способами з повної колоди (52 карти) можна вибрати 4 карти різних мастей і достоїнств?

Завдання 35:

На полиці коштують 5 книг. Скількома способами можна викласти в стопку декілька з них (стопка може полягати і з однієї книги)?

Завдання 36:

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

Завдання 37:

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

Завдання 38:

Чемпіонат України по шахах проводиться в один круг. Скільки грається партій, якщо беруть участь 18 шахістів?

Завдання 39:

Скількома способами можна поставити на шахівницю так, щоб вони не били один одного а) дві тура; б) двох королів; у) двох слонів; г) двох коней; д) двох ферзів?

Завдання 40:

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

Завдання 41:

Скількома способами можна поселити 7 студентів в три кімнати: одномісну, двомісну і чотиримісну?

Завдання 42:

Скількома способами можна розставити на першій горизонталі шахівниці комплект білих фігур (король, ферзь, дві тура, два слони і два коні)?

Завдання 43:

Скільки слів можна скласти з п'яти букв А і не більше ніж з трьох букв Б?

Завдання 44:

Скільки існує 10- цифрових, в яких є хоч би дві одінакоиє цифри?

Завдання 45:

Яких 7-цифрових чисел більше: тих, в записі яких є 1, або інших?

Завдання 46:

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

Завдання 47:

Скількома способами можна розбити 14 чоловік на пари?

Завдання 48:

Скільки існує 9-значних чисел, сума цифр яких парна?

Завдання 49:

Скільки існує 6-цифрових чисел, в записі яких усі парні цифри?

Завдання 50:

Скільки існує 6-цифрових чисел, в записі яких усі парні і непарні цифри чергуються одна за одною?

Завдання 51:

Скільки існує 6-цифрових чисел, в записі яких цифри 4 і 2 чергуються одна за одною?

Завдання 52:

Скільки чисел серед першої сотні натураль­них чисел не діляться ні на 7, ні на 9, ні на 10?

Завдання 53:

Скільки чисел серед 6-цифрових натураль­них чисел не діляться ні на 2, ні на 2, ні на 5?