- •7.091501: "Комп'ютерні системи та мережі"
- •7.091502: ”Системне програмування”
- •Лабораторна робота №1
- •Теоретичні відомості
- •Задачі на теорію множин
- •Задачі для самостійної роботи студентів
- •Завдання
- •Зобразити множину ab-c
- •Приклад відношень g
- •Контрольні питання
- •Лабораторна робота №2
- •Теоретичні відомості
- •Задачі на теорію множин
- •Задачі для самостійної роботи студентів
- •Контрольні питання
- •Лабораторна робота №3
- •Теоретичні відомості
- •Формули з’єднань
- •Біном Ньютона
- •2) Основна властивість біноміальних коефіцієнтів
- •Правило суми
- •Перестановки
- •Перестановки з повторенням
- •Розміщення
- •Розміщення з повтореннями
- •Сполучення
- •Сполучення з повтореннями
- •Біном Ньютона
- •Поліноміальна формула
- •Задачі для самостійної роботи студента
- •Контрольні питання
- •Лабораторна робота №4
- •Теоретичні відомості.
- •Лінійні рекурентні співвідношення з постійними коефіцієнтами
- •Твірна функція
- •Розбиття множини на підмножини
- •Задачі по темі Твірні функції:
- •Задачі для самостійної роботи студентів
- •Контрольні питання
- •Лабораторна робота №5.
- •Теоретичні відомості
- •Способи збереження інформації о графах
- •Задачі на теорію графів
- •Задачі для самостійної роботи студентів
- •Ізоморфізм графів
- •Досяжність і зв’язність.
- •Орієнтовані графи
- •Процедура пошуку в глибину у графі
- •Пошук у ширину
- •Ейлерові цикли
- •Гамільтонові цикли
- •Алгоритми пошуку мінімальних шляхів у графі
- •Задачі на теорію графів
- •Задачі для самостійної роботи студентів
- •Плоскі графи. Розфарбування графа
- •Контрольні питання
- •Пошук максимального потоку у мережі
- •Задачі з теорії графів
- •Задачі для самостійної роботи студентів
- •Лабораторна робота №8.
- •Теоретичні відомості
- •Задачі з теорії кодування
- •Задачі для самостійної роботи студентів
- •Контрольні питання
- •Список рекомендованої літератури
Формули з’єднань
З’єднання
|
Без повторення
|
З повторенням |
Перестановки | ||
Разміщення | ||
Сполучення |
Біном Ньютона
Біномом Ньютона називають формулу для обчислення вираження (а+b)n для натуральних n.
Дану формулу можна довести методом математичної індукції. Нижче представлений комбінаторний доказ.
Запишемо (a+b)n у вигляді добутку (a+b)n=(a+b) (a+b) … (a+b)...
Розкриємо дужки в правій частині цієї рівності й запишемо всі добутки у виді n співмножників а й b у тім порядку, у якому вони з'являються.
Наприклад, (a+b)2 запишеться у вигляді (a+b)2=(a+b) (a+b)=aa+ab+ba+bb, а (a+b)3– у вигляді (a+b)3=(a+b)(a+b)(a+b) =aaa+aab+aba+abb+baa+bab+bba+bbb.
Видно, що в обидві формули входять всі розміщення з повтореннями, складені з букв а й b по дві (три) букви в кожному.
У загальному випадку – після розкриття дужок одержимо всілякі розміщення з повтореннями букв а й b, що складаються з n елементів. Приведемо подібні члени, що містять однакову кількість букв а й букв b. Членів, у які входить k букв a й, отже, (n–k) букв b рівно Р(k, n–k)=. Звідси випливає, що після приведення подібних членів вираз akbn-k увійде з коефіцієнтом , тому формула прийме вид:.
Таким чином, х2 у розкладанні (2х+3)6 буде мати коефіцієнт 4 860.
Числа називають біноміальними коефіцієнтами. За допомогою бінома Ньютона легко довести властивості біноміальних коефіцієнтів (чисел ):
1) Симетричність біноміальних коефіцієнтів =
Цю властивість можна довести з (a+b)n=(b+a)n. Розкладемо обидві частини рівності по біному Ньютона й розглянемо коефіцієнти при akbn-k. Праворуч коефіцієнт дорівнює,а ліворуч .
2) Основна властивість біноміальних коефіцієнтів
Якщо у формулі бінома Ньютона покласти а=1, b=х то одержимо,
(1+x)n=.
3) Сума біноміальних коефіцієнтів
Скористаємося формулою бінома Ньютона, у якій покладемо а=1 й b=1. Тоді .
Поліноміальна формула
Поліномом називають вираження виду (x1+x2+…xk)n...
Поліноміальною формулою називають формулу для обчислення значення виражень (x1+x2+…xk)nдля різного числа, що складають і різних натуральних ступенів n.
Теорема
Формула доводиться аналогічно формулі бінома Ньютона.
Властивості чисел Р(k1k2...k3)
.
Якщо в поліноміальній формулі покласти х1=х2=…=хm=1, то одержимо необхідну рівність.
2. .
Задачі на тему Комбінаторика
Правило добутку
Задача. У магазині «Усе для чаю» є 5 різних чашок й 3 різні блюдця. Скількома способами можна купити чашку із блюдцем?
Рішення.Чашку можна вибрати 5 способами. Для кожного способу вибору чашки існує 3 способи вибору блюдця. Таким чином, маємо 5 3=15 способів вибору пари предметів.
Може виникнути ситуація, коли необхідно скласти комбінацію з більшого числа елементів.
Задача. У магазині «Усе для чаю» є ще 4 чайні ложки. Скількома способами можна купити комплект із чашки, блюдця й ложки?
Рішення. З рішення попередньої задачі відомо, що існує 5 3=15 способів вибору пари предметів чашка - блюдце. Для кожного способу вибору цієї пари існує 4 способи вибору ложки. Таким чином, за правилом добутку маємо 5 3 4=60 способів вибору комплекту із чашки, блюдця й ложки.
Задача.Визначити число способів , якими можна вибрати 6 карт із 36 так, щоб серед них були 3 карти однієї масті?
Рішення: Число способів вибрати карти однієї масті дорівнює ,число способів вибрати одну карту однієї масті дорівнює, остатні 3 карти можуть бути будь-якими з 33 карт, тобто. За правилом добутку маємо:..