Дискретная Математика. Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
 Скачать 6.37 Mb.
|
|
2.13. Практическое занятие № 4. Производящие функции и рекуррентные соотношения 2.13.1. Найти производящие функции следующих последовательностей: а) 0,1,2,... , α n n a n n ; б) ,... 2 , 1 , ! α , 0 , 0 n n n a n n ; в) 0,1,2,... , 2 n n a n ; г) N n N n a n , 0 , ,... 1 , 0 , 1 ; д) ,... 2 , 1 , 0 , α sin n n a n 2.13.2. Найти производящую функцию последовательности n a через производящую функцию последовательности n b , если а) ,... 2 , 1 , , 0 , 0 1 n b n a n n ; б) n i i n n b a 0 ,... 2 , 1 , 0 , ; в) k n b k n a k n n , , 1 ,..., 1 , 0 , 0 ; г) ,... 2 , 1 , 0 , 1 n b b a n n n 2.13.3.Найти производящую функцию последовательности 2 7 5 2 n n 2.13.4. Найти экспоненциальную производящую функцию последовательности n a , выраженную через производящую функцию последовательности n b , если а) ,... 2 , 1 , 0 , 1 n b a n n ; б) n r r r n r n n g b C a 0 ; 2.13.5. С помощью тождеств, связывающих производящие функции, вывести следующие тождества для биномиальных коэффициентов: Яков Бернулли (1654 – 1705) – швейцарский математик. 39 а) m n m n t t t 1 1 1 , k r k m n r k m r n C C C 0 ; б) m n m n t t t 2 1 1 1 1 1 , k r k k m n m r k m n r n C C C 0 1 2.13.6. Найти общий член n a последовательности, для которой функция t f a является производящей: а) m a pt q t f ; б) m a t t f 2 1 2 ; в) arctgt t f a ; г) t x a dx e t f 0 2 2.13.7. Применить технику производящих функций для нахождения суммы чисел: а) n i i n 0 2 2 2 2 2 1 ; б) n i i n 0 3 3 3 3 2 1 2.13.8. Сколькими способами можно разменять 10-копеечную монету монетами 1, 2, 3 и 5 копеек при условии, что каждая из разменных монет присутствует в двух экземплярах? 2.13.9. Сколькими способами выпуклый 2 n -угольник можно разбить на треугольники диагоналями, не пересекающимися внутри 2 n -угольника? Вывести рекуррентное соотношение для n a , где n a - число способов разбиения 2 n -угольника и разрешить это соотношение. 2.13.10. Решить рекуррентные соотношения: а) 8 , 3 , 1 , 3 3 2 1 0 1 2 3 a a a a a a a n n n n б) 3 , 2 , 1 , 0 2 1 0 1 2 3 a a a a a a a n n n n ; в) 0 , 1 , 0 9 1 0 2 a a a a n n 2.13.11. Решить неоднородные рекуррентные соотношения: а) 1 , 0 1 a n a a n n ; б) 2 3 , 1 , 2 4 1 1 0 1 2 a a a a a n n n n 2.13.12. Найти общее решение рекуррентных соотношений: а) 0 1 2 n n n a a a ; б) n n n a a a 4 1 1 2 2.13.13. Пусть t f a и t f b - производящие функции последовательностей n a и n b соответственно, и пусть 1 t f t f b a . Найти n b и t f b , если n m n C a 2.13.14. Найти производящую функцию t f a для последовательности n a , если n a - число решений в целых неотрицательных числах уравнения n z y x 5 3 2 2.13.15. Пусть n j j j n n C a 0 2 , 1 0 1 2 n j j j n n C b , ,... 2 , 1 , 0 n , а t f a и t f b - соответствующие производящие функции. Показать, что а) n a и n b связаны соотношениями вида ; 0 , 1 , , 0 0 1 1 1 b a a b b b a a n n n n n n б) t f a и t f b удовлетворяют системе уравнений 40 t tf t tf t f t f t tf t f b a b b a a , 1 и найти t f a и t f b 2.14. Метод включений и исключений Содержание комбинаторного анализа не исчерпывается подсчетом числа решений соответствующих задач. Не менее важное место в нем занимают проблемы возможности или невозможности осуществления требуемых выборок или расположений элементов. Логическая сущность метода включения и исключения определяется тем, что он применяется к важной задаче разделения множеств на подмножества в зависимости от того, обладают ли их элементы определенной совокупностью свойств или нет. Подсчет числа элементов объединения множеств. Рассмотрим сначала простую задачу о нахождении числа элементов объединения множеств. Будем обозначать через A n количество элементов множества A Основная формула, которой пользуются при нахождении числа элементов объединения двух множеств такова (см. рис 2.3): B A n B n A n B A n (2.14.1) Эта формула совершенно очевидна из диаграммы Эйлера - Венна. С помощью формулы (2.14.1) можно получить формулу для числа эле- U ментов объединения любого числа множеств. B Например, для трех элементов имеем A N C B A N C B A N A A N C B A N C B N B A A N C A B A N C B N B A N C B N C N B N A N C A B A N C A N U B A N C B N C N B N B A N C A B A N C A N C A N B A N C N B N A C C B A N C B N Эту формулу тоже C B A еще можно изобразить с помощью диаграммы (см. рис. 2.3). Для случая n слагаемых анало- Рис. 2.3. гичная формула доказывается методом матема- тической индукции. Теорема 2.3. Если n A A A ,..., , 2 1 - некоторые множества и n n A A N A A N A A N ,..., , 2 2 1 1 , то 2 1 2 1 A N A N A A A N n 4 2 1 3 2 1 1 3 1 2 1 A A A N A A A N A A N A A N A A N A N n n n 1 2 1 1 1 2 n n n n n A A A N A A A N (2.14.2) Формулу (2.14.2) можно обобщить и подсчитывать не только количество элементов данных множеств. Пусть дано n - множество n S некоторых элементов и k - множество свойств: k p p p ,..., , 2 1 , которыми элементы множества n S могут как обладать, так и не обладать. Выделим какую-либо r - выборку свойств ,..., , 2 1 r i i i p p p Число элементов n S s , обладающих всеми r выбранными свойствами обозначим через ,..., , 2 1 r i i i p p p n Отсутствие у элемента какого-либо свойства i p будем обозначать i p . Тогда, например, запись 3 2 1 , , p p p n означает число элементов, обладающих свойствами 1 p и 3 p и не обладающих свойством 2 p . 41 а) Пусть имеется одно свойство p , тогда p n n p n б) Имеется конечное число свойств k p p p ,..., , 2 1 , несовместимых друг с другом. Тогда опять k i i k p n n p p p n 1 2 1 ,..., , в) Элементы обладают комбинациями различных свойств. Тогда справедлива теорема, аналогичная теореме 2.3. Теорема 2.4. Если даны n - множество элементов и k - множество свойств k i p i , 1 , совместимых между собой, тогда k i k j i k l j i k k l j i j i i k p p p n p p p n p p n p n n p p p n 1 1 1 2 1 2 1 ,..., , 1 , , , ,..., , (2.14.3) Доказательство. Теорема может быть доказана с помощью простейших рассуждений, состоящих в попеременном отбрасывании и возвращении подмножеств. Применим, однако, метод математической индукции. p n n p n k , 1 . Эта формула очевидна. Пусть теорема верна для 1 k свойств, т. е. ,..., , 1 , , , ,..., , 1 2 1 1 1 1 1 1 1 1 1 2 1 k k k i k j i k l j i l j i j i i k p p p n p p p n p p n p n n p p p n (2.14.4) Перейдем к случаю, когда имеется k свойств. Так как p n n p n , то по аналогии можно написать , ,..., , ,..., , , ,..., , 1 2 1 1 2 1 1 2 1 k k k k k p p p p n p p p n p p p p n Применим соотношение (2.14.4) для числа , ,..., , 1 2 1 k k p p p p n Получим следующую формулу, которую обозначим (2.14.5) 1 1 1 1 1 2 1 1 1 2 1 , ,..., , 1 , , , , ,..., , k i k j i k k k k j i k i k k k p p p p n p p p n p p n p n p p p p n Прокомментируем эту формулу. В ней k k p p p p n , ,..., , 1 2 1 - число элементов, обладающих свойством k p и одновременно не обладающих свойствами 1 2 1 ,..., , k p p p ; k p n - число элементов, обладающих только свойством k p . 1 1 , k i k i p p n - число элементов, обладающих свойствами k i p p и одновременно и так далее. Ясно, что для того чтобы получить k k p p p p n , ,..., , 1 2 1 из общего числа элементов со свойством k p надо вычесть сначала число элементов, обладающих свойствами k i p p и . Однако при этом элементы, имеющие три свойства: именно k p и, скажем, j i p p и будут исключены дважды (сначала как элементы со свойствами k i p p и , затем как элементы со свойствами k j p p и ). Значит надо возвратить все элементы, обладающие тремя свойствами, то есть прибавить 1 1 , , k j i k j i p p p n и так далее. Вычтем теперь из (2.14.4) формулу (2.14.5), получим k i k j i k k k j i i k k k k j i k i k i j i k i k i k k k k p p p p n p p n p n n p p p p n p p n p p n p n p n n p p p n p p p p n p p p n 1 1 1 2 1 1 2 1 1 1 1 1 1 1 1 2 1 1 2 1 1 2 1 , ,..., , 1 , , ,..., , 1 , , ,..., , , ,..., , ,..., , 42 Характер доказательства этой теоремы таков, что его можно применить для любой комбинации свойств, как выполняющихся, так и не имеющих места. Таким образом, в левой части доказанной формулы может стоять не только k p p p n ,..., , 2 1 , но и, например, , , , 4 3 2 1 p p p p n Теорема формулируется при этом относительно совокупности свойств 4 2 и p p с обязательным выполнением свойств 3 1 и p p следующим образом: , , , , , , , , , , , 4 2 3 1 4 3 1 2 3 1 3 1 4 3 2 1 p p p p n p p p n p p p n p p n p p p p n (2.14.6) |