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

Комбінаторика у класичному розумінні (сучасна назва — комбінаторний аналіз) — це розділ математики, присвяче­ний розв'язанню задач про вибір та розміщення елементів скінченної множини згідно із заданими правилами. Ці правила визначають спосіб побудови деякої конструкції — ком­бінаторної сполуки (конфігурації). Вивчати властивості цих сполук та підраховувати кількість різних способів їх побу­дови зручно у такій послідовності:

а)  спочатку формулюється класична (ключова) задача, яка приводить до комбінаторної конфігурації, що вивча­ється;

б) потім наводиться розв'язання цієї задачі та виведення основної формули;

в)  після цього будується математична модель комбіна­торної сполуки і мовою теорії множин дається її точне означення.

Множина та її елементи. 

Числові множини

Операції над множинами

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

Об’єкти, з яких складається множина, є елементами множини. Множина однозначно визначається її елементами.

Для позначення множин використовують великі латинські літери А, В, С…

Для позначення елементів множин використовують маленькі латинські літериа, b, c, …

Якщо множина має скінченну кількість елементів, то вона називаєтьсяскінченною множиною

Якщо множина має нескінченну кількість елементів, то вона називаєтьсянескінченною множиною

Множина А вважається підмножиною множини В, якщо кожен елемент множини А є й елементом множини В.

Множина, яка не містить жодного елемента, є порожньою множиною.

Порожня множина є підмножиною будь-якої множини.

Множини А і В називаються рівними, якщо вони містять одні і ті ж самі елементи.

У математиці велику роль відіграють такі числові множини:

Натуральними називаються числа, якими можна рахувати: 1, 2, 3, …

Множина N натуральних чисел – нескінченна множина, до якої належить число 1 і всі наступні числа, кожне з яких на 1 більше від попереднього.

Цілими є числа натуральні, протилежні їм і число 0.

Множина Z цілих чисел – нескінченна множина, до якої належить число 0, множина натуральних чисел і всі числа, протилежні натуральним.

Раціональними називаються числа, які можна представити у вигляді дробуm/n, де m – ціле число і n – натуральне число.

Множина Q раціональних чисел – нескінченна множина, до якої належать усі числа, які можна записати у вигляді відношення цілого числа до натурального числа.

Зверніть увагу! Будь-яке раціональне число можна представити у вигляді або скінченого десяткового дробу, або нескінченного періодичного десяткового дробу.

Ірраціональними називаються числа, які не можна представити у вигляді дробу m/n, де m – ціле число і n – натуральні числа.

Зверніть увагу! Будь-яке ірраціональне число можна представити у вигляді нескінченного неперіодичного десяткового дробу.

Множина ірраціональних чисел – нескінченна множина, до якої належать усі числа, які не можна записати у вигляді відношення цілого числа до натурального числа.

Дійсними є числа раціональні та ірраціональні. Множина R дійсних чисел – нескінченна множина, до якої належать усі раціональні та ірраціональні числа.

 Поняття множини. Операції над множинами

Поняття множини належить до первісних понять математики, якому не дається означення Множину можна уявити собі як су­купність деяких предметів, об'єднаних за довільною характерис­тичною ознакою

 Наприклад, множина учнів класу, множина цифр десяткової нумерації (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), множина натуральних чисел, множина зернин у даному колосі, множина букв українського алфавіту, множина точок на прямій

Предмети, з яких складається множина, називаються її елементами і позначаються малими буквами латинського алфавіту. Наприклад, а = 5 - елемент множини цифр десяткової нумерації Для позначення множин використовують великі букви латинсь­кого алфавіту або фігурні дужки, всередині яких записуються елементи множини При цьому порядок запису елементів не має значення Наприклад, множину цифр десяткової нумерації мож­на позначити буквою М (чи будь-якою великою буквою латин­ського алфавіту) або записати так {1, 3, 5, 2, 4, 6, 8, 7, 9, 0}

Належність предмета даній множині позначається символом , а неналежність - символом (інколи ) Наприклад, число 7 А, де А - множина чисел першого десятка, а число 12 A.

Множини бувають скінченні і нескінченні. У скінченній множині міститься певна кількість елементів, тобто кількість елементів скінченної множини виражається натуральним чис­лом Наприклад, множина М цифр десяткової нумерації скінчен­на і містить десять елементів. У нескінченній множині - нескін­ченна кількість елементів. Наприклад, множина натуральних чисел, множина точок прямої - нескінченні множини.

Множина, в якій немає жодного елемента, називається порож­ньою і позначається символом . Наприклад, множина точок перетину двох паралельних прямих - порожня множина

Якщо множина В складається з деяких елементів даної мно­жини А (і тільки з них), то множина В називається підмножиною множини А. У такому разі співвідношення між множинами А і В позначається так В А (читається "В міститься в А" або "В — підмножина А"). Якщо В може й дорівнювати А, то вживається символ В А. Знак називається знаком нестрогого включення, а знак - знаком строгого включення.

Порожня множина є підмножиною будь-якої множини, тобто А.

Саму множину А можна розглядати як підмножину А, тобто А А.

Множину задають двома основними способами:

1) переліченням всіх її елементів;

2) описанням характеристичної властивості її елементів. Наприклад: а) В = {o,,¡} - множина, задана переліченням елементів; б) X - множина коренів квадратного рівняння х2 = 25. Множина X задана характеристичною властивістю елементів - бути коренем рівняння х2 = 25". Цю саму множину можна зада­ти і переліченням її елементів: X = {-5; 5}.

Дві множини називаються рівними, якщо вони складаються з тих самих елементів. Наприклад, множини коренів рівняння х2 = 25 і |x| = 5 рівні між собою. Справді, X = {-5; 5} і Y = {-5; 5}, де Y - множина розв'язків рівняння |x|-5. Отже, X = Y.

Над множинами виконуються певні операції (дії). Зазначимо три з них.

Переріз множин. 

Перерізом множин А і В називається множина С, яка складається з усіх тих і тільки тих елемен­тів, які належать коленій з даних множин А і В.

Приклад 1. Нехай А - множина всіх дільників числа 32, тобто А = {І, 2, 4, 8, 16, 32), а В - множина всіх дільників чис­ла 24, тобто В = {1, 2, 3, 4, 6, 8, 12, 24}. Тоді перерізом множин А і В є множина С = {1, 2, 4, 8}, яка складається зі спільних дільників чисел 32 і 24.

Схематично переріз множин А і В можна зобразити за допо­могою фігур. Символічно позначається так: С = А В і читається: "С є перерізом А і В".

Приклад 2. Нехай М - множина прямокутників, N - множина ромбів, тоді Р = МN - множина квадратів.

Об'єднання множин. 

Об'єднанням (або сумою) двох мно­жин А і В називається така множина С, яка складається з усіх елементів множин А і В, і тільки з них.

Позначається це так: С = А +В і читається: "С є об'єднанням А і В".

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

Приклад 3. А ={1,2, 3,4}, В = {3, 4, 5, 6}, тоді С = {1,2,3,4,5,6}.

Приклад 4. Q - множина раціональних чисел, І - мно­жина ірраціональних чисел. Тоді множиною R всіх дійсних чисел буде об'єднання множин Q і І, тобто R = Q+ І.

Операції над множинами широко використовуються в мате­матиці та інших науках, а також у практиці. Наприклад, розв'яз­ками системи рівнянь є переріз множин розв'язків кожного рів­няння, а об'єднання їх є множиною розв'язків сукупності рів­нянь.

Віднімання множин.

Доповнення множини. Різницею двох множин А і В називається така множина С, яка складається з усіх елементів множини А, що не належать множині В.

Позначається це так: С = А \ В і читається: "С є різницею А і В".

Приклад 5. а) А= {5,6, 8, 12}, В= {5, 6}, тобто В А, тоді С = А \ В= {8, 12};

б) А = {5, 6, 8, 12}, В = {8, 12, 1, 2}, тоді С = А\ В = {5, 6};

в) А = {5, 6, 12}, В = {1, 2}, тоді С = А \ В = {5, 6, 12};

г) А= {5, 6}, В= {5,6, 12}, тобто В А, тоді С = А\ В = .

У випадку, коли А В, то різниця С = А \ В називається доповненням множини В відносно множини А і позначаєть­ся С (АВ).

В основі класичної комбінаторики лежать правило суми та правило добутку.

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

Багато комбінаторних задач можуть бути розв’язані за допомогою двох важливих правил, які називають відповідно правило суми і правило добутку.

Спочатку розглянемо правило суми:

якщо деякий елемент А можна вибрати m способами, а елемент В — r способами (причому будь-який вибір елемента А відрізняється від вибору елемента В), то вибрати А або В можна m +r способами.

Приклад 1. В ящику знаходиться 7 білих і 4 чорних кульки. Тоді вибрати одну кульку: білу або чорну можна 7 + 4 = 11 способами.

Зрозуміло, що правило суми можна розповсюдити на три і більше елементів.

Сформулюємо правило добутку:

якщо деякий елемент А можна вибрати m способами, а після кожного такого вибору інший елемент В можна вибрати (незалежно від вибору елемента А) — r способами, то пару об’єктів А і В можна вибрати mr способами.

Приклад 2. У шкільній їдальні є вибір з 3 перших і 5 других блюд. Тоді обід з першого і другого блюда можна обрати 3 ∙ 5 = 15 способами.

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

Приклад 3. Скільки трицифрових чисел можна скласти з цифр 1; 2; 3; 4; 5, якщо в числі: 1) цифри не повторюються; 2) цифри повторюються.

Розв’язання.

1) Маємо 5 способів для сотень числа (мал. 129). Після того, як місце сотень заповнене (наприклад, цифрою 1), для десятків залишається 4 способи. Міркуючи далі, для одиниць - 3 способи. Отже, маємо: «5 способів, і після кожного з них — 4, і після кожного з них — 3 способи». За правилом добутку маємо 5 ∙ 4 ∙ 3 = 60 чисел.

2) Якщо цифри у числі повторюються, то на кожне з трьох місць є по 5 варіантів заповнення(мал. 130), і тоді всіх чисел буде 5 ∙ 5 ∙ 5 = 125.

Приклад 4. Скільки парних чотирицифрових чисел можна скласти з цифр 6; 7; 8; 9, якщо в числі цифри не повторюються?

Розв’язання. Парне чотирицифрове число можна отримати, якщо останньою цифрою буде 6 або 8. Чисел, у яких остання цифра 6 буде З ∙ 2 ∙ 1 = 6 (мал. 131), чисел, у яких остання цифра 8 буде також 6. За правилом суми всього парних чисел, що задовольняють умові, буде 6 + 6 = 12.



Правило добутку застосовується при розв'язуванні такої класичної задачі:

а)Елемент а можна вибрати т способами. Після кожного такого вибору елемент b можна вибрати к способами. Скількома способами можна здійснити вибір пари елементів (а, b) у вказаному порядку?

б)  Очевидно, що вибір впорядкованої пари (а, b) можна здійснити тк способами. Це твердження складає зміст правила добутку у класичному розумінні.

Зауваження 1. Також тк способами можна вибрати пару (b, а) у зворотньому порядку. Однак для більшості комбіна­торних задач, при розв'язанні яких застосовується правило добутку, порядок вибору елементів пари не має значення. Тому при підрахунку кількості способів вибору пари еле­ментів найчастіше враховується лише один з двох можли­dі їх порядків вибору.

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