Введение в прикладную комбинаторику, Кофман А. (984071), страница 4
Текст из файла (страница 4)
4, б) и т. д. Отыскание числа таких классов и их состава— важная комбннаторная задача. Предположим, далее, что каждой клетке (Хь Х;) сопоставлена числовая функция, а каждому решению — величина, равная сумме этих чисел; найдем решение с минимальной величиной. Если функция величины задана, как на рис. 2, то решение, указанное на рис. 1 или на рис. 3, имеет величину 3+ 3+ 2+ + 9+ 1 = 13. Отыскивая решение с минимальной величиной, мы приходим к одному из двух решений, представленных на рис. 5, для которых эта величина равна 9. А В С В В А В С 0 Е б! а! Рис. 5. Таким образом, читатель уже может получить представление о том, чем мы будем заниматься в этой книге.
В последующих параграфах сначала систематически излагаются методы пересчета. Этн методы, по существу, основаны на понятии производящей функции, и поэтому мы начнем с некоторых классических понятий анализа. Если читатель забыл некоторые понятия (комплексная плоскость, последовательность, голоморфная функция и т. д.), ему следует, не затрачивая излишних усилий, заглядывать время от времени в курс анализа. Математика представляет собой единое целое, и трудно изучать комбинаторные структуры без подходящей базы математики непрерывного. $ 5. Производящие функции Пусть а„, и ен й), — последовательность.
Этой последовательности поставим в соответствие ряд по целым степеням г: !" (г)=по+а,г+агг'+ ... +аиг" + ... (5,1) Предположим, что всегда существует неотрицательное а, для которого )а„~ ( и", и в этом случае всякой последовательности а„ однозначно соответствует ряд !'(г) по целым степеням г, который является голоморфной функцией в области 1г) ( 1!и, !8 Соответствие между а„и )'(г) в этом случае взаимно однозначно. Функция !" (г) называется производящей функцией последовательности а„.
Последовательность а„ представляет собой функцию от и, и = О, 1, 2, ... Обозначим ее через !(и) и будем говорить, что между совокупностями )(и) и !"(г) существует взаимно однозначное соответствие. Вводятся также производящие функции другого типа, называемь1е зкспоненциальными производящими функциями; !"' (г) = а, + а,г+ а, —, + ... + а„—, + ..., (5.2) которыми в некоторых случаях пользоваться более удобно. Между ~'(г) и !'(п) в области !г) <!/а также существует взаимно однозначное соответствие. Производящие функции (5.!) и (5.2) допускают следующее обобщение: 1р" (г) = ао1ро (г) + а,1р, (г) + ... + а„1р„(г) + ... (5.3) Нужно, чтобы соответствие а„» ф*(г) было взаимно однозначно, что приводит к условию линейной независимости всех функций !р„(г). Важен следующий частный случай: Фо(г) = 1 Ф1(г) =г, Фо(г) =г(г — 1), ..., 1р„(г)=г(г — 1)(г — и+1), ..., (5,4) ф* (г) = ао + а,г + аог (г — 1) + ...
... + а„г (г — 1) (г — и + 1) + ... (5.5) Дальше будут рассматриваться также производящие функции других типов. Понятие производящей функции можно распространить на случай функций многих переменных. Последовательности ащ „, т, и ен )ц, т. е. функции 1(т, и), можно поставить в соответствие такую производящую функцию: ! ( 1' 2) 00+ Ю 1+ 01 2+ 20 1+ 11 1 2+а02 2+ ...
+аь1г! + ао ! 1г1 'г, +... +а, „1г1го '+аоого~+... (5.6) или более общую: ф'(го г ) = аооЛО(г1) Ро(го) + а!ой! (г1) Ро(г ) + ао!Ло (г1) Р! (го) + + а20Л1 (г!) !20 (г2) + а1!Л1 (г1) 12! (г1) + а01ЛО (г1) 222 (г2) + ... +а„,ОЛЕЙ(г1)120(го)+а !лЛ„,(г,)!21(г,)+ ... ... + а, „1Л1 (г1) !20 1(г2) + ао, Ло (г!) !20 (г2) + (5 7) !9 Используется также симметрическая форма, получаемая из (5.6). 1" (г„г,) + 1' (г„г,) = 2а„+ (а „+ ам) (г, + г.,) + +(ам+ „)(г';+гэ)+2апг,г.,+(а„+а„)(г',+гз)+ + (ам + а„) (г, + г,) г,г, + ... (5.8) 9 6. Сведения о конечноразностных операторах В исчислении конечных разностей вводится ряд основных операторов.
Оператор можно рассматривать как символ, кото- рый ставится перед функцией для указания некоторого способа получения новой функции. Основными операторами, используе- мыми в теории конечных разностей, являются Е[(х) = 1(х + Ь), Ь>О; (6.1) Л((х) = 1(х + Ь) — 1(х), Ь > О; (6.2) Р7 (х) = — 1(х) = 1'(х); (6.3) Ц(х) = Ь1(х), Ь еи К. (6.4) В данной книге операторы Е и Л будут рассматриваться толь- ко при Ь = 1, хотя в начале этого параграфа величина положи- тельного числа И не фиксируется. Если один оператор действует на некоторую функцию, а вто- рой оператор — на результат действия первого, то можно обра- зовать композицию этих операторов, записывая последующий оператор слева от предыдущего.
Легко доказать, что порядок применения операторов Е, Л, Р и к не играет роли, Например, Л [Р1(х)] — Л вЂ” 1(х) — — 1(х + Ь) — — 1(х)— = — [1(х + Ь) — 1 (х)] = Р [Л~ (х)]. (6.5) Следовательно, можно записать ЛР1(х) = Р Л1 (х), (6.6) Если оператор действует п раз, то это обозначают Е", Л", Р, к~, Таким образом, Л'1 (х) = Л Л) (х) = Л [1 (х + Ь) — 1 (х)] = = ~ (х + 2Ь) — ) (х + Ь) — ~ (х + Ь) + ~ (х) = =)(х+ 2Ь) — 2~(х+ Ь) + ~(х), (6.7) Ез1 (х) ЕЕЕ1(х) ЕЕ1(х + Ь) = Е1(х + 2Ь) 1(х+ ЗЬ), (68) Оператор с показателем О означает тождественный оператор 1, который будет отождествляться с числом Ь = 1; например, Л"1(х) = 11(х) = 1(х), (6.9) Операторы Е, Л, 0 и к удовлетворяют следующим двум основным зкспоненциальным законам: Р"Р"1(х)=0"0 1(х) Р ""7(х), т, лен й(; (6.10) (Р )" ~(х)=(Р")" ~(х) =Р ")(х), т, пеи Х.
(6.11) Сумма (разность) двух операторов, действующих на некото- рую функцию, определяется как сумма (разность) функций, по- лучающихся при применении каждого оператора к атой функ- ции; например, (Е + Р) ) (х) = Е~ (х) + Р~ (х) = ~ (х + й) + ~' (х), (6.12) Опишем алгебру операторов Е, Л, Р, К 1. Мы будем гово- рить, что два оператора равны, если в применении к одной и той же функции они дают один и тот же результат, например Л = Š— 1. (6.!3) Рассмотрим множество конечноразностных операторов 0 = = (Е, Л, Р, К 1).
Если А, В и С принадлежат О, то А+(В+С) = (А+В)+С вЂ” ассоциативность по сложению, (6,14) А+ В=В+ А — коммутативность по сложению, (6.15) А (ВС) = (АВ) С вЂ” ассоциативность по умножению, (6.16) АВ=ВА — коммутативность по умножению, (6.17) А (В+ С) = АВ+ АС вЂ” дистрибутивность слева, (6. 18) (В+ С) А = ВА + СА — дистрибутивность справа. (6.19) Таким образом, над операторами Е, Л, Р, к, ! можно произ- водить действии по законам алгебры действительных чисел с тем исключением, что отсутствуют операторы, обратные к 0 и Ь по умножению.
Например, Е"Р) (х) = Е"~'(х) = )'(х+ пй) = Р~ (х + пй) = РЕ") (х), (6 26) (Р— Л)(Р— Л) ~(х) =(Р' — 2РЛ+ Л'-) ~(х) = =1" (х) — 2~'(х+й) — 2~'(х)+~(х+26) — 2~(х+Ь)-(-~(х). (6,21) Операторы Е, Л, Р, й, 1 удовлетворяют следующим основ- ным условиям: Е1(х) =1(х+ Ь) = = 1(х) + Ь7'(х) + ! 7" (х) + ... + — 1'"'(х) + (1+ йР + -р — + ° ° + „, + .) 1(х) - а"о7(х). (6,22) Отсюда следует, что можно принять Е =е"о, (6.23) 2! Имеем также 1+ Д ело Д=сло — 1 (6.24) или (6.26) Иногда используется оператор (хР), определяемый следующим образом: (х Р) ) (х) = х)' (х). (6.26) Отсюда (хР)' 7 (х) = (хР) [(хР) 7 (х)] = (хР) [хг' (х)] „1 ( ) + х - (х) (хР) 7(х) =(хР)[(хР)')(х)]=(хР)[х~'(х)+ха~.
( )] = х [7 (х) + х[" (х) + 2х~" (х) + х'~"' (х)] = =х)'(х)+ Зхл7" (х) -]- хзт -(х) (6.27) Не следует смешивать (хР)') (х) с хлР'7 (х) (6. 28) прн А ~!. Оператор Р", примененный к произведению двух функций ~(х)д(х), дает знаменитую формулу Лейбница: л В Р" [[(х) д(х)] = ~ С'„(Р" "))(Р'д) = ~ С'„['" '(х) йи'(х).
(6 29) При выводе формулы Лейбница часто используется символическое разложение, очевидное при рассмотрении второго члена (6.29): л () + д)" = 2~ С'.~" 'д'. (6.30) и„=п', п=О, 1, 2, ... (6.31) Имеем Еи„=Епл=(и+1)», п=О, 1, 2, ..., "(6,32) Е'и„=Е'ил=(п+г)л, г= 1, 2, 3, (6.33) Можно положить Е'0' = г". (6.34) 22 достаточно затем заменить [л на )л(х) и йн на ~'(х). Этот метод символического разложения получит дальнейшее развитие в последующем изложении. С точки зрения дальнейших приложений интересно уточнить некоторые результаты.
Пусть Используя оператор Л, имеем Ьи„= Лп» = (п + 1)» — п», Ь»и„=Ь»л»=Ь[(л+ 1)» — и']= (и+ 2)» — 2(и+ 1)» + и», Лзи„= Рп» = Л [(л+ 2)» — 2(л+ 1)»+ л»[= =(и+ 3)' — 3(и+ 2)'+ 3(и+ 1)» — п', (6.35) л»+' (л+ 1)' (заменить п»+' на (л+ 1)»); (6,36) тогда Ьгп» = л» (и — 1)', п»+' — (и+ 1)», л= 1, 2, 3, ..., 1 = 1, 2, ..., г.
(6.37) Выпишем теперь ЛО» = 1» — О», Ь»0» = Л(1» — 0») =2» — 2 1»+ О», ЛЧР = Л (2» — 2 1» + 0») = 3» — 3 2» -[- 3 . 1» — О», (6.38) и полагаем Л'0 = 0 (Π— !)", 0 + †' 1". (6.39) Без труда можно получить рекуррентную формулу: Л'0 " =гй'0 +гй' О», г(/г. (6.40) Таблица 6.1 дает числа А'0" для п=1, 2, ..., 8 и г= =1,2, ..., 8, г((л. Укажем еще один важный результат, касающийся Е'0" и Л'0". Имеем Г Л'0"=(Š— 1)'0"= ~~ С ( — 1) Е' 0"=(разлагая (Š— 1)') = ~ С, ( — 1) (г — й)" (в силу (6.34)). (6.41) Это — общая формула для чисел Л'0". В следующем параграфе мы изучим вопрос о том, как использовать некоторые определенные выше операторы при вычислении различных производящих функций.
Условимся вместо и»+' писать (л+1)» в биномиальном раз- ложении, что символически обозначим Таблица 6.1 Таблица чисел Л'0" д'о" г=.з г=в г 5 г=! Г=т г д'0' Л го в 1 6 36 24 Л'0' 14 150 240 30 Л'0' 1 560 1 800 Лгов 540 720 126 !806 8 400 16 800 15 !20 д'о' 5 040 !в. 40 824 126 000 дгов $7. г-преобразование Производящую функцию )'(г) = ~ а„г" часто называют «преобразованием в г», или г-преобразованием. Некоторые авторы предпочитают ей следующую функцию; г()=Х .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
