Метод включения и исключения. Функция Эйлера. Число беспорядков

Пусть дано n -множество элементов S и N- множество свойств p ₁,…, p_N. Элементы множества S могут как обладать, так и не обладать любым из свойств p_i. Количество элементов, обладающих теми или иными свойствами и их комбинациями, известно.
Требуется найти число элементов, не обладающих ни одним из свойств.
Обозначим:

1.
через некоторую i -ю выборку свойств, а через – число элементов, каждый из которых обладает всеми этими r выбранными свойствами.

2.
через – отсутствие у элемента свойства p_i. Тогда, например, – число элементов, обладающих свойствами p ₁ и p₃ и не обладающих свойствами p₂ и p₄.
Рассмотрим два частных случая.

1.
Имеется лишь одно свойство p. Тогда очевидно, что число элементов, не обладающих свойством p, равно общему числу элементов минус число элементов, обладающих свойством p. .

2.
Имеется конечное множество свойств p ₁,…, p_N, но они не совместимы (т.е. ни один из элементов не может обладать более чем одним свойством). Тогда число элементов, не обладающих ни одним из свойств, равно общему числу элементов минус число элементов, обладающих свойством p ₁, минус число элементов, обладающих свойством p ₂ и т.д.

^ Общий случай – элементы могут обладать комбинацией совместимых свойств.
Теорема. Если даны n -множество элементов S и N свойств p_i , то число элементов, не обладающих ни одним из свойств, равно (формула решета):

.

Примечание 1. Символическая запись метода:
, (*)
где буквой n обозначен функциональный знак. Смысл такой записи – сначала раскрываем круглые скобки внутри квадратных, а затем знак функции n приписываем к каждому из слагаемых. Например,
,
считая, что .

Пример применения формулы включений-исключений — нахождение явного выражения для функции Эйлера , выражающей количество чисел из , взаимно простых с .

Пусть каноническое разложение числа на простые множители имеет вид

Число взаимно просто с тогда и только тогда, когда ни один из простых делителей не делит . Если теперь свойство означает, что делит , то количество чисел взаимно простых с есть .

Количество чисел, обладающих свойствами равно , поскольку .

По формуле включений-исключений находим

Эта формула преобразуется к виду:

Беспорядком называется перестановка без неподвижных точек.

Количество всех беспорядков порядка n может быть вычислено с помощью принципа включения-исключения и дается выражением:

которое называется субфакториалом числа n.

Билет намбер 3:

Линейный оператор и его матрица. Собственные числа и собственные векторы линейного оператора. Понятие диагонализируемости линейного оператора. Существование базиса из собственных векторов линейного оператора как основной необходимый и достаточный признак его диагонализируемости. Характеристический многочлен линейного оператора и его свойства.

Ответ на билет намбер 3:

Пусть заданы линейные пространства и . Правило, по которому каждому элементу ставится в соответствие единственный элемент , называется оператором, действующим в линейных пространствах . Результат действия оператора на элемент обозначают или . Если элементы и связаны соотношением , то называют образом элемента ; элемент прообразом элемента .

Множество элементов линейного пространства , для которых определено действие оператора , называют областью определения оператора и обозначают .

Множество элементов линейного пространства , которые являются образами элементов из области определения оператора , называют образом оператора и обозначают . Если , то .

Оператор , действующий в линейных пространствах называется линейным оператором, если и для любых и для любого числа .

Если пространства и совпадают, то говорят, что оператор действует в пространстве . В дальнейшем ограничимся рассмотрением линейных операторов, действующих в линейном пространстве .