Литература 22 3 основные операции со множествами 4 Основные операции со множествами Определение
 Скачать 154.25 Kb.
|
|
Лекции по дискретной математике: комбинаторика Ф.Г. Кораблев, В.В. Кораблева Оглавление 1. Основные операции со множествами 4 2. Основные комбинаторные числа и их рекуррентные соотношения 7 3. Свойства комбинаторных чисел 10 4. Принцип включения-исключения 15 5. Линейные рекуррентные соотношения с постоянными коэффициентами 18 Литература 22 3 1. ОСНОВНЫЕ ОПЕРАЦИИ СО МНОЖЕСТВАМИ 4 1. Основные операции со множествами Определение. Пусть X, Y — два множества. Положим (1) X ∪ Y = {x|x ∈ X или x ∈ Y }; (2) X ∩ Y = {x|x ∈ X и x ∈ Y }; (3) X \ Y = {x|x ∈ X и x ̸∈ Y }. Тогда X ∪ Y называется объединением множеств X и Y , X ∩ Y называется пересечением множеств X и Y , X \ Y называется разностью множеств X и Y . Если Y ⊆ X, то Y = X \ Y называется дополнением множества Y в множестве X. Определение. Пусть X – множество, Y ⊆ X. Характеристической функцией подмножества Y называется функция χ Y : X → {0, 1}, заданная правилом: χ Y (x) = { 1, если x ∈ Y 0, если x ̸∈ Y . Теорема 1.1 (Об основных операциях над множествами). Операции ∪, ∩ и \ обладают следующими свойствами: (1) X ∪ Y = Y ∪ X и X ∩ Y = Y ∩ X; (2) (X ∪ Y ) ∪ Z = X ∪ (Y ∪ Z) и (X ∩ Y ) ∩ Z = X ∩ (Y ∩ Z); (3) (X ∪ Y ) ∩ Z = (X ∩ Z) ∪ (Y ∩ Z) и (X ∩ Y ) ∪ Z = (X ∪ Z) ∩ (Y ∪ Z); (4) X ∩ Y = X ∪ Y и X ∪ Y = X ∩ Y ; (5) X ∪ X = X и X ∩ X = X; (6) X = X. Доказательство. Докажем третье свойство (X ∪ Y ) ∩ Z = (X ∩ Z) ∪ (Y ∩ Z). Для доказательства равенства двух множеств надо показать, что множество из ле- вой части равенства содержится в множестве из правой части равенства, и наоборот, множество из правой части равенства содержится в множестве из левой части ра- венства. 1. Пусть x ∈ (X ∪ Y ) ∩ Z. Тогда x ∈ X ∪ Y и x ∈ Z. Так как x ∈ X ∪ Y , то либо x ∈ X, либо x ∈ Y . Рассмотрим каждый из этих случаев отдельно. 1.1. Пусть x ∈ X. Тогда, так как x ∈ Z, то x ∈ X ∩Z. Следовательно x ∈ (X ∩Z)∪ (Y ∩ Z). Таким образом в этом случае, если x ∈ (X ∪ Y ) ∩ Z, то x ∈ (X ∩ Z) ∪ (Y ∩ Z). Это означает, что (X ∪ Y ) ∩ Z ⊆ (X ∩ Z) ∪ (Y ∩ Z). 1.2. Пусть x ∈ Y . Тогда, аналогично предыдующему случаю, так как x ∈ Z, то x ∈ Y ∩ Z. Следовательно x ∈ (X ∩ Z) ∪ (Y ∩ Z). Снова получаем, что (X ∪ Y ) ∩ Z ⊆ (X ∩ Z) ∪ (Y ∩ Z). 2. Пусть теперь x ∈ (X ∩ Z) ∪ (Y ∩ Z). Это означает, что либо x ∈ X ∩ Z, либо x ∈ Y ∩ Z. Снова рассмотрим каждый из этих случаев по-отдельности. 2.1. Пусть x ∈ X ∩ Z. Тогда x ∈ X и x ∈ Z. Так как x ∈ X, то x ∈ X ∪ Y . Следовательно x ∈ (X ∪ Y ) ∩ Z. Получаем, что (X ∩ Z) ∪ (Y ∩ Z) ⊆ (X ∪ Y ) ∩ Z. 2.2. Пусть x ∈ Y ∩ Z. Тогда x ∈ Y и x ∈ Z. Снова, так как x ∈ Y , то x ∈ X ∪ Y . Следовательно x ∈ (X ∪ Y ) ∩ Z. Получаем, что (X ∩ Z) ∪ (Y ∩ Z) ⊆ (X ∪ Y ) ∩ Z. 1. ОСНОВНЫЕ ОПЕРАЦИИ СО МНОЖЕСТВАМИ 5 Таким образом мы получили, что с одной стороны (X ∪Y )∩Z ⊆ (X ∩Z)∪(Y ∩Z), а с другой стороны (X ∩ Z) ∪ (Y ∩ Z) ⊆ (X ∪ Y ) ∩ Z. Следовательно (X ∪ Y ) ∩ Z = (X ∩ Z) ∪ (Y ∩ Z). Доказательство оставшихся свойств из формулировки теоремы оставляется в ка- честве упражнения. Определение. Пусть X — множество. Множество всех подмножеств мно- жества X называется булеаном и обозначается 2 X . Определение. Мощностью множества X называется число элементов в мно- жестве X и обозначается |X|. Теорема 1.2 (Свойства характеристической функции). Пусть A, B — подмножества множества X. Тогда справедливы следующий ра- венства: (1) χ A ∩B (x) = χ A (x)χ B (x); (2) χ A (x) = 1 − χ A (x); (3) χ A ∪B (x) = χ A (x) + χ B (x) − χ A (x)χ B (x); (4) ∑ x ∈X χ A (x) = |A|. Доказательство. Докажем третье равенство χ A ∪B (x) = χ A (x) + χ B (x) − χ A (x)χ B (x). Пусть x ∈ X. Возможны четыре случая: x ∈ A \ B, x ∈ B \ A, x ∈ A ∩ B и x ∈ X \ (A ∪ B). Покажем, что равенство справедливо во всех четырех случаях. 1. Пусть x ∈ A \ B. Тогда x ∈ A ∪ B, x ∈ A и x /∈ B. Следовательно χ A ∪B (x) = 1, χ A (x) = 1 и χ B (x) = 0. Тогда χ A ∪B (x) = χ A (x) + χ B (x) − χ A (x)χ B (x). 2. Аналогичным образом равенство справедливо в случае, когда x ∈ B \ A. 3. Пусть x ∈ A ∩ B. Тогда x ∈ A и x ∈ B. Следовательно χ A ∪B (x) = χ A (x) = χ B (x) = 1. Отсюда следует, что χ A ∪B (x) = χ A (x) + χ B (x) − χ A (x)χ B (x). 4. Пусть, наконец, x ∈ X \ (A ∪ B). Тогда x /∈ A и x /∈ B. Следовательно χ A ∪B (x) = χ A (x) = χ B (x) = 0. Отсюда следует, что χ A ∪B (x) = χ A (x) + χ B (x) − χ A (x)χ B (x). Доказательство оставшихся трех равенств из формулировки теоремы оставляется в качестве упражнения. Определение. Пусть для каждого i ∈ I множество X i является подмноже- ством множества X. Если X = ∪ i ∈I X i , то совокупность {X i |i ∈ I} подмножеств множества X называется покрытием множества X. Определение. Покрытие {X i |i ∈ I} называется разбиением множества X, если (1) X i ∩ X j = ∅, при i ̸= j; (2) |X i | > 0 для любого i ∈ I. Пример. 1. Пусть X = N. Рассмотрим множества: X 0 = {x ∈ X|x ≡ 0(3)}, т. е. X 0 = {3, 6, 9, . . .} X 1 = {x ∈ X|x ≡ 1(3)}, т. е. X 1 = {1, 4, 7, 10, . . .} 1. ОСНОВНЫЕ ОПЕРАЦИИ СО МНОЖЕСТВАМИ 6 X 2 = {x ∈ X|x ≡ 2(3)}, т. е. X 2 = {2, 5, 8, 11, . . .} Тогда {X 0 , X 1 , X 2 } является разбиением множества X. 2. Пусть X = (0; 1) ⊂ R. Рассмотрим бесконечное семейство подмножеств X n = ( 1 n ; 1) ⊂ X, n > 2. Т. е. X 2 = ( 1 2 ; 1), X 3 = ( 1 3 ; 1) и т. д. Тогда {X 2 , X 3 , X 4 , . . . } является бесконечным покрытием множества X. Теорема 1.3 (Правило суммы). Если {X i |i = 1, 2, . . . , n} — разбиением множества X, и для каждого i = 1, . . . , n мощность |X i | конечна, то |X| = n ∑ j=1 |X j |. Доказательство. Доказательство проведем индукцией по числу n элементов в разбиении множества X. База индукции: пусть n = 1. Тогда X = X 1 . Следовательно |X| = |X 1 |. Пусть теперь n = 2. Тогда X = X 1 ∪ X 2 и X 1 ∩ X 2 = ∅. Рассмотрим характеристическую функцию χ X (x). С одной стороны ∑ x ∈X χ X (x) = |X|. С другой стороны ∑ x ∈X χ X (x) = ∑ x ∈X χ X 1 ∪X 2 (x) = ∑ x ∈X (χ X 1 (x) + χ X 2 (x) − χ X 1 ∩X 2 (x)) = = ∑ x ∈X χ X 1 (x) + ∑ x ∈X χ X 2 (x) = |X 1 | + |X 2 | Предположение индукции: пусть при всех k < n утверждение теоремы справед- ливо. Шаг индукции: Пусть X = n ∪ j=1 X j . Рассмотрим множество X ′ = n −1 ∪ j=1 X j . Так как {X 1 , . . . , X n } является разбиением множества X, то {X 1 , . . . , X n −1 } является разбие- нием множества X ′ , и тогда по предположению индукции: |X ′ | = n −1 ∑ j=1 |X j |. Заметим, что {X ′ , X n } является разбиением множества X. В частности X ′ ∩ X n = ∅. Имеем |X| = |X ′ | + |X n | = n −1 ∑ j=1 |X j | + |X n | = n ∑ j=1 |X j |. Теорема 1.4 (О числе всех подмножеств). Пусть X — множество. Тогда |2 X | = 2 |X| . Доказательство. Докажем индукцией по числу элементов в множестве X. База индукции: пусть |X| = 0. Тогда X = ∅ и 2 ∅ = {∅}. Следовательно |2 ∅ | = |{∅}| = 1 = 2 0 Предположение индукции: пусть утверждение теоремы верно при |X| < n. 2. ОСНОВНЫЕ КОМБИНАТОРНЫЕ ЧИСЛА И ИХ РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ 7 Шаг индукции: пусть |X| = n > 0. Зафиксируем элемент a ∈ X и положим C 0 = {Y ∈ 2 X |a ̸∈ Y } и C 1 = {Y ∈ 2 X |a ∈ Y }. Тогда C 0 ∩ C 1 = ∅ и 2 X = C 0 ∪ C 1 . Следовательно {C 0 , C 1 } является разбиением множества 2 X . Тогда по правилу суммы 2 X = |C 0 | + |C 1 |. Но |C 0 | = |C 1 | = |{Y ⊆ X \ {a}}|. Имеем 2 X = 2 |C 0 | = 2 · 2 X \{a} = 2 |X| Определение. Пусть X 1 , X 2 , . . . , X n — множества. Множество {(x 1 , . . . , x n ) |x i ∈ X i , i = 1, . . . , n } называется прямым произведением множеств X 1 , X 2 , . . . , X n и обозначается X 1 × . . . × X n . Теорема 1.5 (Правило произведения). Для любых конечных множеств X 1 , X 2 , . . . , X n справедливо равенство |X 1 × X 2 × . . . × X n | = |X 1 | · |X 2 | · . . . · |X n |. Доказательство. Докажем индукцией по числу сомножителей n в прямом про- изведении. База индукции: пусть n = 2. Заметим, что X 1 × X 2 = |X 1 | ∪ i=1 {u i } × X 2 , где X 1 = {u 1 , u 2 , . . . , u |X 1 | }. Более того, ( {u i } × X 2 ) ∩ ({u j } × X 2 ) = ∅ при i ̸= j, и |{u i } × X 2 | = |X 2 | ̸= 0. Следовательно совокупность {{u 1 } × X 2 , . . . , {u |X 1 | } × X 2 } является разбиением множества X 1 × X 2 . Тогда по правилу суммы |X 1 × X 2 | = |X 1 | ∑ i=1 |{u i } × X 2 | = |X 1 | ∑ i=1 |X 2 | = |X 1 | · |X 2 |. Предположение индукции: пусть утверждение теоремы справедливо для прямого произведения k < n сомножителей. Шаг индукции: рассмотрим множество X ′ = X 1 ×. . .×X n −1 . Тогда X 1 ×. . .×X n = X ′ × X n . Следовательно |X 1 × . . . × X n | = |X ′ × X n | = |X ′ | · |X n | = |X 1 | · . . . · X n |. 2. Основные комбинаторные числа и их рекуррентные соотношения Определение. Пусть X — множество мощности n > 0, и пусть k > 0. Число различных подмножеств мощности k в множестве X называется числом сочета- ний из n по k и обозначается C k n . Пример. Рассмотрим X = {1, 2, 3} и k = 2. Тогда существует ровно три раз- личных подмножества мощности 2: {1, 2}, {2, 3} и {1, 3}. Следовательно C 2 3 = 3. Теорема 2.1 (О рекуррентном соотношении для числа сочетаний). 1. C 0 n = C n n = 1; 2. C k n = 0 при k > n; 3. C k n = C k −1 n −1 + C k n −1 . 2. ОСНОВНЫЕ КОМБИНАТОРНЫЕ ЧИСЛА И ИХ РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ 8 Доказательство. 1. Справедливость равенств C 0 n = 1 и C n n = 1 следует из того, что единственное подмножество мощности 0 — это пустое множество ∅, а единствен- ное подмножество мощности n — это все множество X. 2. C k n = 0 при k > n так как не существует подмножеств мощности k > n в множестве из n элементов. 3. Пусть n, k > 0 и пусть C = {Y ⊆ X||Y | = k}. Отметим, что |C| = C k n . Зафикси- руем некоторый элемент a ∈ X и рассмотрим два множества C 0 = {Y ⊆ X||Y | = k и a ̸∈ Y } и C 1 = {Y ⊆ X||Y | = k и a ∈ Y }. Так как C = C 0 ∪ C 1 и C 0 ∩ C 1 = ∅, то совокупность {C 0 , C 1 } является разбиением множества C. Заметим, что (1) |C 0 | = C k n −1 , так как элемент a не принадлежит ни одному множеству из |