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

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

Правило множення (основна формула комбінаторики)

Загальне числоспособів, якими можна вибрати по одному елементу з кожної групи і розставити їх у певному порядку (тобто отримати впорядковану сукупність), так само:

Приклад 1

Монету підкинули 3 рази. Скільки різних результатів кидання можна очікувати?

Рішення

Перша монета має альтернативи - або орел, або решка. Для другої монети також є альтернативи тощо, тобто. .

Потрібна кількість способів:

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

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

Приклад 2

На полиці 30 книг, з них 20 математичних, 6 технічних та 4 економічних. Скільки існує способів вибору однієї математичної чи економічної книги.

Рішення

Математична книга може бути обрана засобами, економічна - засобами.

За правилом суми існує спосіб вибору математичної чи економічної книги.

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

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

Розміщення без повтореньколи відібраний елемент перед відбором наступного не повертається в генеральну сукупність. Такий вибір називається послідовним вибором без повернення, яке результат – розміщенням без повторень з елементів по .

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

Приклад 3

Розклад дня складається з 5 різних уроків. Визначте кількість варіантів розкладу при виборі 11 дисциплін.

Рішення

Кожен варіант розкладу представляє набір 5 дисциплін з 11, від інших варіантів як складом, і порядком прямування. тому:

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

Приклад 4

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

Рішення

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

Розміщення з повтореннямиколи відібраний елемент перед відбором наступного повертається в генеральну сукупність. Такий вибір називається послідовним вибором з поверненням, яке результат - розміщенням з повтореннями з елементів по .

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

Приклад 5

Ліфт зупиняється на 7 поверхах. Скільки способами можуть вийти цих поверхах 6 пасажирів, що у кабіні ліфта?

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

Рішення

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

Поєднання

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

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

Число поєднань з елементів дорівнює:

Приклад 6

У ящику 9 яблук. Скільки можна вибрати 3 яблука з ящика?

Рішення

Кожен варіант вибору складається з 3 яблук і відрізняється від інших тільки складом, тобто є поєднанням без повторень з 9 елементів:

Кількість способів, якими можна вибрати 3 яблука з 9:

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

Число поєднань з повтореннями з елементів за :

Приклад 7

Поштою продають листівки 3 видів. Скільки можна купити 6 листівок?

Це завдання знайти число поєднань з повтореннями з 3 по 6:

Розбиття множини на групи

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

Число розбиття на груп, коли в першу потрапляють елементів, в другу - елементів, k-у групу- елементів, так само:

Приклад 8

Групу з 16 осіб потрібно розбити на три підгрупи, у першій з яких має бути 5 осіб, у другій – 7 осіб, у третій – 4 особи. Скільки способами це можна зробити?

Рішення

Тут

Число розбиття на 3 підгрупи:

Викладається поняття геометричного законурозподілу дискретної випадкової величиниі розглядається приклад розв'язання задачі. Наведено формули математичного очікуваннята дисперсії випадкової величини, розподіленої за геометричним законом.

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

Народження комбінаторики як розділу пов'язане з працями Б. Паскаля та П. Ферма з теорії азартних ігор. Великий внесок у розвиток комбінаторних методів зробили Г.В. Лейбніц, Я. Бернуллі та Л. Ейлер.

Французький філософ, письменник, математик та фізик Блез Паскаль (1623–1662) рано виявив свої видатні математичні здібності. Коло математичних інтересів Паскаля було дуже різноманітне. Паскаль довів одну
з основних теорем проективної геометрії (теорема Паскаля), сконструював підсумовуючу машину (арифмометр Паскаля), дав спосіб обчислення біноміальних коефіцієнтів (трикутник Паскаля), вперше точно визначив та застосував для доказу метод математичної індукції, зробив суттєвий крок у розвитку аналізу нескінченно малих, зіграв важливу рольу зародженні теорії ймовірності. У гідростатиці Паскаль встановив її основний закон (закон Паскаля). "Листи до провінціалу" Паскаля з'явилися шедевром французької класичної прози.

Готфрід Вільгельм Лейбніц (1646-1716) - німецький філософ, математик, фізик та винахідник, юрист, історик, мовознавець. У математиці поряд з І. Ньютоном розробив диференціальне та інтегральне обчислення. Важливий внесок зробив комбінаторику. З його ім'ям, зокрема, пов'язані теоретико-числові задачі.

Готфрід Вільгельм Лейбніц мав мало значну зовнішність і тому справляв враження досить непоказної людини. Одного разу в Парижі він зайшов у книжкову крамницю, сподіваючись придбати книгу свого знайомого філософа. На запитання відвідувача про цю книгу книготорговець, оглянувши його з голови до ніг, насмішкувато кинув: “Навіщо вона вам? Невже ви здатні читати такі книги? Не встиг вчений відповісти, як до крамниці увійшов сам автор книги зі словами: "Великому Лейбницю привіт та повага!" Продавець ніяк не міг зрозуміти, що перед ним справді знаменитий Лейбніц, книги якого мали великий попит серед учених.

Надалі важливу роль гратиме наступна

Лемма.Нехай у множині елементів, а у множині — елементів. Тоді число всіх різних пар, де дорівнюватиме.

Доведення.Дійсно, з одним елементом з множини ми можемо скласти таких різних пар, а всього в безлічі елементів.

Розміщення, перестановки, поєднання

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

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

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

Теорема.Число розміщень множини з елементів по елементів дорівнює

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

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

Рішення.Потрібна кількість трисмугових прапорів:

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

Так, всі різні перестановки множини з трьох елементів — це

Число всіх перестановок з елементів позначається (від початкової літери французького слова “permutation”, що означає “перестановка”, “переміщення”). Отже, число всіх різних перестановок обчислюється за формулою

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

Рішення.Потрібна кількість розміщення турів

За визначенням!

Визначення.Поєднаннями з різних елементів щодо елементів називаються комбінації, які складені з даних елементів щодо елементів і відрізняються хоча б одним елементом (інакше кажучи, -елементні підмножини даної множиниіз елементів).

Як бачимо, у поєднаннях на відміну розміщень не враховується порядок елементів. Число всіх поєднань з елементів за елементами у кожному позначається (від початкової літери французького слова “combinasion”, що означає “поєднання”).

Числа

Всі поєднання з множини по два — .

Властивості чисел (\sf C)_n^k

Дійсно, кожному -елементному підмножині даної -елементної множини відповідає одна і тільки одна -елементна підмножина тієї ж множини.

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

Трикутник Паскаля

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

Теорема.

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

1 спосіб. Вибираємо перший член послідовності, потім другий, третій тощо. член

2 спосіб. Виберемо спочатку елементів з цієї множини, а потім розташуємо їх у деякому порядку

Домножимо чисельник і знаменник цього дробу на:

приклад.Скільки способів можна у грі "Спортлото" вибрати 5 номерів з 36?

Шукана кількість способів

Завдання.

1. Номери машин складаються з 3 літер російського алфавіту (33 літери) та 4 цифр. Скільки існує різних номерів машин?
2. На роялі 88 кнопок. Скільки способами можна отримати послідовно 6 звуків?
3. Скільки є шестицифрових чисел, що діляться на 5?
4. Скільки способами можна розкласти 7 різних монет у три кишені?
5. Скільки можна скласти п'ятизначних чисел, десяткового записуяких хоча один раз зустрічається цифра 5?
6. Скільки способами можна посадити 20 осіб за круглим столом, Вважаючи способи однаковими, якщо їх можна отримати один з іншого рухом по колу?
7. Скільки є п'ятицифрових чисел, що діляться на 5, у запису яких немає однакових цифр?
8. На папері з картатою зі стороною клітини 1 см намальована коло радіуса 100 см, що не проходить через вершини клітин і не стосується сторін клітин. Скільки клітин може перетинати це коло?
9. Скільки способами можна розставити в ряд числа так, щоб числа стояли поруч і до того ж йшли в порядку зростання?
10. Скільки п'ятизначних чисел можна становити з цифр, якщо кожну цифру можна використати лише один раз?
11. Зі слова РОТ перестановкою букв можна отримати такі слова: ТОР, ОРТ, ОТР, ТРО, РТО. Їх називають анаграм. Скільки анаграм можна становити зі слова ЛОГАРИФМ?
12. Назвемо розбиттямнатурального числа; подання його у вигляді суми натуральних чисел. Ось, наприклад, всі розбиття числа:

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

Скільки існує різних розбиття числа на доданків?
13. Скільки існує трицифрових чисел з незростаючим порядком цифр?
14. Скільки існує чотирицифрових чисел з зростаючим порядком цифр?
15. Скільки способами можна розсадити в ряд 17 осіб, щоб і опинилися поряд?
16. дівчаток і хлопчиків розсаджуються довільним чином у ряді місць. Скільки способами можна їх розсадити так, щоб жодні дві дівчинки не сиділи поруч?
17. дівчаток і хлопчиків розсаджуються довільним чином у ряді місць. Скільки способами можна їх розсадити так, щоб всі дівчатка сиділи поряд?

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

Чим будемо займатись? У вузькому значенні комбінаторика - це підрахунок різних комбінацій, які можна скласти з деякої множини дискретнихоб'єктів. Під об'єктами розуміються якісь відокремлені предмети чи живі істоти - люди, звірі, гриби, рослини, комахи тощо. При цьому комбінаторику зовсім не хвилює, що безліч складається з тарілки манної каші, паяльника та болотяної жаби. Принципово важливо, що ці об'єкти піддаються перерахуванню – їх три (Дискретність)і суттєво те, що серед них немає однакових.

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

Перестановки, поєднання та розміщення без повторень

Не лякайтеся малозрозумілих термінів, тим більше деякі з них дійсно не дуже вдалі. Почнемо з хвоста заголовка - що означає « без повторень»? Це означає, що в даному параграфі будуть розглядатися множини, які складаються з різнихоб'єктів. Наприклад, … ні, кашу з паяльником і жабою пропонувати не буду, краще щось смачніше =) Уявіть, що перед вами на столі матеріалізувалося яблуко, груша і банан (за наявності таких ситуацію можна змоделювати і реально). Викладаємо фрукти зліва направо у такому порядку:

яблуко / груша / банан

Питання перше: Скільки способами їх можна переставити?

Одна комбінація вже записана вище та з іншими проблемами не виникає:

яблуко / банан / груша
груша / яблуко / банан
груша / банан / яблуко
банан / яблуко / груша
банан / груша / яблуко

Разом: 6 комбінацій або 6 перестановок.

Добре, тут не склало особливих труднощів перерахувати всі можливі випадки, але як бути, якщо предметів більше? Вже із чотирма різними фруктами кількість комбінацій значно зросте!

Жодних мук - 3 об'єкти можна переставити способами.

Питання друге: скільки можна вибрати а) один фрукт, б) два фрукти, в) три фрукти, г) хоча б один фрукт?

Навіщо обирати? Так нагуляли ж апетит у попередньому пункті – для того, щоб з'їсти! а) Один фрукт можна вибрати, очевидно, трьома способами - взяти або яблуко, грушу або банан.

Формальний підрахунок проводиться за формулі кількості поєднань:

Запис у даному випадкуслід розуміти так: «скількими способами можна вибрати 1 фрукт із трьох?»

б) Перерахуємо всі можливі поєднання двох фруктів:

яблуко та груша;
яблуко та банан;
груші та банан.

Кількість комбінацій легко перевірити за тією самою формулою:

Запис розуміється аналогічно: «скількими способами можна вибрати 2 фрукти з трьох?».

в) І, нарешті, три фрукти можна вибрати єдиним способом:

До речі, формула кількості поєднань зберігає сенс і для порожньої вибірки:
способом можна вибрати жодного фрукта – власне, нічого не взяти і все.

г) Скільки способами можна взяти хоча б одинфрукт? Умова «хоча б один» передбачає, що нас влаштовує 1 фрукт (будь-який) або 2 будь-яких фрукти або всі 3 фрукти:
способами можна вибрати хоча б один фрукт.

Для відповіді на наступне питаннямені потрібно два добровольці… …Ну що ж, якщо ніхто не хоче, тоді викликатиму до дошки =)

Питання третє: Скільки способами можна роздати по одному фрукту Даші та Наташі?

Для того, щоб роздати два фрукти, спочатку потрібно їх вибрати. Відповідно до пункту «бе» попереднього питання, зробити це можна засобами, перепишу їх заново:

яблуко та груша;
яблуко та банан;
груші та банан.

Але комбінацій зараз буде вдвічі більше. Розглянемо, наприклад, першу пару фруктів:
яблуком можна пригостити Дашу, а грушею – Наташу;
або навпаки - груша дістанеться Даші, а яблуко - Наталці.

І така перестановка можлива кожної пари фруктів.

В даному випадку працює формула кількості розміщень:

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

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

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

Зупинимося на кожному виді комбінацій.

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

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

Відмінною особливістю перестановок є те, що у кожній із них бере участь ВСІбезліч, тобто, Усеоб'єктів. Наприклад, дружна сім'я:

Завдання 1

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

Рішення: використовуємо формулу кількості перестановок:

Відповідь: 120 способами

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

Завдання 2

Скільки чотиризначних чисел можна становити з чотирьох карток із цифрами 0, 5, 7, 9?

Для того, щоб скласти чотиризначне число потрібно задіяти Усечотири картки (цифри на якихрізні! ) , і це дуже важлива передумова для застосування формули Очевидно, що, переставляючи картки, ми отримуватимемо різні чотиризначні числа, … стоп, а чи все тут гаразд? ;-)

Добре подумайте над завданням! Взагалі, це характерна рисакомбінаторних та ймовірнісних завдань – у них ПОТРІБНО ДУМАТИ. І найчастіше думати по-житейськи, як, наприклад, у розборі вступного прикладуз фруктами. Ні, звичайно, я не закликаю тупо опрацьовувати інші розділи математики, однак маю помітити, що ті самі інтегралиможна, можливо навчитися вирішуватичисто механічно.

Рішення та відповідь наприкінці уроку.

Збільшуємо обороти:

Поєднання

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

Поєднаннями називають різні комбінації з об'єктів, які вибрані з багатьох різних об'єктів, і які відрізняються один від одного хоча б одним об'єктом. Іншими словами, окремо взяте поєднання – це унікальна вибірка з елементів, у якій не важливий їхній порядок(Розташування). Загальна кількість таких унікальних поєднань розраховується за формулою .

Завдання 3

У ящику міститься 15 деталей. Скільки способами можна взяти 4 деталі?

Рішення: перш за все, знову звертаю увагу на те, що за логікою умови, деталі вважаються різними- навіть якщо вони насправді однотипні та візуально однакові (у цьому випадку їх можна, наприклад, пронумерувати) .

У задачі йдеться про вибірку з 4-х деталей, в якій немає значення їх « подальша доля- грубо кажучи, "просто вибрали 4 штуки і все". Таким чином, у нас є поєднання деталей. Вважаємо їх кількість:

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

Способами можна взяти 4 деталі із ящика.

Ще раз: що це означає? Це означає, що з набору 15 різних деталей можна скласти одну тисячу триста шістдесят п'ять унікальнихпоєднання 4-х деталей. Тобто кожна така комбінація з 4-х деталей відрізнятиметься від інших комбінацій хоча б однією деталлю.

Відповідь: 1365 способами

Формулі необхідно приділити саме пильну увагуоскільки вона є «хітом» комбінаторики. При цьому корисно розуміти і без жодних обчислень записувати «крайні» значення: . Що стосується розібраної задачі:

Єдиним способом можна взяти жодної деталі;
способами можна взяти 1 деталь (будь-яку з 15-ти);
способами можна взяти 14 деталей (при цьому якась одна з 15 залишиться в ящику);
- єдиним способом можна взяти усі п'ятнадцять деталей.

Рекомендую уважно ознайомитися з біномом Ньютона та трикутником Паскаля, за яким, до речі, дуже зручно виконувати перевірку обчислень при невеликих значеннях «ен».

Завдання 4

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

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

Завдання 4

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

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

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

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

Ну а висновків тут два:

По-перше, не все очевидне – очевидно;

І по-друге, не бійтеся вирішувати завдання «нестандартно»!

Щиро дякую за ваші листи, вони допомагають поліпшити якість навчальних матеріалів!

Розміщення

Або «просунуті» поєднання. Розміщеннями називають різні комбінації з об'єктів, які вибрані з багатьох різних об'єктів, і які відрізняються один від одного як складом об'єктів у вибірці, так і їх порядком. Кількість розміщень розраховується за формулою

Що наше життя? Гра:

Завдання 5

Боря, Діма та Володя сіли грати в «очко». Скільки способами їм можна здати по одній карті? (колода містить 36 карт)

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

Способами можна роздати 3 карти гравцям.

Є й інша схема рішення, яка, на мій погляд, навіть зрозуміліша:

способами можна витягти 3 карти з колоди.

Тепер давайте розглянемо якусь одну із семи тисяч ста сорокакомбінацій, наприклад: король пік, 9 черв'яків, 7 черв'яків. Висловлюючись комбінаторною термінологією, ці 3 карти можна «переставити» між Борею, Дімою та Володею засобами:

КП, 9Ч, 7Ч;
КП, 7Ч, 9Ч;
9Ч, КП, 7Ч;
9Ч, 7Ч, КП;
7Ч, КП, 9Ч;
7Ч, 9Ч, КП.

І аналогічний факт справедливий для будь-когоунікального набору із 3-х карт. А таких наборів, не забуваймо, ми нарахували. Не треба бути професором, щоб зрозуміти, що знайдену кількість поєднань слід помножити на шість:

Способами можна здати по одній карті 3-х гравців.

Фактично, вийшла наочна перевірка формули, Остаточний зміст якої ми прояснимо в наступному параграфі.

Відповідь: 42840

Можливо, у вас залишилося питання, а хто ж роздавав карти? …Напевно, викладач =)
І щоб нікому не було прикро, у наступному завданні візьме участь вся студентська група:

Завдання 6

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

Завдання про «розміщення» посад у колективі зустрічається дуже часто і є справжнісіньким баяном. Коротке рішеннята відповідь наприкінці уроку.

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

25) Що називають перестановками?

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

26) За якою формулою обчислюють число перестановок з різних елементів?

Перестановки.Візьмемо nрізних елементів: a 1 , a 2 , a 3 , …, a n . Переставлятимемо їх усіма можливими способами, Зберігаючи їх кількість і змінюючи лише порядок їх розташування. Кожна з отриманих у такий спосіб комбінацій називається перестановкою.Загальна кількість перестановок із n елементівпозначається P n. Це число дорівнює добутку всіх цілих чисел від 1 до n:

Символ n! (називається факторіал) - скорочений запис твору: 1 · 2 · 3 · … · ( n – 1) · n.

П р і м е р. Знайти число перестановок з трьох елементів: a, b, c.

Розв'язання. Відповідно до наведеної формули: P 3 = 1 · 2 · 3 = 6.
Справді, ми маємо 6 перестановок: abc, acb, bac, bca, cab, cba.

27) Що називають розміщеннями? Запишіть формулу, за якою обчислюють число розміщень з елементів n по m.

Розміщення- це упорядковані підмножини даної кінцевої множини.

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

Їх загальна кількість позначається: і дорівнює твору:

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

Розв'язання. Відповідно до формули отримаємо:

Ось ці розміщення: ab, ba, ac, ca, ad, da, bc, cb, bd, db, cd, dc.

28) Що називають поєднаннями? Запишіть формулу, за якою обчислюють число поєднань з n елементів m.

Поєднання без повторень з n елементів mє m-Елементне підмножина деякого n-Елементної множини.

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

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

Їхня загальна кількість позначається і може бути обчислена за формулою:

З цієї формули ясно, що

Зауважимо, що можна скласти лише одне поєднання з n елементів n , яке містить усі n елементів.Формула числа поєднань дає це значення, якщо прийняти, що 0! = 1 , що є визначенням 0! .

Відповідно до цього визначення отримаємо:

Загальну кількість поєднань можна обчислити, користуючись іншим виразом:

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

Рішення:

Ці поєднання: abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde.

29) За якою формулою обчислюється кількість перестановок із n елементів, якщо елементи повторюються?

Перестановкамиз n елементів називаються розміщення з цих nелементів по n (перестановки - окремий випадокрозміщень).

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

приклад . Візьмемо літери Б, А, Р . Які перестановки із цих літер можна отримати? Скільки таких наборів вийде, якщо: 1) літери у наборі не повторюються; 2) літера А повторюється двічі?

Рішення.

1. Вийдуть набори: БАР, БРА, АРБ, АБР, РАБ, РБА.

За формулою (3.3) отримуємо: наборів.

2. Вийдуть набори: БАРА, БРАА, БААР, ААРБ, ААБР, АБАР, АРАБ, АРБА, АБРА, РАБА, РААБ, РБАА.

За формулою (3.4) отримуємо: наборів.

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

Рішення.З цих шести цифр можна скласти Р 6 = 6! = 720 перестановок. Але числа, що починаються на нуль, не є шестизначними. Такі числа відрізняються друг від друга перестановкою п'яти інших цифр, отже, їх буде Р 5 = 120. Тому шестизначних чисел буде 720 - 120 = 600 чисел.

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

Рішення.Перша лінія шахівниці є 8 клітин, на яких і треба розмістити ці 8 фігур. Різні варіантирозташування відрізнятимуться лише порядком фігур, отже, це будуть перестановки з повтореннями Р 8 (2,2,2).

За формулою (3.4) одержуємо: способів.

30) Якою формулою визначається число розміщень з повтореннями з n елементів m елементів?

Розміщення

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

Кількість розміщень без повтореньз n по m (nрізних елементів) обчислюється за такою формулою:

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

Рішення.

1. Вийдуть такі набори: БА, БР, АР, АБ, РБ, РА .

За формулою (3.1) отримуємо: наборів.

2. Вийдуть набори: ББ, ХА, БР, АА, АБ, АР, РР, РБ, РА.

За формулою (3.2) одержуємо: набори.

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

Рішення.Випишемо кілька комбінацій: КККЖЗЗ, ЗЗЗЗЗЗ, КЖЗКЖЗ... Ми бачимо, що склад вибірки змінюється і порядок елементів суттєвий (адже якщо, наприклад, у вибірці КЖЗКЖЗ поміняти місцями К і Ж, ситуація на дорозі буде іншою). Тому застосовуємо формулу (3.2) та обчислюємо число розміщень із повтореннями з 3 по 6, отримуємо комбінацій.

31) Якою формулою визначається число поєднань із повтореннями з n елементів по m елементів?

Поєднання

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

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

приклад . Візьмемо літери Б, А, Р . Які поєднання цих букв, взятих по дві, можна отримати? Скільки таких наборів вийде, якщо: 1) літери у наборі не повторюються; 2) можна брати по дві однакові літери.

Рішення.

1. Вийдуть набори: БА (БА і АБ - той самий набір), АР і РБ

За формулою (3.5) отримуємо: наборів.

2. Вийдуть набори: ББ, ХА, БР, АА, АР, РР.

За формулою (3.6) одержуємо: наборів.

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

Рішення.Треба вибрати двох осіб із 20. Зрозуміло, що від порядку вибору нічого не залежить, тобто Іванов-Петров чи Петров-Іванов – це та сама пара чергових. Отже, це будуть поєднання із 20 по 2.

За формулою (3.5) отримуємо: методів.

приклад . У хлібному відділі є булки білого та чорного хліба. Скільки можна купити 6 булок хліба?

Рішення.Позначаючи булки білого та чорного хліба літерами Б і Ч, складемо кілька вибірок: ББББББ, ББЧЧББ, ЧЧЧЧЧБ, ... Склад змінюється від вибірки до вибірки, порядок елементів несуттєвий, отже це – поєднання з повтореннями з 2 по 6. За формулою (3.6 ) Отримуємо способів.

Зробимо перевірку та випишемо всі варіанти покупки: ББББББ, БББББЧ, ББББЧЧ, БББЧЧЧ, ББЧЧЧЧ, БЧЧЧЧЧ, ЧЧЧЧЧЧ. Їх справді 7.

32) Що називають сумою двох подій?

Сумой двох подійназивають подія, що полягає у появі події, або події, або обох цих подій.
Сумою кількох подійназивають подія, що полягає у появі хоча б однієї з цих подій.

33) Що називають твором двох подій?

Добутком двох подійназивають подію, що полягає у спільній появі цих подій.

34) Чому дорівнює ймовірність суми двох несумісних подій?

Подіяназивають незалежним від подіїякщо поява події не змінює ймовірності появи події, тобто якщо умовна ймовірність події дорівнює її безумовної ймовірності:
.
Властивість незалежності подій взаємно: якщо подія не залежить від події, то і подія не залежить від події.
Теорема.Імовірність спільної появи двох незалежних подійдорівнює добутку ймовірності цих подій:
.
Декілька подій називають попарно незалежними, якщо кожні два з них є незалежними.
Декілька подій називають незалежними у сукупностіякщо незалежні кожні два з них і незалежні кожна подія і всі можливі творирешти.

35) Сформулюйте теорему складання?

Ймовірність р(А+В) суми подій Аі Удорівнює

Р (А+В) = р (А) + р (У) – р (АВ). (2.2)

Доведення.

Доведемо теорему додавання для схеми випадків. Нехай п- Число можливих результатів досвіду, т А- Число результатів, сприятливих подій А, т В –число наслідків, сприятливих події У, а т АВ -число результатів досвіду, у яких відбуваються обидві події (тобто результатів, сприятливих твору АВ). Тоді число наслідків, за яких має місце подія А+В, одно т А + т В - т АВ(бо в сумі ( т А + т В)т АВвраховано двічі: як результати, сприятливі А, і результати, сприятливі У). Отже, ймовірність суми можна визначити за формулою 2,2 що потрібно довести.

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

Комбінаторика виникла XVI столітті. Перші комбінаторні завдання стосувалися азартних ігор. Сьогодні комбінаторні методивикористовуються для вирішення транспортних завдань, складання планів виробництва та реалізації продукції. Встановлено зв'язки між комбінаторикою та завданнями лінійного програмуваннястатистики. Комбінаторика використовується для складання та декодування шифрів, для вирішення інших проблем теорії інформації.

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

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

IМетод. Намагатимемося виписати всі такі числа. На першому місці може стояти будь-яка цифра крім 0. Наприклад, 2. На другому місці будь-яка цифра з 0, 4, 6 і 8. Нехай 0. Тоді як третю цифру можна вибрати будь-яку з 4, 6, 8. Отримуємо три числа

Замість 0 на друге місце можна було поставити 4, тоді третє цифрою можна записати або 0 або 6, або 8:

Розмірковуючи аналогічно, отримуємо ще дві трійки тризначних чисел із цифрою 2 на першому місці:

Інших, окрім виписаних 12-ти, тризначних чисел із цифрою 2 на першому місці, і задовольняють умові, немає.

Якщо на першому місці записати цифру 4, а решту вибирати із цифр 0, 2, 6, 8, то отримаємо ще 12 чисел:

По стільки тризначних чисел можна скласти з цифрою 6 на першому місці і цифрою 8 на першому місці. Отже, потрібна кількість:

Ось ці числа:

204, 206, 208, 240, 246, 248, 260, 264, 268, 280, 284, 286;

402, 406, 408, 420, 426, 428, 460, 462, 468, 480, 482, 486;

602, 604, 608, 620, 624, 628, 640, 642, 648, 680, 682, 684;

802, 804, 806, 820, 824, 826, 840, 842, 846, 860, 862, 864.

Відповідь: 48. ◄

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

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

Комбінаторне правило додавання(правило "або") — одне з основних правил комбінаторики, яке стверджує, що якщо є n елементів та елемент A 1можна вибрати m 1 способами, елемент A 2можна вибрати m 2 A n можна вибрати m n способами, то вибрати або A 1, або A 2, або, і так далі, A n можна, можливо

m 1 + m 2 + ... + m n

методами.

Наприклад, вибрати подарунок дитині з 9 машинок, 7 плюшевих ведмедів та 3 залізницьможна, можливо

методами.

Відповідь: 19. ◄

Правило множення (правило "і") - Ще одне з важливих правилкомбінаторики. Згідно з ним, якщо елемент A 1можна вибрати m 1 способами, елемент A 2можна вибрати m 2 способами і так далі, елемент A n можна вибрати m n способами, то набір елементів ( A 1, A 2, ... , A n ) можна вибрати

m 1 · m 2 · ... · m n

методами.

Наприклад.

1) Вибрати дитині в подарунок машинку, плюшевого ведмедя та залізницю, вибираючи з 9 машинок, 7 плюшевих ведмедів та 3 залізниць, можна

9 · 7 · 3 = 189

методами.

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

2) Скористаємося правилом множення для розв'язання задачі, вже розглянутої вище: Скільки трицифрових чисел можна становити з цифр 0, 2, 4, 6, 8, використовуючи в записі числа кожну з них не більше одного разу?

IIМетод.

0 не може стояти першим, значить першу цифру потрібно вибрати з 2, 4, 6, 8 - 4 способи;

другою цифрою може бути будь-яка з чотирьох, що залишилися - 4 способи;

третю цифру можна вибрати серед трьох решти - 3 способи.

Отже, кількість тризначних чисел, що шукається:

4 · 4 · 3 = 48.

Відповідь: 48. ◄

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

Безліч із n елементів називається упорядкованим якщо кожному його елементу поставлено у відповідність натуральне число від 1 до n .

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

Наприклад, із 4 елементів ♦ ♣ ♠ можна скласти наступні 24 перестановки:

♦ ♣ ♠	♦ ♣ ♠	♣ ♦ ♠	♠ ♦ ♣
♦ ♠ ♣	♦ ♠ ♣	♣ ♦ ♠	♠ ♦ ♣
♦ ♣ ♠	♣ ♦ ♠	♣ ♦ ♠	♠ ♦ ♣
♦ ♣ ♠	♣ ♠ ♦	♣ ♠ ♦	♠ ♣ ♦
♦ ♠ ♣	♠ ♦ ♣	♣ ♠ ♦	♠ ♣ ♦
♦ ♠ ♣	♠ ♣ ♦	♣ ♠ ♦	♠ ♣ ♦

◄

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

P 1 = 1; P 2 = 2; P 3 = 6; P 4 = 24.

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

P n= 1 · 2 · 3 · ... · ( n - 1 ) · n = n!.

Для P nсправедлива рекурентна формула:

P n = n· P n - 1 .

Значення факторіалу визначено не тільки для натуральних чисел, а й для 0:

0! = 1 .

Таблиця факторіалів цілих чисел від 0 до 10
n		1	2	3	4	5	6	7	8	9	10
n!	1	1	2	6	24	120	720	5 040	40 320	362 880	3 628 800

Наприклад, скільки способів 5 хлопчиків і 5 дівчаток можуть зайняти в театрі місця в одному ряду з 1-го по 10-е місце, якщо жодні два хлопчики і жодні дві дівчинки не сидять поруч?

Можливі два випадки з однаковою кількістю способів: 1) хлопчики – на непарних місцях, дівчатка на парних та 2) навпаки.

Розглянемо перший випадок. Хлопчики по непарних місцях можуть сісти

P 5 = 120

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

120 · 120 = 14400

методами. Значить, всього способів

14 400 + 14 400 = 28 800.

Відповідь: 28 800. ◄

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

Перестановкою із повтореннями з n елементів, серед яких k різних, при цьому налічується n 1 невиразних елементів першого типу, n 2 невиразних елементів другого типу і так далі, n k невиразних елементів k -го типу (де n 1 + n 2 + … + n k = n ), називається будь-яке розташування цих елементів по n різних місць.

Число перестановок із повтореннями довжини n з k різних елементів, взятих відповідно до n 1 , n 2 , …, n k раз кожен позначається і обчислюється так: $$ P_(n_1,n_2, ... , n_k)=\frac(n{n_1!n_2! ... n_k!}~.$$!}

Наприклад, скільки різних десятизначних чисел можна становити з цифр: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4?

В даному випадку: n = 10, n 1 = 1, n 2 = 2, n 3 = 3, n 4 = 4,$$P_(1, 2, 3, 4)=\frac(10{1!2! 3! 4!}=\frac{10!}{1!2! 3! 4!}=12~600.$$!}

Відповідь: 12 600. ◄

Розміщення

Розміщенням з n елементів m(m ≤ n) m елементів, взятих у певному порядку з даних n елементів.

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

Наприклад, складемо всі розміщення з чотирьох елементів A, B, C, Dпо два елементи:

A B; A C; A D;

B A; B C; B D;

C A; C; C D;

D A; D; DC.

◄

Число всіх розміщень з nелементів по mпозначають \(A_n^m\) (читається: " Аз nпо m") і обчислюється за будь-якою з формул:$$A_n^m=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot (n-m+1)\\A_n^m= \frac(n{(n-m)!}$$!}

Приклади завдань.

1) Скористаємося поняттям розміщень з n елементів по m для вирішення задачі, вже двічі розглянутої раніше: Скільки трицифрових чисел можна становити з цифр 0, 2, 4, 6, 8, використовуючи в записі числа кожну з них не більше одного разу?

I IIМетод.

Першу цифру можна вибрати чотирма способами з набору 2, 4, 6, 8. У кожному з цих випадків кількість пар другої та третьої цифри дорівнює кількості розміщень з 4 цифр, що залишилися по 2. Значить кількість тризначних чисел, що шукається, дорівнює: 2=4\cdot \frac(4{(4-2)!}=4\cdot \frac{4!}{2!}=4\cdot (3\cdot 4)=48.$$Ответ: 48.!}

2) Для польоту в космос необхідно укомплектувати екіпаж із шести осіб. До нього повинні входити: командир корабля, перший і другий його помічники, два бортінженери, один з яких старший, і один лікар. Командний склад вибирається з 20 льотчиків, бортінженери — із 15 фахівців, а лікар — із 5 медиків. Скільки способами можна укомплектувати екіпаж?

Оскільки у виборі командного складуважливий порядок, то командира і його помічників можна вибрати \(A_(20)^3\) способами. Порядок бортінженерів теж важливий, отже, їх вибору існує \(A_(15)^2\) способів. Лікар лише один, для його вибору існує 5 методів. Скористаємося комбінаторним правилом множення і знайдемо кількість можливих екіпажів корабля:$$A_(20)^3\cdot A_(15)^2\cdot 5=\frac(20{17!}\cdot \frac{15!}{13!}\cdot 5=(18\cdot 19\cdot 20)\cdot (14\cdot 15)\cdot 5=7~182~000.$$Ответ: 7 182 000. !} ◄

Зрозуміло, що якщо m = n , то$$A_n^m=A_n^n=P_n=n!.$$

Справедливо також, що якщо m = n - 1 , то$$A_n^(n-1)=A_n^n=P_n=n!.$$

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

Крім звичайних розміщень бувають і розміщення з повтореннями або вибірки із поверненням .

Нехай є n різних об'єктів. Виберемо з них m штук, діючи по наступного принципу. Візьмемо будь-який, але не будемо його встановлювати в якийсь ряд, а просто запишемо під номером 1 його назву, сам об'єкт після цього повернемо до інших. Потім знову з усіх n об'єктів оберемо один (у тому числі, можливо, і той, який був щойно взятий), запишемо його назву, позначивши номером 2, і знову повернемо об'єкт назад. І так далі, поки не отримаємо m назв.

Розміщення з повтореннями позначаються \(\overline(A)_n^m\) і, згідно з правилом множення, обчислюються за формулою $$\overline(A)_n^m=n^m.$$Зауважимо, що тут припустимо випадок, коли m > n тобто обраних об'єктів більше, ніж їх всього є. Це не дивно: кожен об'єкт після "використання" повертається і може бути використаний повторно.

Наприклад, кількість варіантів шестизначного пароля, в якому кожен знак є цифрою від 0 до 9 або літерою. латинського алфавіту(одна й та сама мала і велика буква — один символ) і може повторюватися, так само:$$\overline(A)_(10+26)^6=\overline(A)_(36)^6=36^6 =2~176~782~336.$$Якщо ж малі і прописні літеривважаються різними символами (як це зазвичай і буває), кількість можливих паролів стає ще більш колосальним:$$\overline(A)_(10+26+26)^6=\overline(A)_(62)^6= 62^6=56~800~235~584.$$

◄

Поєднання

Поєднанням з n елементів m(m ≤ n) називається будь-яка безліч, що складається з m елементів, вибраних із даних n елементів.

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

Наприклад, складемо всі поєднання із чотирьох елементів A, B, C, Dпо два елементи:

A B; A C; A D;

B C; B D;

C D.

◄

Число всіх поєднань з nелементів по mпозначають \(C_n^m\) (читається: " Cз nпо m") і обчислюється за будь-якою з формул: )~\cdot~ ...~\cdot~ (n-m+1))(1\cdot2\cdot3~\cdot~...~\cdot ~m)$$$$C_n^m=\frac( n{m!\cdot (n-m)!}.$$!}

Приклади завдань.

1) Бригада, що займається ремонтом школи, складається з 12 малярів та 5 теслярів. З них для ремонту фізкультурного залу треба виділити 4 малярів та 2 теслярів. Скільки можна це зробити?

Так як порядок малярів у кожній обраній четвірці і порядок теслярів у кожній обраній парі не має значення, то, згідно з комбінаторним правилом множення, кількість способів, що шукається, дорівнює:$$C_(12)^4 \cdot C_5^2 =\frac(12{4!\cdot 8!}\cdot \frac{5!}{2!\cdot 3!}=\frac{9\cdot10\cdot11\cdot12}{1\cdot2\cdot3\cdot4}\cdot \frac{4\cdot5}{1\cdot 2}=4~950.$$Ответ: 4 950. !} ◄

2) У класі навчаються 30 учнів, серед яких 13 хлопчиків та 17 дівчаток. Скільки способами можна сформувати команду з 7 учнів цього класу, якщо до неї повинна входити хоча б одна дівчинка?

Кількість всіх можливих команд по 7 осіб із класу дорівнює \(C_(30)^7\). Кількість команд у яких лише хлопчики - \ (C_ (13) ^ 7 \). Отже, кількість команд, у яких є хоча б одна дівчинка, дорівнює $$C_(30)^7 - C_(13)^7 =\frac(30{7!\cdot 23!} - \frac{13!}{7!\cdot 6!}=2~035~800-1~716=2~034~084.$$Ответ: 2 034 084. !} ◄

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

Окрім звичайних поєднань розглядають поєднання з повтореннями .

Нехай у безлічі є n об'єктів. Виберемо з них m штук, діючи за таким принципом. Візьмемо будь-який, але не будемо його встановлювати в якийсь ряд, а просто запишемо, сам об'єкт після цього повернемо до інших. Потім знову з усіх n об'єктів виберемо один (у тому числі, можливо, і той, який було взято та записано раніше), запишемо його назву і знову повернемо об'єкт назад. І так далі, поки не отримаємо m назв.

Принципова відмінність від розміщень із повтореннями у тому, що у разі елементи списку не нумеруються. Наприклад, список "A, С, A, В"та список "А, А, В, С"вважаються однаковими.

Поєднання з повтореннями позначаються \(\overline(C)_n^m\) і обчислюються за формулою $$\overline(C)_n^m=P_(m,~n-1)=\frac((m+n-1 ){m!\cdot (n-1)!}.$$И ещё один способ записи той же формулы:$$\overline{C}_n^m=C_{m+n-1}^m=\frac{(m+n-1)!}{m!\cdot (n-1)!}.$$Заметим, что подобно размещениям с повторениями, допустим случай, когда !} m > n тобто обраних об'єктів більше, ніж їх всього є. Дійсно, кожен об'єкт після "використання" повертається назад і може бути використаний знову і знову.

Наприклад, з'ясуємо скільки можна купити 7 тістечок у кондитерському відділі, якщо у продажу 4 їх сорти?

Природно вважати, що кількість тістечок кожного виду не менше 7, і за бажання можна купити тільки тістечка одного з них. Так як порядок в якому кладуть куплені тістечка в коробку не важливий, маємо справу з поєднаннями з повтореннями. Так як потрібно вибрати 7 тістечок з 4 його видів, то кількість способів, що шукається, дорівнює:$$\overline(C)_4^7=\frac((7+4-1){7!\cdot (4-1)!}=\frac{10!}{7!\cdot 3!}=\frac{8\cdot 9\cdot 10}{1\cdot 2\cdot 3}=120.$$!}

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

Біном Ньютона та біноміальні коефіцієнти

Рівність$$(x+a)^n=C_n^0x^na^0+C_n^1x^(n-1)a^1+...+C_n^mx^(n-m)a^m+...+ C_n^nx^0a^n$$називають біномом Ньютона або формулою Ньютона . Права частинарівності називається біноміальним розкладанням у суму а коефіцієнти \(C_n^0,~C_n^1,~...~,~C_n^n\) — біноміальними коефіцієнтами .

Властивості біномних коефіцієнтів:

\(~~~~~~~~1.~~C_n^0=C_n^n=1\\ ~~~~~~~~2.~~C_n^m=C_n^(n-m)\\ ~~ ~~~~~~3.~~C_n^m=C_(n-1)^(m-1)+C_(n-1)^(m)\\ ~~~~~~~~4.~ ~C_n^0+C_n^1+C_n^2+~...~+C_n^n=2^n\\ ~~~~~~~~5.~~C_n^0+C_n^2+C_n^ 4+~... =C_n^1+C_n^3+C_n^5+~...=2^(n-1)\\ ~~~~~~~~6.~~C_n^n+C_ (n+1)^n+C_(n+2)^n+~...~+C_(n+m-1)^n=C_(n+m)^(n+1)\\ \)

Властивості біномного розкладання:

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

тобто одно n+ 1 .

2. Сума показників ступенів x і a кожного члена розкладання дорівнює показнику ступеня бінома,

тобто (n - m) + m = n .

3. Загальний член розкладання (позначається T n+1 ) має вигляд$$T_(n+1)=C_n^m x^(n-m)a^m,~~~~m=0,~1,~2,~...~,~n.$$

Трикутник Паскаля

Усі можливі значення біномних коефіцієнтів (числа поєднань) для кожного показника ступеня бінома n можна записати у вигляді нескінченної трикутної таблиці. Така таблиця називається трикутником Паскаля:

					\(C_0^0\)
				\(C_1^0\)		\(C_1^1\)
			\(C_2^0\)		\(C_2^1\)		\(C_2^2\)
		\(C_3^0\)		\(C_3^1\)		\(C_3^2\)		\(C_3^3\)
	\(C_4^0\)		\(C_4^1\)		\(C_4^2\)		\(C_4^3\)		\(C_4^4\)
\(C_5^0\)		\(C_5^1\)		\(C_5^2\)		\(C_5^3\)		\(C_5^4\)		\(C_5^5\)
	. . .				. . .				. . .

У цьому трикутнику крайні числа у кожному рядку дорівнюють 1. Дійсно, \(C_n^0=C_n^n=1\). А кожне не крайнє число дорівнює сумі двох чисел попереднього рядка, що стоять над ним: \(C_n^m=C_(n-1)^(m-1)+C_(n-1)^(m)\).

Таким чином, цей трикутник пропонує ще один (рекурентний) спосіб обчислення чисел \(C_n^m\):

n = 0									1
n = 1								1		1
n = 2							1		2		1
n = 3						1		3		3		1
n = 4					1		4		6		4		1
n = 5				1		5		10		10		5		1
n = 6			1		6		15		20		15		6		1
n = 7		1		7		21		35		35		21		7		1
n = 8	1		8		28		56		70		56		28		8		1
...				...				...		...				...