Вибірка з m по n. Розміщення з повтореннями

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

Комбінаторика - розділ математики, який вивчає завдання вибору та розташування елементів з деякої основної множини відповідно до заданих правил. Формули та принципи комбінаторики використовуються в теорії ймовірностей для підрахунку ймовірності випадкових подійі, відповідно, отримання законів розподілу випадкових величин. Це, своєю чергою, дозволяє досліджувати закономірності масових випадкових явищ, що дуже важливим для правильного розуміння статистичних закономірностей, які у природі і техніці.

Правила складання та множення у комбінаториці

Правило суми. Якщо дві дії А і В взаємно виключають один одного, причому дію А можна виконати m способами, а В - n способами, то виконати одну з цих дій (або А або В) можна n + m способами.

приклад 1.

У класі навчається 16 хлопчиків та 10 дівчаток. Скільки способами можна призначити одного чергового?

Рішення

Черговим можна призначити чи хлопчика, чи дівчинку, тобто. черговим може бути будь-хто з 16 хлопчиків або будь-яка з 10 дівчаток.

За правилом суми отримуємо, що одного чергового можна призначити 16+10=26 способами.

Правило твору. Нехай потрібно виконати послідовно дій. Якщо перше дію можна виконати n 1 способами, друге дію n 2 способами, третє - n 3 способами і так до k-го дії, яке можна виконати n k способами, то всі k дій можуть бути виконані:

методами.

приклад 2.

У класі навчається 16 хлопчиків та 10 дівчаток. Скільки способами можна призначити двох чергових?

Рішення

Першим черговим можна призначити або хлопчика або дівчинку. Т.к. у класі навчається 16 хлопчиків та 10 дівчаток, то призначити першого чергового можна 16+10=26 способами.

Після того, як ми вибрали першого чергового, другого ми можемо вибрати з 25 осіб, що залишилися, тобто. 25 способами.

По теоремі множення двоє чергових можна вибрати 26*25=650 способами.

Поєднання без повторень. Поєднання з повтореннями

Класичним завданням комбінаторики є завдання про кількість поєднань без повторень, зміст якої можна висловити: скільки способами можна, можливо вибрати m з n різних предметів ?

приклад 3.

Необхідно вибрати в подарунок 4 з 10 різних книг. Скільки можна це зробити?

Рішення

Нам із 10 книг потрібно вибрати 4, причому порядок вибору не має значення. Таким чином, потрібно знайти число поєднань з 10 елементів по 4:

.

Розглянемо задачу про кількість поєднань із повтореннями: є по r однакових предметівкожного з n різних типів; скільки способами можна, можливо вибрати m () з цих (n * r) предметів?

.

приклад 4.

У кондитерському магазині продавалися 4 сорти тістечок: наполеони, еклери, пісочні та листкові. Скільки можна купити 7 тістечок?

Рішення

Т.к. серед 7 тістечок можуть бути тістечка одного сорту, число способів, якими можна купити 7 тістечок, визначається числом поєднань з повтореннями з 7 по 4.

.

Розміщення без повторень. Розміщення з повтореннями

Класичним завданням комбінаторики є завдання про кількість розміщень без повторень, зміст якої можна висловити: скільки способами можна, можливо вибрати і розмістити по m різним місцям m з n різних предметів?

Приклад 5.

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

Рішення.

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

Таким чином, 4 фотографії на 12 сторінках можна розташувати 11 880 способами.

Також класичним завданнямкомбінаторики є завдання про кількість розміщень із повтореннями, зміст якої можна висловити питанням: скільки способами можна, можливо вибрать і розмістити по m різним місцям m з n предметів,зреді яких є однакові?

Приклад 6.

У хлопчика залишилися від набору для настільної гри штампи з цифрами 1, 3 та 7. Він вирішив за допомогою цих штампів нанести на всі книги п'ятизначні номери-скласти каталог. Скільки різних п'ятизначних номерів може становити хлопчик?

Перестановки без повторень. Перестановки із повтореннями

Класичним завданням комбінаторики є завдання про кількість перестановок без повторення, зміст якої можна висловити: скільки способами можна, можливо розмістити n різних предметів на n різних місцях?

Приклад 7.

Скільки можна скласти чотирилітерних «слів» із літер слова «шлюб»?

Рішення

Генеральною сукупністю є 4 літери слова «шлюб» (б, р, а, к). Число «слів» визначається перестановками цих 4 літер, тобто.

Для випадку, коли серед n елементів, що вибираються, є однакові (вибірка з поверненням), задачу про кількість перестановок з повтореннями можна висловити питанням: Скільки способами можна переставити n предметів, розташованих на n різних місцях, якщо серед n предметів є k різних типів (k< n), т. е. есть одинаковые предметы.

Приклад 8.

Скільки різних буквосполучень можна зробити з літер слова «Міссісіпі»?

Рішення

Тут 1 буква "м", 4 букви "і", 3 букви "c" і 1 буква "п", всього 9 букв. Отже, кількість перестановок з повтореннями дорівнює

ОПОРНИЙ КОНСПЕКТ З РОЗДІЛУ "КОМБІНАТОРИКА"

План:

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

2. Загальні правила комбінаторики.

4. Застосування графів (схем) під час вирішення комбінаторних завдань.

1. Комбінаторика та її виникнення.

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

Комбінаторика виникла XVI столітті. У житті привілейованих верств тогочасного суспільства велике місце займали азартні ігри (мапи, кістки). Широко поширені лотереї. Спочатку комбінаторні завдання стосувалися переважно азартних ігор: Скільки можна отримати це числоокулярів, кидаючи 2 або 3 кістки або кількома способами можна отримати двох королів у деякій картковій грі. Ці та інші проблеми азартних ігор були рушійною силоюу розвитку комбінаторики і далі у розвитку теорії ймовірностей.

Одним із перших зайнявся підрахунком числа різних комбінацій при грі в кістки італійський математик Тарталья. Він становив таблиці (числа способів випадання k очок на r кістках). Однак він не врахував, одна і та ж сума очок може випасти у різний спосібтому його таблиці містили велика кількістьпомилок.

Теоретичне дослідження питань комбінаторики розпочали у XVII столітті французькі математикиБлез Паскаль та Ферма. Вихідним пунктом їх досліджень були проблеми азартних ігор.

Подальший розвиток комбінаторики пов'язані з іменами Я. Бернуллі, Р. Лейбніца, Л. Ейлера. Проте, й у роботах основну роль грали докладання до різних ігор.

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

2. Загальні правила комбінаторики.

Правило суми:Якщо деякий об'єкт А може бути обраний m способами, а об'єкт-k способами, то об'єкт «або А, або В» можна вибрати m +k способами.

Приклади:

1. Припустимо, що в ящику знаходиться n різнокольорових кульок. Довільним чином виймається 1 кулька. Скільки способами це можна зробити?

Відповідь: n методами.

Розподілимо ці n кульок по двох ящиках: в першу-m кульок, в другий-k кульок. Довільним чином з довільно обраного ящика виймається 1 кулька. Скільки способами це можна зробити?

Рішення: З першого ящика кульку можна вийняти m способами, з другого-k способами. Тоді всього способів m+k=n.

2. Морський семафор.

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

Рішення: Загальна кількість складається з положень, коли обидва прапорці розташовані по різні сторонивід тіла сигнальника та положень, коли вони розташовані по одну сторону від тіла сигнальника. При підрахунку числа можливих положень застосовується правило суми.

Правило твору:Якщо об'єкт А можна вибрати m способами, а після кожного такого вибору інший об'єкт можна вибрати (незалежно від вибору об'єкта А) k способами, то пари об'єктів «А і В» можна вибрати m *k способами.

Приклади:

1. Скільки двоцифрових чиселіснує?

Рішення: Число десятків може бути позначено будь-якою цифрою від 1 до 9. Число одиниць може бути позначено будь-якою цифрою від 0 до 9. Якщо число десятків дорівнює 1, то число одиниць може бути будь-яким (від 0 до 9). Таким чином, існує 10 двоцифрових чисел, з числом десятків-1. Аналогічно міркуємо і для будь-якого іншого числа десятків. Тоді можна порахувати, що існує 9 *10 = 90 двоцифрових чисел.

2. Є 2 ящики. В одному лежить m різнокольорових кубиків, а в іншому - k різнокольорових кульок. Скільки способами можна вибрати пару «Кубик-кулька»?

Рішення: Вибір кульки залежить від вибору кубика, і навпаки. Тому число способів, якими можна вибрати цю пару дорівнює m * k .

3. Генеральна сукупність без повторень та вибірки без повторень.

Генеральна сукупність без повторень- це набір деякого кінцевого числа різних елементів a 1, a 2, a 3, ..., a n.

Приклад:Набір з n різнокольорових клаптиків.

Вибіркою обсягуk (kn)називається група з m елементів цієї генеральної сукупності.

Приклад:Строката стрічка, зшита з m різнокольорових клаптиків, вибраних з даних n .

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

- кількість розміщень з n по k.

Кількість розміщень з n по k можна визначити наступним способом: перший об'єкт вибірки можна вибрати n способами, далі другий об'єкт можна вибрати n -1 способом і т.д.

Перетворивши цю формулу, маємо:

Слід пам'ятати, що 0!=1.

Приклади:

1. У першій групі класу А першості з футболу бере участь 17 команд. Розігруються медалі: золото, срібло та бронза. Скільки способами вони можуть бути розіграні?

Рішення:Комбінації команд-переможців відрізняються друг від друга складом і порядком прямування елементів, тобто. є розміщеннями з 17 до 3.

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

Рішення:Комбінації керівного складу суспільства відрізняються одна від одної складом і порядком прямування елементів, тобто. є розміщеннями з 25 до 4.

Перестановками без повторень із nелементівназиваються розміщення без повторень з n елементів з n , тобто. Розміщення відрізняються один від одного лише порядком прямування елементів.

Число перестановок.

Приклади:

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

Рішення:Маємо перестановки із 5 елементів.2. Скількими способами можна зібрати 6 різнокольорових клаптиків у строкату стрічку?
Рішення:Маємо перестановки із 6 елементів.

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

- число поєднань з n по k

Елементи кожного зпоєднань можна розставитиметодами. ТодіПриклади:

1. Якщо у півфіналі першості з шахів бере участь 20 осіб, а у фінал виходять лише троє, то скільки способів і можна визначити цю трійку?

Рішення:У даному випадкупорядок, у якому розташовується ця трійка, не суттєвий. Тому трійки, що вийшли у фінал, є поєднаннями із 20 по 3.

2. Скільки можна вибрати трьох делегатів з десяти осіб на конференцію?

Рішення:У разі порядок, у якому розташовується ця трійка, не суттєвий. Тому трійки делегатів є поєднаннями із 10 по 3.

Конспект:

4. Застосування графів (схем) під час вирішення комбінаторних завдань.

У разі коли кількість можливих виборів на кожному кроці залежить від того, які елементи були обрані раніше, можна зобразити процес складання комбінацій у вигляді «дерева». Спочатку з однієї точки проводять стільки відрізків, скільки різних виборів можна зробити першому кроці. З кінця кожного відрізка проводять стільки відрізків, скільки можна зробити виборів на другому кроці, якщо на першому кроці було обрано цей елемент і т.д.

Завдання:

При складанні команд космічного кораблявраховується питання психологічної сумісності учасників подорожі. Необхідно скласти команду космічного корабля з трьох осіб: командира, інженера та лікаря. На місце командира є 4 кандидати: a 1 , a 2 , a 3 , a 4 .На місце інженера-3:b 1 , b 2 , b 3 . На місце лікаря-3: c1, c2, c3. Проведена перевірка показала, що командирa 1 психологічно сумісний з інженерами b 1 та b 3та лікарями c 1 та c 3 . Командир a 2 – з інженерами b 1 та b 2 . та всіма лікарями. Командирa 3 - з інженерамиb 1 та b 2та лікарямиз 1 і з 3. Командир a 4 -з усіма інженерами та лікарем з 2 . Крім того, інженерb 1 не сумісний із лікарем c 3, b 2 - з лікарем з 1 і b 3 - з лікарем c 2 . Скільки способами за цих умов може бути складена команда корабля?

Рішення:

Складемо відповідне «дерево».

Відповідь: 10 комбінацій.

Таке дерево є графом і застосовується на вирішення комбінаторних завдань.

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

Основна формула комбінаторики

Нехай є k груп елементів, причому i-ягрупа складається із n i елементів. Виберемо по одному елементу з кожної групи. Тоді загальне число N способів, якими можна зробити такий вибір, визначається співвідношенням N = n 1 * n 2 * n 3 * ... * n k .

приклад 1.Пояснимо це правило простому прикладі. Нехай є дві групи елементів, причому перша група складається з n 1 елементів, а друга - n 2 елементів. Скільки різних пар елементів можна скласти із цих двох груп, таким чином, щоб у парі було по одному елементу від кожної групи? Допустимо, ми взяли перший елемент із першої групи і, не змінюючи його, перебрали всі можливі пари, змінюючи лише елементи з другої групи. Таких пар цього елемента можна скласти n 2 . Потім ми беремо другий елемент із першої групи і також складаємо для нього всі можливі пари. Таких пар також буде n 2 . Так як у першій групі всього n 1 елемент, всього можливих варіантів буде n 1 * n 2 .

приклад 2.Скільки трицифрових парних чисел можна становити з цифр 0, 1, 2, 3, 4, 5, 6, якщо цифри можуть повторюватися?
Рішення: n 1 =6 (т.к. як перша цифра можна взяти будь-яку цифру з 1, 2, 3, 4, 5, 6), n 2 =7 (т.к. як другу цифру можна взяти будь-яку цифру з 0 , 1, 2, 3, 4, 5, 6), n 3 =4 (т.к. як третя цифра можна взяти будь-яку цифру з 0, 2, 4, 6).
Отже, N = n 1 * n 2 * n 3 = 6 * 7 * 4 = 168.

У тому випадку, коли всі групи складаються з однакового числаелементів, тобто. n 1 =n 2 =...n k =n вважатимуться, кожен вибір виробляється з однієї й тієї групи, причому елемент після вибору знову повертається у групу. Тоді число всіх способів вибору дорівнює n k. Такий спосіб вибору комбінаторики носить назву вибірки із поверненням.

приклад 3.Скільки всіх чотирицифрових чисел можна становити з цифр 1, 5, 6, 7, 8?
Рішення.До кожного розряду чотиризначного числа є п'ять можливостей, отже N=5*5*5*5=5 4 =625.

Розглянемо безліч, які з n елементів. Це безліч у комбінаториці називається генеральною сукупністю.

Число розміщень з n елементів m

Визначення 1.Розміщенням з nелементів по mу комбінаториці називається будь-який упорядкований набірз mрізних елементів, вибраних з генеральної сукупності в nелементів.

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

Число розміщень у комбінаториці позначається A n m і обчислюється за такою формулою:

Примітка: n!=1*2*3*...*n (читається: "ен факторіал"), крім того вважають, що 0!=1.

Приклад 5. Скільки існує двозначних чисел, у яких цифра десятків та цифра одиниць різні та непарні?
Рішення:т.к. непарних цифр п'ять, саме 1, 3, 5, 7, 9, це завдання зводиться до вибору і розміщення дві різні позиції двох із п'яти різних цифр, тобто. вказаних чиселбуде:

Визначення 2. Поєднаннямз nелементів по mу комбінаториці називається будь-який невпорядкований набірз mрізних елементів, вибраних з генеральної сукупності в nелементів.

Приклад 6. Для множини (1, 2, 3) поєднаннями є (1, 2), (1, 3), (2, 3).

Число поєднань з n елементів m

Число поєднань позначається C n m і обчислюється за такою формулою:

Приклад 7.Скільки способами читач може вибрати дві книжки із шести наявних?

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

Перестановки з n елементів

Визначення 3. Перестановкоюз nелементів називається будь-який упорядкований набірцих елементів.

Приклад 7a.Різними перестановками множини, що складається з трьох елементів (1, 2, 3) є: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), ( 3, 2, 1), (3, 1, 2).

Число різних перестановок з елементів n позначається P n і обчислюється за формулою P n = n!.

Приклад 8.Скільки способами сім книг різних авторівЧи можна розставити на полиці в один ряд?

Рішення:це завдання про кількість перестановок семи різних книг. Є P 7 =7!=1*2*3*4*5*6*7=5040 способів здійснити розміщення книг.

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

По-перше, від того, з якої кількості елементів ми можемо комбінувати їх набори (наскільки велика Генеральна сукупністьелементів).

По-друге, результат залежить від того, який розмір набори елементів нам потрібні.

І останнє, важливо знати, чи є для нас суттєвим порядок елементів у наборі. Пояснимо останній чинник на такому прикладі.

Приклад 9.на батьківських зборахє 20 осіб. Скільки існує різних варіантів складу батьківського комітету, якщо до нього мають увійти 5 осіб?
Рішення:У цьому прикладі нас не цікавить порядок прізвищ у списку Комітету. Якщо в результаті в його складі будуть одні й ті ж люди, то за змістом для нас це один і той самий варіант. Тому ми можемо скористатися формулою для підрахунку числа поєднаньіз 20 елементів по 5.

Інакше будуть справи, якщо кожен член комітету спочатку відповідає за певний напрямок роботи. Тоді при тому самому списковому складі комітету, всередині нього можливо 5! варіантів перестановокякі мають значення. Кількість різних (і за складом, і за сферою відповідальності) варіантів визначається у цьому випадку числом розміщеньіз 20 елементів по 5.

Завдання для самоперевірки
1. Скільки трицифрових парних чисел можна становити з цифр 0, 1, 2, 3, 4, 5, 6, якщо цифри можуть повторюватися?

2. Скільки існує п'ятизначних чисел, які однаково читаються зліва направо та праворуч наліво?

3. У класі десять предметів та п'ять уроків на день. Скільки способами можна скласти розклад на один день?

4. Скільки можна вибрати 4 делегати на конференцію, якщо в групі 20 осіб?

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

6. З трьох математиків та десяти економістів треба скласти комісію, що складається з двох математиків та шести економістів. Скільки способами це можна зробити?

Мета заняття:вміти застосовувати основні формули комбінаторики та знати умови застосування цих формул; знати властивості біномних коефіцієнтів та вміти визначати розкладання бінома при конкретних значеннях n.

План заняття:

1. Число розміщень.

2. Число перестановок.

3. Число поєднань.

4. Повторення.

5. Біном Ньютона. Трикутник Паскаля.

Методичні вказівкиз вивчення теми

У багатьох практичних випадках виникає необхідність підрахувати кількість можливих комбінацій об'єктів, які відповідають певним умовам. Такі завдання називають комбінаторними. Різноманітність комбінаторних завдань не піддається вичерпному опису, але серед них є цілий рядособливо часто зустрічаються, котрим відомі способи підрахунку.

Комбінаторика- область математики, в якій вивчаються питання про те, скільки різних комбінацій, підпорядкованих тим чи іншим умовам, можна скласти з елементів, що належать даному безлічі. Термін «комбінаторика» походить від латинського слова combina – поєднувати, з'єднувати.

Нехай є кілька n елементів: x 1, x 2, x 3, …, x n .

З цієї множини можна утворити різні підмножини, тобто вибірки, кожна з яких містить m елементів (0 ≤ m ≤ n). Розрізняють упорядковані вибірки (розміщення), перестановки та невпорядковані вибірки (поєднання).

Розміщення

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

Кількість розміщень з nелементів по mелементів позначають (А – перша літера французького слова arrangement, що означає розміщення, упорядкування) і обчислюють за формулою:

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

твір n натуральних чиселвід 1 до nпозначається символом n! (nфакторіал), тобто

Наприклад, 2! =

5!=

Зауважимо, що зручно розраховувати 0!, вважаючи за визначенням, 0!=1.

Приклади:

З останніх двох формул випливає, що

приклад.

В однокруговому турнірі з футболу беруть участь 8 команд. Скільки є варіантів призової трійки?

Рішення: Так як порядок команд у призовій трійці важливий, то ми маємо справу з розміщеннями Тоді

(Варіантів).

приклад.

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

Рішення:

(Спосібів).

приклад.

Скільки можна скласти телефонних номерівіз 5 цифр так, щоб у кожному окремо взятому номері всі цифри були різними?

(Телефонних номерів).

Перестановки

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

Число всіх можливих перестановок з n елементів позначають P n (P – перша буква французького слова permutation, що означає перестановка) і обчислюють за такою формулою:

приклад.

У фінальному забігу на 100 метрів беруть участь 8 спортсменів. Скільки існує варіантів протоколу забігу?

Рішення:

У разі йдеться про всіх перестановках з 8 елементів. Тоді (варіантів)

приклад.

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

Рішення:

(способів)

приклад.

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

Рішення:

(Спосібів).

Поєднання

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

Число поєднань обчислюють за такою формулою: (С - перша літера французького слова combinasion).

приклад.

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

Рішення:

(Спосібів).

приклад.

Скільки можна вибрати три деталі з ящика, що містить 15 деталей?

Рішення:

(Спосібів).

Інший вид формул числа розміщень та числа поєднань

; , тобто .

Властивості числа поєднань:

5)

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

Правило суми.Якщо деякий об'єкт А може бути обраний із сукупності об'єктів n способами, а інший об'єкт – k способами, то об'єкт «або А, або В» можна вибрати n + k способами.

Правило твору.Якщо деякий об'єкт А може бути обраний із сукупності об'єктів n способами і після кожного такого вибору інший об'єкт - k способами, то пара об'єктів (А, В) у зазначеному порядку може бути обрана n×k способами.

Якщо деякі елементи повторюються, то цьому випадку комбінації з повтореннями обчислюють за іншими формулами.

Розміщення з повтореннями

Число розміщень по mелементів з повтореннями з nрізних елементів одно n m,тобто

приклад.

З цифр 1,2,3,4,5 можна становити 5 3 =125 трицифрових чисел, якщо в тому самому числі можуть траплятися і однакові цифри.

Перестановки із повтореннями

Якщо серед nелементів є n 1елементів одного виду, n 2елементів іншого виду і т.д., то число перестановок із повтореннями

де

приклад.

Скільки різних перестановок літер можна зробити у слові "математика"?

Рішення:

Поєднання з повтореннями

Число поєднань з повтореннями з nрізних елементів по mелементів дорівнює числу поєднань без повторень з ( n+m-1) різних елементів по mелементів:

приклад.

Знайти число поєднань із повтореннями з чотирьох елементів a, b, c, dпо 3 елементи.

Рішення:

Шукане число буде

Біном Ньютона

Для довільного позитивного цілого числа n справедлива така формула:

Це біном Ньютона. Коефіцієнти називаються біноміальними коефіцієнтами.

При n = 2 отримаємо формулу;

При n = 3 отримаємо формулу.

приклад.Визначити розкладання за n=4.

Рішення:

Біноміальні коефіцієнти мають ряд властивостей:

2. ;

Розглянемо наступний трикутник:

………………………….

Рядок під номером n містить біномні коефіцієнти розкладання. Скориставшись властивістю можна помітити, що кожен внутрішній елементтрикутника дорівнює сумідвох елементів, розташованих над ним, а бічні елементи трикутника – одиниці:

……………………….

Це трикутник Паскаля. Він дозволяє швидко знайти значення біномних коефіцієнтів.

У російськомовної літературі перестановки, складені з різних елементів вибором по m елементів, які відрізняються або складом елементів, або їх порядком, зазвичай називають розміщеннями, а під перестановками розуміють всю сукупність комбінацій, що складаються з одних і тих же n різних елементів і відрізняються тільки порядком їх розташування. У цьому сенсі число всіх можливих перестановок для множини з n різних елементів вважається за формулою факторіалу Pn = n! або Excel «=ФАКТР(N)» (див. рис. № 1)

Наприклад, якщо ввести «=ПЕРЕСТ(3;2)», отримаємо 6. Це 6 комбінації: (1,2), (2,1), (1,3), (3,1), (2,3) , (3,2).

І це вбудована функція «=ЧИСЛКОМБ(N;K)» видає комбінаторну формулу, звану в нас «Кількість поєднань». У російськомовної літературі називають перестановки, складені з n різних елементів вибором по m елементів, які відрізняються лише складом елементів, а порядок їх вибору байдужий (див. рис, №4)

Під час використання вбудованих функцій використовуйте «Довідка з цієї функції». Наприклад:

Завдання для самостійного рішення

1. Обчислити:

2. Обчислити:

3. Обчислити:

4. Знайти nякщо 5С n 3 =

5. Знайти n, якщо

6. Знайти n, якщо

7. Знайти n, якщо

8. Знайти n, якщо , k n

9. Розв'язати рівняння

10. Вирішити систему

11. Скільки можна скласти сигналів із 6 прапорців різного кольору, взятих по 2?

12. Скільки можна вибрати чотири особи на чотири різні посади з дев'яти кандидатів?

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

14. У класі 10 навчальних предметівта 5 різних уроківв день. Скільки способами можуть бути розподілені уроки в один день?

15. Скільки можна записати чотирицифрових чисел, використовуючи без повторення всі 10 цифр?

16. Фірма робить вибір із дев'яти кандидатів на три різні посади. Скільки є способів такого вибору?

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

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

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

20. На зборах виступатимуть 6 ораторів. Скільки способами їх прізвища можна розмістити у списку?

21. Скільки трицифрових чисел можна становити з цифр 1, 2, 3, якщо кожна цифра входить до зображення числа лише один раз?

22. Скільки різними способами можна розставити 10 різних книг на полиці, щоб 4 книги стояли поруч?

23. В однокруговому турнірі з футболу беруть участь 8 команд. Скільки всього матчів буде зіграно?

24. Із 25 студентів потрібно обрати трьох делегатів на конференцію. Скільки способами це можна зробити?

25. Скільки можна вибрати дві деталі з ящика, що містить 10 деталей?

26. У колоді 36 карт, їх 4 туза. Скільки способами можна витягти 6 карт так, щоб серед них було 2 тузи?

27. Комплексна бригада складається з двох малярів, трьох штукатурів та одного столяра. Скільки різних бригад можна створити з робочого колективу, в якому 15 малярів, 10 штукатурів та 5 столярів?

28. У відбірному турнірі за 3 путівки на чемпіонат світу беруть участь 10 команд. Скільки існує варіантів "щасливої ​​трійки"?

29. З 12 осіб обирають чотирьох для призначення на 4 однакові посади. Скільки можна зробити такий вибір?

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

31. На площині дано nточок, з яких ніякі три не лежать на одній прямій. Знайти число прямих, які можна одержати, з'єднуючи точки попарно.

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

33. Скільки існує різних семизначних номерів?

34. Нехай літери деякої абетки утворюються як послідовність точок, тире та пробілів. Скільки літер можна утворити, якщо використовувати 5 символів?

35. При грі в бридж між чотирма гравцями розподіляється колода карток у 52 аркуші по 13 карток кожному гравцю. Скільки існує різноманітних способів роздати карти?

36. У поштовому відділенніпродаються листівки п'яти видів. Визначити кількість способів купівлі семи листівок.

37. Два колекціонери обмінюються марками. Знайти кількість способів обміну, якщо перший колекціонер обмінює 3 марки, а другий – 6 марок. (Обмін відбувається за однією маркою).

38. В одного студента 6 книг з математики, а в іншого – 5. Скільки способами вони можуть обміняти 2 книги одного на 2 книги іншого?

39. Скільки різних перестановок літер можна зробити за словами: «замок», «ротор», «обороноспроможність», «дзвін», «семінар»?

40. Скільки різними способами можна розмістити в 9 клітинках такі 9 букв: а, а, а, б, б, б, в, в, в?

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

42. Скільки способами з колоди в 52 карти можна витягти 6 карт, що містять туза і короля однієї масті?

43. Визначити розкладання за n=5.

44. Визначити розкладання за n=8.

45. Знайти член розкладання , який містить x (тобто містить x нульової ступеня).

46. ​​Знайти шостий член розкладання , якщо біноміальний коефіцієнттретього від кінця члена дорівнює 45.

47. У розкладанні коефіцієнт третього члена на 44 більше за коефіцієнт другого члена. Знайти вільний член, тобто член розкладання, що не залежить від x (членом, що не залежить від x, буде той, який містить x в нульовому ступені).

48. У розкладанні бінома знайти члени, які містять ірраціональності.

49. Знайти номер члена розкладання , який містить a та b в однакових ступенях.

Практичне заняття №2

(інтерактивне заняття у малих групах)

Булеві функції

Мета заняття:вміти будувати різні булеві функції, перевіряти еквівалентність булевих формул (використовуючи таблицю істинності), визначати суттєві та фіктивні змінні.

План заняття:

1. Основні операції

2. Булеві функції від n змінних

3. Основні еквівалентності

Число розміщень без повторень з n по k n kрізними координатами.

Число розміщень без повторень знаходиться за формулою:

Приклад:Скільки способів можна побудувати 3-значне число з різними цифрами, що не містить цифри 0?

Кількість цифр
, розмірність вектора з різними координатами

Число розміщень із повтореннями

Число розміщень з повтореннями n по k - Це число способів, скільки можна з nрізних елементів побудувати векторів з kкоординатами, серед яких можуть бути однакові.

Число розміщень із повтореннями знаходиться за формулою:

.

Приклад:Скільки слів довжини 6 можна становити з 26 букв латинського алфавіту?

Кількість літер
, розмірність вектора

Число перестановок без повторень

Число перестановок без повторень з n елементів – це число способів, скільки можна розташувати на n різних місцях nрізних елементів.

Число перестановок без повторень знаходиться за формулою:

.

Примітка:Потужність шуканої множини Азручно шукати за формулою:
, де х- Число способів вибрати потрібні місця; у- Число способів розмістити на них потрібні елементи; z- Число способів розташувати інші елементи на місцях, що залишилися.

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

Усього способів розставити 5 книг на 5-ти місцях – одно = 5! = 120.

У завданні х- Число способів вибрати два місця поруч, х= 4;у- Число способів розмістити дві книги на двох місцях, у = 2! = 2; z- Число способів розмістити інші 3 книги на решті 3-х місцях, z= 3! = 6. Значить
= 48.

Число поєднань без повторень

Число поєднань без повторень з n по k - Це число способів, скільки можна з nрізних елементів вибрати kштук без урахування порядку.

Число поєднань без повторень знаходиться за формулою:

.

Властивості:

1)
; 2)
; 3)
;

4)
; 5)
; 6)
.

приклад.У урні 7 куль. Із них 3 білих. Навмання вибирають 3 кулі. Скільки способами це можна зробити? У кількох випадках серед них буде один білий.

Усього способів
. Щоб отримати кількість способів вибрати 1 біла куля(з 3-х білих) та 2 чорних кулі (з 4-х чорних), треба перемножити
і
Таким чином, шукана кількість способів

Вправи

1. З 35 учнів клас за підсумками року мали “5” з математики – 14 людина; з фізики – 15 осіб; з хімії – 18 осіб; з математики та фізики – 7 осіб; з математики та хімії – 9 осіб; з фізики та хімії – 6 осіб; з усіх трьох предметів – 4 особи. Скільки людей мають “5” із зазначених предметів? Скільки людина не має “5” із зазначених предметів? Чи має “5” тільки з математики? Чи має “5” тільки з двох предметів?

2. У групі з 30 студентів кожен знає принаймні один іноземна мова– англійська чи німецька. Англійську знають 22 студенти, німецьку – 17. Скільки студентів знають обидві мови? Скільки студентів знають німецьку мову, але не знають англійську?

3. У 20 кімнатах гуртожитку інституту Дружби Народів мешкають студенти з Росії; у 15 – з Африки; у 20 – із країн Південної Америки. Причому у 7 – живуть росіяни та африканці, у 8 – росіяни та південноамериканці; у 9 – африканці та південноамериканці; в 3 - і росіяни, і американські, і африканці. У кількох кімнатах мешкають студенти: 1) лише з одного континенту; 2) лише з двох континентів; 3) лише африканці.

4. Кожен із 500 студентів зобов'язаний відвідувати хоча б один із трьох спецкурсів: з математики, фізики та астрономії. Три спецкурси відвідують 10 студентів, з математики та фізики – 30 студентів, з математики та астрономії – 25; спецкурс лише з фізики – 80 студентів. Відомо також, що спецкурс з математики відвідують 345 студентів, з фізики – 145, з астрономії – 100 студентів. Скільки студентів відвідують спецкурс лише з астрономії? Скільки студентів відвідують два спецкурси?

5. Староста курсу подав наступний звіт з фізкультурної роботи. Усього – 45 студентів. Футбольна секція – 25 осіб, баскетбольна секція – 30 осіб, шахова секція – 28 осіб. При цьому, 16 осіб одночасно відвідують футбольну та баскетбольну секції, 18 – футбольну та шахову, 17 – баскетбольну та шахову, 15 осіб відвідують усі три секції. Поясніть, чому звіт не було прийнято.

6. В акваріумі 11 рибок. З них 4 червоні, інші золоті. Навмання вибирають 4 рибки. Скільки способами це можна зробити? Знайти кількість способів зробити це так, щоб серед них буде: 1) рівно одна червона; 2) рівно 2 золоті; 3) хоча б одна червона.

7. У списку 8 прізвищ. З них 4 – жіночі. Скільки способами їх можна розділити на дві рівні групи те щоб у кожної була жіноча прізвище?

8. З колоди в 36 карток вибирають 4 . Скільки способів зробити це так, щоб: 1) усі карти були різних мастей; 2) усі карти були однієї масті; 3) 2 червоні та 2 чорні.

9. На картках розрізної абетки дано букви К, К, К, У, У, А, Е, Р. Скільки способів скласти їх у ряд так, щоб вийшло «кукареку».

10. Дано картки розрізаної абетки з літерами О, Т, О, Л, О, Р, І, Н, Р, О, Л, О, Г. Скільки способів скласти їх так, щоб вийшло слово «отолоринголог».

11. Дано картки нарізної абетки з літерами Л, І, Т, Е, Р, А, Т, У, Р, А. Скільки способів скласти їх у ряд так, щоб вийшло слово «література».

12. 8 осіб стають у чергу. Скільки способів зробити це так, щоб дві певні людини А і Б виявилися: 1) поруч; 2) на краях черги;

13. 10 людей сідають за круглий стілна 10 міс. Скількими способами це можна зробити так, щоб поряд виявилися: 1) дві певні людини А та Б; 2) три певні особи А, Б і С.

14. З 10 арабських цифр становлять 5-значний код. Скільки способами це можна зробити так, щоб: 1) усі цифри були різними; 2) останньому місці парна цифра.

15. З 26 букв латинського алфавіту (серед них 6 голосних) складається шестилітерне слово. Скільки способами це можна зробити так, щоб у слові були: 1) рівно одна літера «а»; 2) рівно одна голосна літера; рівно дві літери "а"; в) рівно дві голосні.

16. Скільки чотиризначних чисел поділяються на 5?

17. Скільки чотиризначних чисел з різними цифрами поділяються на 25?

19. Кинуті 3 гральні кістки. У кількох випадках випала: 1) рівно 1 «шістка»; 2) хоча б одна "шістка".

20. Кинуті 3 гральні кістки. У кількох випадках буде: 1) усі різні; 2) рівно два однакові числа очок.

21. Скільки слів із різними літерами можна скласти з алфавіту а, в, с, d. Перелічити їх у лексикографічному порядку: abcd, abcd….