Метод включений и исключений

↑

▷ Содержание

Стр 1 из 2Следующая ⇒

Пусть множество А имеет N элементов и n одноместных отношений (свойств) Р₁,Р₂,…,Р_n. Каждый из N элементов может обладать или не обладать любым из этих свойств. Обозначим через N_{i1...i k} число элементов, обладающих свойствами Р_i1,...,P_{i k} и, может быть, некоторыми другими. Тогда число N(0) элементов, не обладающих ни одним из свойств Р₁,Р₂,…,Р_n, определяется по следующей формуле, называемой формулой включений и исключений:

N(0) = S₀ – S₁ + S₂ -... + (-1)ⁿ S_n ,

П р и м е р 1. Пусть колода состоит из n карт, пронумерованных числами 1,2,…,n. Сколькими способами можно расположить карты в колоде так, чтобы ни для одного i (1 ≤ i ≤ n) карта с номером i не занимала i-e место?

Имеется n свойств Р_i в виде «i-я карта занимает в колоде i-е место». Число всевозможных расположений карт в колоде равно n!. Число N_{i1...i k} расположений, при которых карта с номером i_j занимает место i_j (j=1,...,k), равно (n-k)!. Тогда S₀ = n!,

Используя формулу, получаем, что число N(0) расположений, при которых ни одно из свойств Р_i не выполнено, равно

Обобщая формулу (5.2), получаем формулу, позволяющую вычислить число N(r) элементов, обладающих ровно r свойствами (1 ≤ r ≤ n):

Для положительных целых чисел a и b значение функции равно количеству чисел из множества {1,2,…,b}, которые делятся на а, т.е. кратных а.

П р и м е р 2. сколько положительных чисел от 1 до 500 делятся ровно на одно из чисел 3,5 или 7?

Обозначим свойства делимости на 3,5 и 7 соответственно через Р₁, Р₂ и Р₃. Тогда для N = 500 имеем , , . Так как N₁₂ – число общих кратных для чисел 3 и 5, наименьшее общее кратное которых равно 15, то N₁₂ совпадает с количеством чисел, которые делятся на 15, т.е. . Аналогично , , . По формуле (5.3) находим искомое число чисел

-2(N₁₂ + N₁₃ + N₂₃) + 3N₁₂₃ = 166 +100 +71 -2(33+23+14) +3 4 =209.

Лабораторная работа №2

Комбинаторный анализ

Цель работы: ознакомиться с элементами комбинаторного анализа, изучить комбинаторные схемы.

Таблица 3.1 – Варианты заданий

Продолжение таблицы 3.1

Запрограммировать решение

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии