Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
M — множество, состоящее из n элементов, m 6 n. Размещением из n элементов по m или упорядоченной (n, m)-выборкой, называется любой кортеж (a i 1 , a i 2 , . . . , a i m ), состоящий из m попарно различных элементов мно- жества M. Размещение можно рассматривать как разнозначную функцию f : {1, 2, . . . , m} → M, для которой f (j) = a i j Пример 5.2.1. Для множества M = {a, b, c} пары (a, b) и (b, a) являются размещениями из 3 по 2, тройка (a, c, b) — размещением из 3 по 3, а тройка (b, a, b) размещения не образует. ¤ Число размещений из n по m обозначается через A m n или P (n, m). Пока- жем, что A m n = n! (n − m)! = n(n − 1) . . . (n − m + 1) (5.1) (напомним, что 0! = 1). Действительно, размещение m элементов мож- но представить как заполнение некоторых m позиций элементами множе- ства M. При этом первую позицию можно заполнить n различными спосо- бами. После того как 1-я позиция заполнена, элемент для заполнения 2-й позиции можно выбрать (n − 1) способами. Если продолжить этот процесс, 172 Глава 5. КОМБИНАТОРИКА то после заполнения позиций с 1-й по (m − 1)-ю будем иметь (n − m + 1) спо- собов заполнения последней, m-й позиции. Перемножая эти числа, получаем формулу (5.1). Пример 5.2.2. Из десяти различных книг произвольным образом бе- рутся и ставятся на полку одна за другой 3 книги. Имеется A 3 10 вариантов расстановок, где A 3 10 = 10! 7! = 10 · 9 · 8 = 720. ¤ Cочетанием из n элементов по m или неупорядоченной (n, m)-выборкой называется любое подмножество множества M, состоящее из m элементов. Пример 5.2.3. Если M = {a, b, c}, то {a, b}, {a, c}, {b, c} — все сочетания из 3 по 2. ¤ Число сочетаний из n по m обозначается через C m n , ¡ n m ¢ или C(n, m). Если объединить размещения из n элементов по m, состоящие из од- них и тех же элементов (не учитывая порядка их расположения), в клас- сы эквивалентности, то можно установить биекцию ϕ между сочетаниями и полученными классами по следующему правилу: ϕ({a i 1 , a i 2 , . . . , a i m }) {(b 1 , b 2 , . . . , b m ) | {b 1 , b 2 , . . . , b m } = {a i 1 , a i 2 , . . . , a i m }}. Так как из каждого сочетания C можно получить m! размещений (упорядочивая m! способами элементы из множества C по числу перестановок этого множества), то каж- дый класс эквивалентности содержит m! размещений и, значит, A m n = m!·C m n , т. е. C m n = A m n m! . Таким образом, C m n = n! (n − m)! m! . Пример 5.2.4. Из десяти чисел четыре можно выбрать C 4 10 = 10! 6!4! = = 7·8·9·10 4! = 7·8·9·10 1·2·3·4 = 210 способами. ¤ Число C m n обладает следующими свойствами: 1) C m n = C n−m n ; 2) C m n + C m+1 n = C m+1 n+1 (правило Паскаля); 3) (a + b) n = n P m=0 C m n a m b n−m для любых a, b ∈ R, n ∈ ω (бином Ньютона). В силу последнего свойства числа C m n называются биномиальными коэф- фициентами. Пример 5.2.5. Из свойства 3 следует, что 2 n = n P m=0 C m n . Действительно, 2 n = (1 + 1) n = n P m=0 C m n 1 m 1 n−m = n P m=0 C m n . ¤ 5.3. РАЗМЕЩЕНИЯ И СОЧЕТАНИЯ С ПОВТОРЕНИЕМ 173 § 5.3. Размещения и сочетания с повторением Размещением с повторением из n элементов по m или упорядоченной (n, m)-выборкой с возвращениями называется любой кортеж (a 1 , a 2 , . . . , a m ) элементов множества M, для которого |M| = n. Поскольку в кортеж (a 1 , a 2 , . . . , a m ) на каждое место может претендовать любой из n элементов множества M, число размещений с повторениями ˆ P (n, m) равно n · n · . . . · n | {z } m раз = n m : ˆ P (n, m) = n m . Пример 5.3.1. Из цифр 1, 2, 3, 4 можно составить ˆ P (4, 3) = 4 3 = 64 трехзначных числа. ¤ Определим отношение эквивалентности на множестве размещений с по- вторениями из n по m: (a 1 , a 2 , . . . , a m ) ∼ (b 1 , b 2 , . . . , b m ) ⇔ для любого c ∈ M число элементов a i , равных c, совпадает с числом элементов b i , равных c. Сочетанием с повторением из n элементов по m или неупорядоченной (n, m)-выборкой с возвращениями называется любой класс эквивалентности по отношению ∼ множества размещений с повторениями из n элементов по m. Другими словами, сочетания с повторениями суть множества, которые состоят из элементов, выбранных m раз из множества M, причем один и тот же элемент допускается выбирать повторно. Число сочетаний с повторениями из n элементов по m обозначается через ˆ C(n, m) и вычисляется по формуле ˆ C(n, m) = C m n+m−1 = (n + m − 1)! m!(n − 1)! . Пример 5.3.2. Число различных бросаний двух одинаковых кубиков равно ˆ C(6, 2) = C 2 7 = 21. ¤ § 5.4. Разбиения Пусть M — множество мощности n, {M 1 , M 2 , . . . , M k } — разбиение мно- жества M на k подмножеств, |M i | = m i , m 1 + m 2 + . . . + m k = n. Кортеж (M 1 , . . . , M k ) называется упорядоченным разбиением множества M. 174 Глава 5. КОМБИНАТОРИКА Если k = 2, то упорядоченное разбиение множества M на два подмноже- ства, имеющие соответственно m 1 и m 2 элементов, определяется сочетанием (без повторений) из n элементов по m 1 или из n по m 2 (m 2 = n − m 1 ). Следо- вательно, число разбиений R(m 1 , m 2 ) равно биномиальному коэффициенту C m 1 n = C m 2 n . Таким образом, R(m 1 , m 2 ) = n! m 1 !(n − m 1 )! = n! m 1 ! m 2 ! . В общем случае число R(m 1 , m 2 , . . . , m k ) упорядоченных разбиений (M 1 , M 2 , . . . , M k ), для которых |M i | = m i , равно n! m 1 ! m 2 ! . . . m k ! , а число R 0 (n, k) упорядоченных разбиений на k подмножеств вычисляется по фор- муле R 0 (n, k) = X m 1 + ... +m k =n, m i >0 R(m 1 , m 2 , . . . , m k ). Числа R(m 1 , m 2 , . . . , m k ) называются полиномиальными коэффициентами, поскольку для всех a 1 , a 2 , . . . , a k ∈ R справедливо соотношение (a 1 + a 2 + . . . + a k ) n = X m 1 + ... +m k =n, m i >0 n! m 1 ! . . . m k ! · a m 1 1 a m 2 2 . . . a m k k . Пример 5.4.1. В студенческой группе, состоящей из 25 человек, при вы- боре старосты за выдвинутую кандидатуру проголосовали 12 человек, про- тив — 10, воздержались — 3. Сколькими способами могло быть проведено такое голосование? Пусть M — множество студентов в группе, M 1 — множество студентов, проголосовавших за выдвинутую кандидатуру, M 2 — множество студентов, проголосовавших против, M 3 — множество студентов, воздержавшихся от голосования. Тогда |M| = 25, |M 1 | = 12, |M 2 | = 10, |M 3 | = 3, (M 1 , M 2 , M 3 ) — упорядоченное разбиение множества M. Искомое число R(12, 10, 3) равно 25! 12!10!3! = 1487285800. ¤ Число ˆ R(l 1 , l 2 , . . . , l r ; m 1 , m 2 , . . . , m r ) разбиений исходного множества M на k подмножеств, неупорядоченных между собой, среди которых l i множеств 5.5. МЕТОД ВКЛЮЧЕНИЙ И ИСКЛЮЧЕНИЙ 175 имеет мощность m i , i = 1, . . . , r, l 1 + . . . + l r = k, m 1 l 1 + . . . + m r l r = n, вычисляется по формуле ˆ R(l 1 , . . . , l r ; m 1 , . . . , m r ) = n! l 1 ! . . . l r !(m 1 !) l 1 . . . (m r !) l r , а число всех возможных разбиений множества M на k подмножеств, неупо- рядоченных между собой, равно X l 1 +...+l r =k, m 1 l 1 + ... +m r l r =n, m i >0 при l i >0 ˆ R(l 1 , . . . , l r ; m 1 , . . . , m r ). Пример 5.4.2. Сколькими способами из группы в 28 человек можно сформировать 4 коалиции по 7 человек? Пусть M — множество людей в группе, l i — число коалиций по i человек, где i = 1, . . . , 28. Тогда по условиям задачи имеем |M| = 28, l 7 = 4, l i = 0, i ∈ {1, 2, . . . , 28} \ {7}, m 7 = 7, и, следовательно, искомое число будет равно ˆ R(4; 7) = 28! 4!(7!) 4 . ¤ § 5.5. Метод включений и исключений Пусть множество A имеет N элементов и n одноместных отношений (свойств) P 1 , P 2 , . . ., P n . Каждый из N элементов может обладать или не обладать любым из этих свойств. Обозначим через N i 1 ...i k число элемен- тов, обладающих свойствами P i 1 , . . . , P i k и, может быть, некоторыми дру- гими. Тогда число N(0) элементов, не обладающих ни одним из свойств P 1 , P 2 , . . . , P n , определяется по следующей формуле, называемой формулой включений и исключений: N(0) = S 0 − S 1 + S 2 − . . . + (−1) n S n , (5.2) где S 0 = N; S k = P 16i 1 <... k 6n N i 1 ...i k , k = 1, 2, . . . , n. Пример 5.5.1. Пусть колода состоит из n карт, пронумерованных чис- лами 1, 2, . . . , n. Сколькими способами можно расположить карты в колоде так, чтобы ни для одного i (1 6 i 6 n) карта с номером i не занимала i-е место? 176 Глава 5. КОМБИНАТОРИКА Имеется n свойств P i в виде “i-я карта занимает в колоде i-е место”. Число всевозможных расположений карт в колоде равно n!. Число N i 1 ...i k располо- жений, при которых карта с номером i j занимает место i j (j = 1, . . . , k), равно (n − k)!. Тогда S 0 = n!, S k = X 16i 1 <... k 6n N i 1 ...i k = C k n (n − k)! = n! k! . Используя формулу (5.2), получаем, что число N(0) расположений, при ко- торых ни одно из свойств P i не выполнено, равно n X k=0 (−1) k S k = n! n X k=0 (−1) k 1 k! . ¤ Обобщая формулу (5.2), получаем формулу, позволяющую вычислить число N(r) элементов, обладающих ровно r свойствами (1 6 r 6 n): N(r) = n−r X k=0 (−1) k C r r+k S r+k . (5.3) В § 3.4 мы определили функцию [x] для вещественных чисел x как наи- большее целое число, не превосходящее x. Для положительных целых чисел a и b значение функции [ b a ] равно количеству чисел из множества {1, 2, . . . , b}, которые делятся на a, т. е. кратных a. Пример 5.5.2. Сколько натуральных чисел от 1 до 500 делятся ровно на одно из чисел 3, 5 или 7? Обозначим свойства делимости на 3, 5 и 7 соответственно через P 1 , P 2 и P 3 . Тогда для N = 500 имеем N 1 = [ 500 3 ] = 166, N 2 = [ 500 5 ] = 100, N 3 = [ 500 7 ] = 71. Так как N 12 — число общих кратных для чисел 3 и 5, наименьшее общее кратное которых равно 15, то N 12 совпадает с количе- ством чисел, которые делятся на 15, т. е. N 12 = [ 500 15 ] = 33. Аналогич- но N 13 = [ 500 21 ] = 23, N 23 = [ 500 35 ] = 14, N 123 = [ 500 105 ] = 4. По формуле (5.3) находим искомое число чисел N(1) = 3−1 P k=0 (−1) k C 1 1+k S 1+k = (−1) 0 C 1 1 S 1 + +(−1) 1 C 1 2 S 2 + (−1) 2 C 1 3 S 3 = (N 1 + N 2 + N 3 ) − 2(N 12 + N 13 + N 23 ) + 3N 123 = = 166 + 100 + 71 − 2(33 + 23 + 14) + 3 · 4 = 209. ¤ 5.6. РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ 177 § 5.6. Рекуррентные соотношения. Возвратные последовательности Рекуррентным соотношением, рекуррентным уравнением или рекуррент- ной формулой называется соотношение вида a n+k = F (n, a n , a n+1 , . . . , a n+k−1 ), которое позволяет вычислять все члены последовательности a 0 , a 1 , a 2 , . . ., если заданы ее первые k членов. Пример 5.6.1. 1. Формула a n+1 = a n + d задает арифметическую про- грессию. 2. Формула a n+1 = q · a n определяет геометрическую прогрессию. 3. Формула a n+2 = a n+1 + a n задает последовательность чисел Фибо- наччи. ¤ В случае, когда рекуррентное соотношение линейно и однородно, т. е. выполняется соотношение вида |