Реферат: Початки комбінаторики
(1, …, 1, 2, …, 2, …, n , …, n ).
123123123
k 1 k 2 … kn
Як бачимо, множиною елементів, якими утворюється комбінація з повтореннями, тут є {1, 2, …, n }.
Комбінації по m елементів множини {a 1 , a 2 , …, an } з повтореннями складу (k 1 , k 2 , …, kn ) можна взаємно однозначно поставити у відповідність послідовність довжини m +n -1 із m "1" і n -1 "0":
(1, …, 1, 0, 1, …, 1, 0, …, 1, …, 1).
123123123
k 1 k 2 … kn
Такій послідовності, у свою чергу, взаємно однозначно відповідає комбінація номерів місць у цій послідовності, на яких розташовані 1 (або 0). Кількість таких комбінацій є , що й є кількістю всіх можливих комбінацій по m елементів n -елементної множини з повтореннями.
6. Формули включень і виключень
Кількість елементів об'єднання двох множин, що не перетинаються, є сумою їх кількостей. Але якщо множини перетинаються, то елементи перетину при цьому додаванні кількостей враховуються двічі. Тому їх кількість треба один раз відняти:
|A ÈB |=|A |+|B |-|A ÇB |. (*)
При обчисленні |A ÈB ÈC | додавання |A |+|B |+|C | веде до того, що елементи кожного з перетинів |A ÇB |+|B ÇC |+|A ÇC | враховуються двічі, тому їх треба по одному разу відняти. Якщо перетин A ÇB ÇC порожній, то в результаті кожний елемент об'єднання враховано по одному разу, і все гаразд. Якщо ні, то в результаті елементи цього перетину тричі додаються і тричі віднімаються, тобто у виразі
|A |+|B |+|C |–|A ÇB |–|B ÇC |–|A ÇC |
не враховані. Отже, їх треба додати:
|A ÈB |=|A |+|B |+|C |–|A ÇB |–|B ÇC |–|A ÇC |+|A ÇB ÇC |. (**)
Вирази (*), (**) наводять на припущення, що в загальному випадку об'єднання n множин A 1 , A 2 , …, An
|A 1 ÈA 2 È…ÈAn |=|A 1 |+|A 2 |+…+|An |–|A 1 ÇA 2 |–|A 1 ÇA 3 |–…–|An -1 ÇAn |+
+|A 1 ÇA 2 ÇA 3 |+…+|An -2 ÇAn -1 ÈAn |–…+(-1)n +1 |A 1 ÇA 2 Ç…ÇAn |. (1)
Як бачимо, кількості елементів усіх можливих перетинів непарної кількості множин додаються, а парної – віднімаються. Формула (1) називається формулою включень і виключень .
Доведення формули (1) можна провести з використанням індукції за n , але тут ми його не наводимо.
Ця формула дає змогу за кількостями елементів у кожній з множин, в усіх можливих їх перетинах по дві, по три і т.д. множини обчислити кількість елементів об'єднання.
Приклад. Є група студентів, серед яких каву п'ють 12 (це множина A ), чай – 10 (множина B ), йогурт – 8 (C ), каву і чай – 5 (A ÇB ), каву і йогурт – 4 (A ÇC ), чай і йогурт – 3 (B ÇC ), усі три напої – 1 (A ÇB ÇC ). Тоді всього студентів у групі 12+10+8-5-4-3+1=19.
За допомогою формули (1) можна обчислити кількість елементів деякої множини U , що не належать жодній з її підмножин A 1 , A 2 , …, An :
|U \(A 1 ÈA 2 È…ÈAn )|=|U |–|A 1 |–|A 2 |–…–|An |+|A 1 ÇA 2 |+|A 1 ÇA 3 |+…+
+|An -1 ÇAn |–|A 1 ÇA 2 ÇA 3 |–…–|An -2 ÇAn -1 ÈAn |+…+(-1)n |A 1 ÇA 2 Ç…ÇAn |. (2)
Формулу (2) також називають формулою включень і виключень.
7. Біноміальні коефіцієнти
Означення . Біном Ньютона – це вираз вигляду (a+b)n .
Біном розкладається в суму одночленів, які є добутками деяких степенів його доданків a і b.Школярі-восьмикласники знають формули розкладу бінома Ньютона в многочлен із степенями a і bпри n=2 та 3:
(a+b)2 =a2 +2ab+b2 ,
(a+b)3 =a3 +3a2 b+3ab2 +b3 .
Спробуємо розкласти (a+b)n в многочлен у загальному випадку n. Запишемо його у вигляді, пронумерувавши дужки: