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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Правило суми. Якщо дві дії А і В взаємно виключають один одного, причому дію А можна виконати 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 однакових предметів кожного з різних типів; скільки способами можна, можливо вибрати 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 букв. Отже, кількість перестановок з повтореннями дорівнює

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

Число розміщень без повторень з 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….

План:

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

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

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

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

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

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

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

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

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

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

Приклади:

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

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

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

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

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

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

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

Приклади:

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

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

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

Генеральна сукупність без повторень- це набір деякого кінцевого числа різних елементів 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 за умови, що вони повинні складатися з різних цифр?

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

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

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

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

Рішення:У разі порядок, у якому розташовується ця трійка, не суттєвий. Тому трійки делегатів є поєднаннями із 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 комбінацій.

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