алуйста показує, что число n-підмножін у k-множінi збігається з числом (k - n) -множін тієї ж множини.
Доведення. Если з k-множини ВИДАЛИТИ n-підмножінy Y, то залиша (k - n) -підмножіна або ДОПОВНЕННЯ до Y в X. Тому з n-підмножін и їхніх ДОПОВНЕННЯ можна утворіті парі Такі, что Кожна n-підмножіна и Кожна (k -n) -підмножіна потраплять лишь в одну пару. А це й означає, что таких підмножін однакова Кількість, тобто =.
Властівість 2. Зафіксуємо тепер Який-небудь Із k елементів, например а, и розіб'ємо всі сполучення з k елементів no n на два класи -, що містять елемент а и не містять цього елемента. Число зотриманням першого класу дорівнює, тому что в цьом класі з тихий, что залиша k - 1 елементів треба вібрато ще n - 1 елемент. Число зотриманням іншого класу дорівнює. Треба вібрато n Із всех елементів, крім а. Альо будь-яке сполучення відносіться чі то до дере, чі то до іншого класу. Тому
(4.10)
. 6 Формула включень и вилучений
До тепер мова Йшла про підрахунок числа підмножін, что утворяться путем Вибірки про єктів Із деякої множини відповідно до умів, что визначаються їхню Кількість, упорядкованість и повторюваність. Чи не менше значення мают задачі перерахування, зв язані з властівостямі об'єктів.
Нехай наявні N про єктів и Деяка сукупність властівостей. Позначімо ТОЩО Кількість про єктів, что мают Властивості відповідно ТОЩО. Очевидно, таких чисел буде Стільки, скільки підмножін можна утворіті з елементів множини Н, тобто 2n (деякі числа могут дорівнюваті нулю). Для об'єктів, что НЕ володіють властівістю, уводиться Позначення.
Звідсі число об'єктів, что НЕ володіють жодною Із властівостей множини Н, візначається формулою Включення и вилучення:
(4.11)
Основна формула віпліває безпосередно з визначення операции про єднання множини
Дійсно, при відніманні від N про єктів Із властівостямі про єкти, что володіють двома властівостямі та віднімаються двічі, и того нужно Додати, де - попарні сполучення елементів з Н. Альо при цьом двічі враховуються про laquo ; єкти, что володіють трьома властівостямі І, отже, їх необходимо віключіті, тобто відняті торбу всех, де - сполучення з властівостей по три. Цей процес Включення и вилучення продовжується до последнего члена, что візначає число об єктів Із усіма n властівостямі, знак которого покладів від парності n. Наведена формула відома під Назв сімволічній метод, принцип перехресної класіфікації, метод решета та формула Обертаном.
Таким чином, у цьом розділі наведені основні Відомості з комбінаторікі, Які Згідно ми будемо Неодноразово згадувати и ікорістовуваті при вікладі методів синтезу автоматів та структур та других розділів дискретного АНАЛІЗУ.
5. Основи Теорії графів
Графічне Подання решение різніх прикладних завдань нам добро известно. До графічних Поданєв у широкому змісті могут буті віднесені малюнки, креслення, графіки, діаграмі, блок-схеми и т.п. З їхньою помощью наочно ілюструються залежності процесів и явіщ, логічні, структурні, причинно-наслідкові и Інші взаємозв'язкі. Однако теорія графів має свою ВЛАСНА проблематику.
У діскретній математиці граф є найважлівішім математичность ПОНЯТТЯ. На Основі Теорії графів будують моделі різноманітніх завдань, таких як маршрутізації, розподілу ресурсов, діскретної оптімізації, сіткового планування и керування, АНАЛІЗУ І проектування організаційніх структур, АНАЛІЗУ процесса їх Функціонування и много Іншого.
5.1 Основні визначення
Визначення. Графом назівається сукупність двох множини точок и ліній, между Якими визначене відношення інцідентності, причому, КОЖЕН елемент інцідентній Рівно двом елементи.
Елементи множини назіваються вершинами, а елементи множини - ребрами графа.
Вершини и ребра графа назіваються его елементами, тому найчастіше пишуть і.
Визначення. Если ребро з'єднує вершини, тоді смороду є для него кінцевімі точками и назіваються суміжнімі вершинами. Два ребра назіваються суміжнімі, если смороду інцідентні до Загальної вершини.
необходимо відзначіті, что при зображенні графа НЕ всі деталі малюнка мают значення. Так, например, несуттєвою є довжина и кривизна ребер, взаємне Розташування вершин на площіні. Принципова є только відношення інцідентності.
У Деяк завданнях інцідентні ребру вершини нерівноправні, а розглядаються в Певнев порядку. Тоді шкірному ребру можна пріпісаті напрямок Від першої інцідентної вершини до Другої.
Приклад. Мод...
