Головна |
Правило суми. Якщо є кінцеві безлічі А і В, причому
A ? B = O, тоді | A U B | = | A | + | B | (Число елементів в об'єднанні множин є сума чисел елементів у величезних кількостях).
правило твори. Нехай A'B = {( , ) / A, B} - декартовій твір множин A і B, тоді | A'B | = | A | · | B | (Потужність безлічі АxВ є твір потужностей множин А і В).
Приклад 1. нехай A={1,2}, B = {a, b, c}. тоді
A'B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}. | A'B | = | A | · | B | = 2 · 3 = 6.
Правило можна узагальнити на n множин: Нехай А1, ..., Аn - Різні безлічі, тоді А1'...'Аn = {(?1, ?2, ..., ?n) | ?1 А1, ?2 А2, ..., ?n Аn}
і | А1'...'Аn| = | А1| - | А2| --- | Аn|.
Приклад 2. Знайти число двійкових наборів довжини n.
Рішення: Нехай А1 = {0,1}, ..., Аn = {0,1}. тоді
, Де E2 = {0,1}.
Нехай нам дано деякий кінцеве безліч X = {x1, ..., Xn}. Розглянемо деякий його підмножина { }. Надалі таке підмножина назвемо r-вибіркою.
R-вибірки бувають двох видів:
1. Якщо в r-вибірці важливий порядок елементів, тоді ми будемо називати її r-перестановкою з n елементів.
2. Якщо в r-вибірці порядок елементів не важливий, тоді будемо називати її r-поєднанням з n елементів.
У кожному з видів можливі 2 випадки:
а)Допускається повторення елементів, тоді це r-перестановки з повтореннями (або r-поєднання з повтореннями).
b)Всі елементи різні, тоді це r-перестановки без повторень (або r-поєднання без повторень).
Затвердження 1. Число r-перестановок з повтореннями з n елементів П (n, r) = nr.
Доведення: Так як ми на кожне місце можемо поставити будь-який з n елементів, а таких місць r, значить все можливостей за правилом твори nr. Дійсно, А1 = X, ..., Аr = X, тоді .
Приклад 3. X = {1,2,3}. Скільки двозначних чисел ми можемо скласти з елементів безлічі X?
Рішення: Їх всього nr, Де n = 3, r = 2. Тоді 32 = 9 чисел, а саме числа 11, 21, 31, 12, 22, 32, 13, 23, 33.
затвердження 2. Число r-перестановок без повторень з n елементів , де .
Доведення: , ; А2 = Х1, де , , ...,
, де , . Іншими словами, на перше місце можна поставити n штук елементів, на друге - елементів і так далі, на останній r-е місце можна поставити
n - r + 1 елементів. Тоді за правилом твори
r| = .
Зауваження. Дуже часто r-перестановки без повторень з n елементів в літературі називають розміщенням з n елементів по r. Прийнято наступні позначення P (n, r) = Arn = (N)r (Число розміщень з n елементів по r).
Приклад 4. Х = {1,2,3}. Скільки двозначних чисел без повторюваних цифр можна скласти з елементів безлічі Х?
Рішення: Їх всього P (n, r) = n (n - 1) (n - 2) ... (n - r + 1), де n = 3, r = 2. Тоді P (3,2) = 3 · 2 = 6 чисел (12, 21, 13, 31, 23, 32).
слідство 1. Якщо в утвердженні 2 r = n, то це перестановка з n елементів, і тоді .
Приклад 5. X = {1,2,3}. Скільки тризначних чисел без повторюваних цифр можна скласти з елементів безлічі Х?
Рішення: їх всього Pn = N !, де n = 3. Тоді P3 = 3! = 1 · 2 · 3 = 6 чисел: 123, 213, 231, 321, 312, 132.
Формула Стірлінга: (~ - Асимптотично одно).
якщо , то .
Затвердження 3. Число r-поєднань без повторень з n елементів .
Доведення: Беремо довільну неупорядковану вибірку { } - R-елементів. З цієї однієї невпорядкованою отримуємо r! упорядкованих. А так як все невпорядкованих вибірок , то - Число впорядкованих вибірок. Оскільки кожна упорядкована вибірка отримана перестановкою елементів в невпорядкованою, то
.
Приклад 6. X = {1,2,3}. знайти : 12, 13, 23 (невпорядковані двозначні числа без цифр, що повторюються).
Приклад 7. У чемпіонаті країни з футболу беруть участь 18 команд, причому кожні дві команди зустрічаються між собою 2 рази. Скільки матчів грається протягом сезону?
Рішення: В першому колі відбудеться стільки матчів, скільки існує двоелементний підмножин у безлічі, що містить 18 елементів, тобто їх число дорівнює = 153.
У другому колі грається стільки ж матчів, тому протягом сезону відбудеться 306 зустрічей.
числа , Де r = 0,1, ..., n називають біноміальними коефіцієнтами.
0! = 1 (за визначенням, для зручності).
2.3. Властивості біноміальних коефіцієнтів.
Біноміальна теорема. поліноміальна теорема
1) - ціле число.
2) : = , = > ( ).
3) : .
4) Біноміальна теорема. . (1)
Доведення: >
> елемента;
> елементів.
Треба дізнатися, який коефіцієнт при > > після перемноження виходить різних комбінацій, але деякі елементи повторюються. Тобто коефіцієнт при дорівнює числу
r-поєднань x з усіх n дужок, де , тобто . ¦
5) Слідство 2. Якщо у формулі (1) x = y = 1, то
.
6) Слідство 3. Якщо у формулі (1) x = -1, y = 1, то
.
Приклад 8. Знайти число двійкових наборів довжини n з 0 і 1, що мають r одиниць.
Рішення: Всього довічних наборів довжини n з 0 і 1 - 2n, З них, що мають r одиниць, так само
= .
Приклад 9.Для освітлення залу може бути включена кожна з 10 ламп. Скільки існує різних способів освітлення залу?
Рішення: Очевидно стільки, скільки існує підмножин у десятіелементного безлічі, тобто . При цьому враховується і той спосіб освітлення, при якому жодна лампа не горить.
Приклад 10. Записати комплексне число в алгебраїчній формі.
Рішення: За формулою (1) маємо
.
Значить, (2 + i)6 = -117 + 44i.
7) a) нехай (Парне число), тоді .
b)нехай (Непарне число), тоді
,
де [n / 2] - ціла частина числа n / 2.
Доведення:
a) Треба довести, що , якщо , Де r = 0, 1, ..., - 1.
= , = , = = <1. Так як , то ; n - r ? r + 1 + 1. Тоді (r + 1) / (n-r) ? (r + 1) / ((r + 1) +1) <1.
доказ для b) аналогічно.
затвердження 4. Число r-поєднань з повтореннями з n елементів
.
Доведення: Нехай {x1, ..., Xn} - Наші елементи, з них виберемо r елементів { } Без урахування порядку, але з повторенням.
нехай x1 зустрічається ?1 раз,
x2 зустрічається ?2 рази,
...
xn зустрічається ?n раз,
де 0? ?i? r, 1? i? n; ?1 + ?2 + ... + ?n = R.
Число наших вибірок дорівнює числу рішень нашого рівняння в цілих позитивних числах. Отже, вибірка дає рішення , і навпаки, рішення дає вибірку, тобто взаимнооднозначное відповідність між рівнянням і вибірками.
нехай ?1, ..., ?n - вирішення рівняння . Тоді виписуємо ?1 одиниць, потім 0, потім ?2 одиниць, потім 0, і так далі:
0 0 ... 0 .
У цьому наборі одиниць r штук, нулів (n - 1) штук.
По кожному рішенню рівняння отримаємо набори з 0 і 1 довжиною r + n - 1.
Отже, кожен такий набір дає рішення . Тому число рішень рівняння дорівнює числу наборів з r + n - 1 нулів і одиниць, кожен з яких має рівно r одиниць, а це число дорівнює .
Приклад 11. E = {1, 2, 3}. Скільки поєднань з повтореннями з E по 2?
Рішення: D23 = C24 = (4!) / (2! 2!) = (3-4) / 2 = 6. Усього таких поєднань 6, а саме: 11, 12, 22, 23, 13, 33.
Завдання. Якщо дано (x + y + z)4, Як знайти коефіцієнт при x2yz?
Рішення: (x + y + z) (x + y + z) (x + y + z) (x + y + z) - з кожної дужки витягуються різні змінні, таких варіантів 34.
Як виходить x2yz: x x y z
x y x z.
... ... ... ...
Як підрахувати, скільки разів зустрінеться x2yz.
Спочатку ми вибираємо x по максимальному ступені, що буде наборів. тоді варіантів буде для вибору y. За правилом твори варіантів буде для вибору x2y. аналогічно, -З12- С11 варіантів буде для вибору x2yz. Іншими словами, x2yz зустрінеться -З12-З11 = -З12 = (4!) / (2! 2!) - (2!) (1! 1!) = 3-4 = 12 разів.
Рішення подібних завдань дає наступна поліноміальна
Теорема 1. .
Доведення:(x1 + x2 + ... + Xk) ... (X1 + x2 + ... + Xk) - Всього n дужок.
Для того щоб вибрати r1 штук x1 з n дужок необхідно варіантів. Далі у нас залишилося (n - r1) Дужок, значить, число виборів r2 штук x2 з (n - r1) Дужок буде . Тоді загальне число виборів буде і т.д. Тоді число виборів rk штук xk з (n - r1 -...- rk-1) Дужок буде , Так як r1 + ... + Rk = N.
всього виборів буде
n!
=
r1!r2! ...rk!
Значить, коефіцієнт при буде .
Приклад 12. Знайти коефіцієнт при x2yz в (x + y + z)4.
Рішення: За полиномиальной теоремі коефіцієнт при x2yz буде дорівнює (4!) / (2! · 1! · 1!) = 3 · 4 = 12.
Приклад 13. Скільки різних поєднань літер можна скласти з слова макака.
Рішення: Використовуємо поліноміальних теорему. Будемо оперувати з буквами як з виразами виду (М + А + К)6 .
Так як в слові макак букв >
то число шуканих слів (різних поєднань літер з слова макака) дорівнюватиме коефіцієнту при члені
МА3К2 = 60.
ЕДЕРАЛЬНОЕ ОСВІТИ | ББК 22.174 я73 | ВСТУП | Безлічі і операції над ними | алгебра множин | Розбиття множини на підмножини | Кортежі і декартовій твір множин | відносини | Властивості бінарних відносин | алгебра підмножин |