 |
|
Елементи комбінаторики
Задачі, в яких визначаються всі можливі різні комбінації, складені з скінченого числа елементів за деяким правилом, називаються комбінаторними. Розділ математики, в якому визначається їх розв’язання, називається комбінаторикою. Під час розв’язування комбінаторних задач доводиться розглядати скінчені множини, складені з елементів будь-якої природи, та їх підмножини. Залежно від умови задачі розглядаються скінчені множини, в яких істотним є або порядок елементів, або їх склад, або перше і друге одночасно. Такі скінчені множини (сполуки) дістали певну назву: перестановки, розміщення, комбінації.
1. Перестановки.Усякий встановлений в скінченій множині порядок називається перестановкою її елементів. Множина, в якій задано порядок розміщення її елементів, називається упорядкованою.
Характеристична ознака перестановок: 1) предмети різні; 2) всі місця зайняті; 3) порядок елементів важливий.
Число всіх перестановок у множині з 
елементів позначають 
. Воно дорівнює добутку послідовних натуральних чисел від 1 до 
включно:
.
Добуток 
прийнято позначати знаком 
(читається « 
- факторіал»); при цьому припускають, що 
, 
. Тому можна записати:
2. Розміщення.Нехай дано скінчену множину, яка складається з 
елементів. Будь-яка її упорядкована підмножина, яка містить 
елементів, де 
, називається розміщенням з 
елементів по 
.
Отже, розміщення відрізняються одне від одного або елементами, або порядком елементів.
Характеристичні ознаки розміщень: 1) предмети і місця різні; 2) 
;
3) усі 
місць необхідно зайняти ; 4) порядок елементів важливий.
Число розміщень з 
елементів по 
елементів позначають 
і знаходять за формулою:
.
Якщо 
, то дістаємо формулу: 
При розв’язуванні задач часто користуються рівністю: 
.
3. Комбінації.Нехай дано скінчену множину, яка складається з елементів. Будь-яка її підмножина, яка містить елементів, де , називається комбінацією з елементів по .
Характеристичні ознаки комбінацій: 1) предмети різні; 2) ; 3) порядок вибору елементів не має значення.
Число віх можливих комбінацій з елементів по елементів позначають 
і знаходять за формулою:
Число всіх підмножин множини А, яка складається з 
елементів, дорівнює 
.
197.Дано: А = 
, В = 
, С = 
. Знайдіть:
1) 
; 2) 
; 3) 
; 4) 
.
198.Дано: А = 
, В = 
, С = 
. Знайдіть:
1) 
; 2) 
; 3) 
; 4) 
.
199.Дано: М = 
, N = 
. Знайдіть:
1) M/N; 2) N/M; 3) (M/N) 
(N/M).
200.Дано А = , В = 
. Знайдіть: А/В і В/А.
201.Дано А = 
, В = 
. Знайдіть:
1) ; 2) ; 3) А/В; 4) В/А.
202.Дано: А = { 
: 
}, B = { 
: 
}. Знайдіть 
і 
.
203.Дано: А = { : }, В = { 
: 
}. Знайти і ;А/В; В/А.
204.Нехай А – множина цілих чисел, які діляться на 4, В – множина цілих чисел, які діляться на 3. З’ясуйте, які із чисел 9, 0, - 24, - 53, 128, 1242048 належать множинам і ?
205.Знайдіть , якщо:
1) А – множина парних чисел, В = { 
: 
, де 
};
2) А – множина простих чисел, В – множина непарних чисел.
206.Знайдіть 
, якщо М – множина простих чисел, що менші від 40, Р – множина непарних чисел, більших за 14.
207.Знайдіть К/F, якщо К = {1, 2, 3, 4, 5, 6, 7}, F = {2, 4. 6}.
208.Зі 100 студентів лише німецьку мову вивчають 18; німецьку, але не англійську – 23, німецьку і французьку – 8; німецьку – 26; французьку – 48, англійську і французьку – 8; ніякої мови не вивчають – 24. З’ясуйте, скільки студентів вивчають англійську мову? Скільки студентів вивчають англійську і німецьку мову, але не французьку? Скільки студентів вивчають французьку мову в тому і лише тому випадку, якщо вони не вивчають англійську?
209.Обчисліть:
1) 
; 2) 
; 3) 
; 4) 
;
5) 
; 6) 
; 7) 
; 8) 
;
9) 
; 10) 
; 11) 
; 12) 
;
13) 
; 14) 
; 15) 
; 16) 
;
17) 
; 18) 
210.Спростіть:
1) 
; 2) 
; 3) 
; 4) 
;
5) 
; 6) 
; 7) 
; 8) 
;
9) 
; 10) 
; 11) 
; 12) 
.
211.Розв’яжіть рівняння:
1) 
; 2) 
; 3) 
; 4) 
;
5) 
; 6) 
; 7) 
; 8) 
;
9) 
; 10) 
; 11) 
.
212.Вкажіть скількома способами можна скласти список із 9 прізвищ?
213.Вкажіть скількома способами можна розкласти вісім різних листів у вісім різних конвертів, якщо в кожний конверт вкладається лише один лист?
214.З’ясуйте, скільки п’ятицифрових чисел можна написати цифрами 5, 6, 7, 8, 9 так, щоб усі цифри кожного числа були різними?
215.Із цифр 0, 1, 2, 3, 4 складені всі можливі п’ятизначні числа так, що в кожному числі цифри не повторюються. Вкажіть скільки одержали чисел?
216.Вкажіть скільки всього шестизначних парних чисел можна скласти з цифр 1, 3, 4, 5, 7, 9, якщо в кожному із цих чисел жодна цифра не повторюється?
217.З цифр 1, 2, 3, 4, 5 складено всі можливі п’ятизначні числа без повторення цифр. Вкажіть скільки серед цих п’ятизначних чисел таких, які:
1) починаються цифрою 5;
2) не починаються з цифри 3;
3) починаються з 53;
4) не починаються з 543.
218.З’ясуйте, скількома способами можна розсадити 4 учнів на 25 місцях?
219.Студенту треба скласти 4 екзамени на потязі 8 днів. З’ясуйте, скількома способами це можна зробити?
220.Вкажіть скільки існує всього семицифрових телефонних номерів, в кожному із яких жодна цифра не повторюється?
221.Вкажіть скільки існує двоцифрових чисел, в яких цифра десятків і цифра одиниць різні і непарні?
222.З’ясуйте, із скількох різних предметів можна скласти 210 різних розміщень по два елементи в кожному?
223.Із 20 робітників треба виділити 6 для роботи на елеваторі. Вкажіть скількома способами це можна зробити?
224.На полиці є 35 книжок. Вкажіть скількома способами можна вибрати дві із них?
225.Вкажіть скількома способами можна закреслити 6 номерів із 49 в картці «Спорт лото».
226.У групі навчається 32 студента. Вкажіть скількома способами можна сформувати команду з 4 студентів для участі в математичній олімпіаді?
227.На площині розташовано 25 точок таким чином, що жодні три з них не лежать на одній прямій. Вкажіть скільки існує трикутників з вершинами в цих точках?
228.З’ясуйте, скількома способами групу із 17 студентів можна розділити на дві групи таким чином, щоб в одній було 5 студентів, а в другій – 12 студентів?
229.Студент має по одній монеті в 1 коп., 2 коп., 5 коп., 10 коп., 25 коп. З’ясуйте, скількома способами він може ці монети розкласти в дві кишені?
230.У деякому царстві немає двох людей, які б мали однаковий набір зубів. З’ясуйте, скільки людей мешкає там, якщо кількість зубів у мешканців утворює всю множину можливих варіантів?
231.А) 25 викладачів потиснули один одному руки перед педрадою. Вкажіть скільки було зроблено рукостискань?
Б) 25 студентів обмінялися фотографіями так, що кожний обмінявся з кожним. Вкажіть скільки було роздано фотографій?
232.А) В групі з 32 студентів вибирають на конференцію делегацію, яка складається з трьох осіб. Вкажіть скільки існує варіантів такого вибору?
Б) В групі з 32 студентів для проведення зборів обирають голову, заступника та секретаря. Вкажіть скількома способами це можна зробити?
233.А) Біля стола стоїть 9 стільців. Вкажіть скільки існує способів розміщення за столом 9 осіб?
Б) 9 дівчат водять хоровод. Вкажіть скільки існує різних варіантів стати дівчатам в коло?
В) З дев’яти різних намистин потрібно зробити намисто. Вкажіть скільки існує різних способів його утворення?
234.7 книг різних авторів і трьохтомник одного автора розташовані на книжковій полиці. З’ясуйте, скількома способами можна розставити ці 10 книжок на полиці так, щоб книги автора трьохтомника стояли поруч?
235.Збори з 30 осіб обирають голову, секретаря та трьох членів редакційної комісії. Вкажіть скількома способами це можна зробити?
236.У підрозділі 60 солдат і 5 офіцерів. Вкажіть скількома способами можна виділити наряд, Який складається із трьох солдат і одного офіцера?
237.У одного хлопчика є 10 марок для обміну, а у другого – 8. Вкажіть скількома способами вони можуть обміняти дві марки одного на дві марки другого?
238.На одній паралельній прямій розташовано 7 точок, а на другій – 12. Вкажіть скільки існує чотирикутників з вершинами в цих точках?
239.Вкажіть скількома способами з колоди з 36 карт можна вибрати 10 карт так, щоб серед них було рівно три тузи?
240.Вкажіть скількома способами можна розподілити пари в шести групах між трьома викладачами, якщо кожен викладач викладатиме у двох групах?
241.Для відвідування театру закуплено 20 квитків в один ряд партеру. Вкажіть скількома способами можна розподілити ці квитки між 10 чоловіками і 10 жінками так, щоб два чоловіки або дві жінки не сиділи поруч?
242.Із 10 троянд і 8 жоржин треба скласти букет з п’яти квітів так, щоб в ньому було:
1) лише п’ять троянд;
2) 2 троянди і 3 жоржини;
3) або 2 троянди і 3 жоржини, або 3 троянди і 2 жоржини;
4) п’ять квітів, серед яких була б принаймні одна троянда.
Вкажіть скількома способами можна скласти букет?
243.Із семи бігунів і трьох стрибунів треба скласти команду із 5 чоловік, в яку б входило:
1) три бігуна і два стрибуна;
2) чотири бігуна і один стрибун;
3) хоч би один стрибун.
Вкажіть скількома способами це можна зробити?
до змісту