Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Топ:
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Интересное:
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2024-02-15 | 26 |
5.00
из
|
Заказать работу |
|
|
З’єднання | Без повторен ь елемент ів | З повторен нями елемент ів |
Перестановки | ||
Розміщення | ||
Сполучення |
Тема№3
Принцип включення-виключення
Нехай є деяка скінченна множина , що має потужність у об'єктів та множина властивостей Кожний об'єкт множини може володіти або не володіти однією або одночасно декількома (всіма) властивостями із множини .
Введемо ряд позначень.
– кількість об'єктів множини , які володіють властивістю ;
– кількість об'єктів, що не володіють властивістю ;
– кількість об'єктів, що володіють двома властивостями одночасно;
– кількість об'єктів, що володіють трьома властивостями одночасно;
– кількість об'єктів, що володіють усіма властивостями множини одночасно;
– кількість об'єктів, що не володіють ні одним з властивостей множини .
Теорема 4
Доведення.
Формула включень та виключень визначає кількість об'єктів, що не володіють ні однією з властивостей, заданих множиною .
Наприклад:
На фірмі працює 67 співробітників. З них 47 володіють англійською мовою, 35 – німецькою, 20 – французькою; одночасно англійською та німецькою володіють – 23 співробітника, англійською та французькою – 12, німецькою та французькою – 11, трьома мовами володіють 5 співробітників. Скільки співробітників не володіють ні однією із перерахованих мов?
Розв’язання.
Визначимо наступні властивості:
– "володіти англійською мовою”;
– "володіти німецькою мовою;
– "володіти французькою мовою".
За формулою включень і виключень маємо:
Окремі випадки формули включень і виключень
1. Якщо всі властивості попарно несумісні, тобто
|
то формула включень і виключень має вигляд:
2. Якщо кожне число залежить не від характеру властивостей, а лише від їх кількості, то формула має вигляд:
де – кількість об’єктів, що володіють рівно властивостями.
Зада ча про безлад
Нехай є множина
Розглянемо перестановки елементів множини .
Елемент перестановки називається нерухомим, якщо , тобто елемент стоїть на своєму місці.
Наприклад.
При у перестановці – елемент – нерухомий, а у перестановці – усі елементи нерухомі.
Безладом називається перестановка, яка не має нерухомих елементів, тобто
Постановка за дачі
Визначити – кількість безладів у -елементній множині, або кількість перестановок чисел таких, що .
Розв’язання.
Загальне число перестановок у -елементній множині дорівнює . Позначимо через таку властивість перестановки, що -й елемент стоїть на своєму місці, тобто . Тоді ліва частина формули включень та виключень і є розв’язком задачі про безлад. За позначенням є кількість перестановок в -елементній множині, у яких один -тий елемент стоїть на своєму місці і дорівнює , бо один елемент не можна переставляти, а останні елементи можуть бути переставлені способами. Так як число перестановок не залежить від того, який саме елемент знаходиться на своєму місці, то:
:
Аналогічно, визначимо – кількість перестановок, у яких рівно два елементи знаходяться на своїх місцях: та, відповідно, – кількість перестановок, у яких тільки елементів знаходяться на своїх місцях: .
За формулою включень-виключень маємо:
Розпишемо формулу
– ще називають субфакторіалом.
Зада ча про зустріч
Визначити кількість таких перестановок чисел , що точно елементів із знаходяться на своїх місцях (тобто ), а інші , перебувають у безладі.
Інакше: нас цікавлять перестановки, в яких рівно елементів нерухомі.
Розв’язання.
Із загального числа елементів вибирається , які залишаються на своїх місцях. Оскільки вибір елементу визначає й його місце розташування, то кількість варіантів дорівнює: . Для інших елементів розв’язується задача про безлад: . Тоді,за правилом добутку кількість способів, якими можна переставити елементів при таких умовах, дорівнює:
|
|
|
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!