Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
Пример 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-е место? 5.5. МЕТОД ВКЛЮЧЕНИЙ И ИСКЛЮЧЕНИЙ 173 Имеется 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. ¤ 174 Глава 5. КОМБИНАТОРИКА § 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 задает последовательность чисел Фибо- наччи. ¤ В случае, когда рекуррентное соотношение линейно и однородно, т. е. выполняется соотношение вида a n+k + p 1 a n+k−1 + . . . + p k a n = 0 (5.4) (p i = const), последовательность a 0 , a 1 , a 2 , . . . называется возвратной. Мно- гочлен P a (x) x k + p 1 x k−1 + . . . + p k (5.5) называется характеристическим для возвратной последовательности {a n }. Корни многочлена P a (x) называются характеристическими. Множество всех последовательностей, удовлетворяющих данному ре- куррентному соотношению, называется общим решением. Описание общего решения соотношения (5.4) имеет аналоги с описани- ем решения обыкновенного дифференциального уравнения с постоянными коэффициентами. Теорема 5.6.1. 1. Пусть λ — корень характеристического многочле- на (5.5). Тогда последовательность {cλ n }, где c — произвольная константа, удовлетворяет соотношению (5.4). 2. Если λ 1 , λ 2 , . . ., λ k — простые корни характеристического многочле- на (5.5), то общее решение рекуррентного соотношения (5.4) имеет вид a n = c 1 λ n 1 + c 2 λ n 2 + . . . + c k λ n k , где c 1 , c 2 , . . . , c k — произвольные константы. 5.6. РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ 175 3. Если λ i — корень кратности r i (i = 1, . . . , s) характеристического многочлена (5.5), то общее решение рекуррентного соотношения (5.4) име- ет вид a n = s X i=1 (c i1 + c i2 n + . . . + c ir i n r i −1 ) · λ n i , где c ij — произвольные константы. ¤ Зная общее решение рекуррентного уравнения (5.4), по начальным усло- виям a 0 , a 1 , . . ., a k−1 можно найти неопределенные постоянные c ij и тем самым получить решение уравнения (5.4) с данными начальными условия- ми. Пример 5.6.2. Найти последовательность {a n }, удовлетворяющую ре- куррентному соотношению a n+2 − 4a n+1 + 3a n = 0 и начальным условиям a 1 = 10, a 2 = 16. Корнями характеристического многочлена P a (x) = x 2 − 4x + 3 являются числа x 1 = 1 и x 2 = 3. Следовательно, по теореме 5.6.1 общее решение имеет вид a n = c 1 + c 2 3 n . Используя начальные условия, получаем систему ( c 1 + 3c 2 = 10, c 1 + 9c 2 = 16, решая которую, находим c 1 = 7 и c 2 = 1. Таким образом, a n = 7 + 3 n . ¤ Рассмотрим неоднородное линейное рекуррентное уравнение a n+k + p 1 a n+k−1 + . . . + p k a n = f (n), n = 0, 1, . . . (5.6) Пусть {b n } — общее решение однородного уравнения (5.4), а {c n } — частное (конкретное) решение неоднородного уравнения (5.6). Тогда после- довательность {b n +c n } образует общее решение уравнения (5.6), и тем самым справедлива Теорема 5.6.2. Общее решение неоднородного линейного рекуррентного уравнения представляется в виде суммы общего решения соответствую- щего однородного линейного рекуррентного уравнения и некоторого част- ного решения неоднородного уравнения. ¤ 176 Глава 5. КОМБИНАТОРИКА Таким образом, в силу теоремы 5.6.1 задача нахождения общего решения рекуррентного уравнения (5.6) сводится к нахождению некоторого частного решения. В отдельных случаях имеются общие рецепты нахождения частного ре- шения. Если f (n) = β n (где β не является характеристическим корнем), то, под- ставляя a n = cβ n в (5.6), получаем c(β k + p 1 β k−1 + . . . + p k ) · β n = β n и отсюда c · P a (β) = 1, т. е. частное решение можно задать формулой a n = 1 P a (β) · β n Пусть f (n) — многочлен степени r от переменной n и число 1 не является характеристическим корнем. Тогда P a (1) = 1 + p 1 + . . . + p k 6= 0 и частное решение следует искать в виде a n = r P i=0 d i n i . Подставляя многочлены в фор- мулу (5.6), получаем r X i=0 d i (n + k) i + p 1 r X i=0 d i (n + k − 1) i + . . . + p k r X i=0 d i n i = = r X i=0 d i ((n + k) i + p 1 (n + k − 1) i + . . . + p k n i ) = = r X i=0 d i (g 1 n i + . . .) = f (n). Сравнивая коэффициенты в левой и правой частях последнего равенства, получаем соотношения для чисел d i , позволяющие эти числа определить. Пример 5.6.3. Найти решение уравнения a n+1 + 2a n = n + 1 (5.7) с начальным условием a 0 = 1. Рассмотрим характеристический многочлен P a (x) = x+2. Так как P a (1) = = 3 6= 0 и правая часть f (n) уравнения (5.6) равна n + 1, то частное реше- ние будем искать в виде c n = d 0 + d 1 · n. Подставляя c n в уравнение (5.7), получаем (d 0 +d 1 (n+1))+2(d 0 +d 1 ·n) = (3d 0 +d 1 )+3d 1 ·n = 1+n. Приравни- вая коэффициенты в левой и правой частях последнего равенства, получаем систему ( 3d 0 + d 1 = 1, 3d 1 = 1, ЗАДАЧИ И УПРАЖНЕНИЯ 177 откуда находим d 0 = 2 9 , d 1 = 1 3 . Таким образом, частное решение уравне- ния (5.7) имеет вид c n = 2 9 + 1 3 n. По теореме 5.6.1 общее решение однородно- го уравнения a n+1 + 2a n = 0 задается формулой b n = c · (−2) n , и по теореме 5.6.2 получаем общее решение уравнения (5.7): a n = 2 9 + 1 9 n + c · (−2) n . Из на- чального условия a 0 = 1 находим 2 9 + c = 1, т. е. c = 7 9 . Таким образом, a n = 2 9 + 1 3 n + 7 9 (−2) n . ¤ Задачи и упражнения 1. Сколько различных слов можно составить из букв a, b, c, d, если использо- вать каждую букву по одному разу? 2. Сколькими способами можно расставить 8 ладей на шахматной доске так, чтобы они не били друг друга? 3. Сколько различных флагов можно составить из трех горизонтальных полос белого, синего и красного цветов? 4. Сколькими способами можно составить список из 22 студентов? 5. В чемпионате участвуют 12 спортсменов. Сколькими способами могут быть распределены золотая, серебряная и бронзовая медали? 6. 15 студентов обменялись попарно друг с другом фотографиями. Сколько всего фотографий? 7. Сколько существует неупорядоченных четырехзначных кодов, составленных из 10 цифр? 8. Во взводе 3 сержанта и 30 солдат. Сколько существует способов выделения одного сержанта и трех солдат для патрулирования? 9. Сколькими способами из 20 студентов можно выбрать 5 делегатов? 10. Сколькими способами из простых делителей числа 2310 можно составить числа, имеющие ровно два простых делителя? 11. Сколько диагоналей имеет выпуклый n-угольник? 12. Найти наибольшее возможное число пересечений диагоналей выпуклого n-угольника. 13. Сколькими способами можно разбить группу из 15 человек на две подгруп- пы, в одну из которых входят 4 человека, а в другую — 11? 178 Глава 5. КОМБИНАТОРИКА 14. Решить уравнение: а) A 5 n = 18 · A 4 n−2 ; б) C x−2 x = 45, в) C 2x+3 2x+8 = 13 · A 3 2x+6 15. Найти два средних члена разложения (a 3 − ab) 31 16. Доказать, что а) 1 − C 1 n + C 2 n − C 3 n + . . . + (−1) n = 0; б) 1 2 + (C 2 n ) 2 + . . . + (C n n ) 2 = C n 2n 17. Крокодил имеет 68 зубов. Доказать, что среди 16 17 крокодилов может не ока- заться двух с одним и тем же набором зубов. 18. Сколько различных десятизначных чисел можно написать, используя циф- ры 0, 1 и 2? 19. Алфавит X состоит из двух символов. Сколько существует слов алфавита X, длины которых не превосходят 4? 20. Автомобильные номера данного региона состоят из трех цифр и трех букв алфавита X = {A, B, C, D, E, H, K, M, O, P, T, X, Y}. Сколько автомобилей может быть занумеровано различными номерами? 21. Сколькими способами можно разложить 5 монет достоинством 1 коп., 5 коп., 10 коп., 50 коп., 1 руб. в два кармана? 22. Чему равно число различных результатов бросаний двух неотличимых ку- биков, на грани каждого из которых нанесены цифры 1, 2, 3, 4, 5, 6? 23. Сколько различных перестановок образуется из следующих слов: а) зебра; б) баран; в) водород; г) абракадабра? 24. Группе из пяти сотрудников выделено три путевки. Сколько существует спо- собов распределения путевок, если: а) все путевки различны; б) все путевки одинаковы? 25. Сколько существует способов размещения 8 человек в восьмиместном авто- мобиле, если место водителя могут занять 4 человека? 26. На арену цирка выводятся 5 львов и 4 тигра. Сколькими способами мож- но расположить зверей в цепочку, если запрещено выводить тигров одного за другим? ЗАДАЧИ И УПРАЖНЕНИЯ 179 27. В лотерее разыгрывается 5 выигрышных билетов. Подошедший к урне вы- нимает наугад 5 билетов из 100 имеющихся. Сколькими способами можно вынуть 3 выигрышных билета? 28. Имеется 2n билетов в театр на один ряд, состоящий из 2n мест. Сколько су- ществует способов распределения мест для компании из n мужчин и n жен- щин, если не располагаются рядом двое мужчин и две женщины? 29. На плоскости заданы m параллельных прямых, а также n параллельных прямых так, что каждая из m прямых пересекается с каждой из n прямых в единственной точке. Сколько различных параллелограммов можно соста- вить из рассматриваемых прямых? 30. Сколько решений в натуральных числах имеет уравнение x 1 + x 2 + . . . + x n = n? |