Введение в прикладную комбинаторику, Кофман А. (984071), страница 6
Текст из файла (страница 6)
(7.82) Из (7.83) следует, что «(п) = Р (п) — Р (п — 1). (7.84) Если Р'(г) — г-нреобразование для Р(п), а 7" (г) — г-нреобра. зование для 1(п), то 7' (г) = Р* (г) — гР" (г). (7.85) Итак, (7.86) Этот результат можно обобщить. Положим Р,(п) = Х ~(«), л Р,(п)= ~~'., Р,(г), (7.87) Рь(п) = Х Рь-~ («). Легко получить Р'() Г() ь (~ )ь (7.88) Основные свойства преобразований К*(г) и 7=(г). Найдем г-преобразование для Р(п) = Х 7(«). (7.83) Это как раз г-преобразование для последовательности, получаемой суммированием порядка й из 1(п); эту последовательность можно получить индукцией: Р, (и) =1(п)+1(п — 1)+ ... + 7(0), и Р (п) = Х (7 (г) + [(à — Ц+ " + 1(0)) = =)(п)+ 2~(п — 1)+ 3~(п — 2)+ ...
+(и+ 1) [(О), Рз (а) = Х [[ (г) + 2~ (г — 1) + ЗЯ вЂ” 2) + ... + (г + 1) ) (О) [ = Г=а = 1 (и) + 37 (а — 1) + 67 (и — 2) + ... + ~ 1(0), Ра(п) =7(п)+ й7(п — 1)+ ... +С~~а ~1(п — 1)+ ... ... + С~+~а ~[(0). (7.89) Оператор 11= б/бг, примененный к функции 1'"(г) (г-преобразованию для((а)), дает (см. (7.72) и (7,73)) Ф 1)2[ (г) ~~ г (т 1)1(т) гг-2 (7.90) 1) "7'*(г) = ~ А,'~ (г) г' ~. Имеет место другая основная формула: (7.91) Рассматривают также оператор Р(гР) (полипом относительно гР): Ю Р (г1)) [" (г) = ~ Р (с) ~ (г) г', (7.92) г 0 Приведем теперь несколько основных свойств экспоненциального г-преобразования.
34 По определению (см. (7.33)) О (г) = 1)' 1(п)— а О -1(0)+ 1(1)++1(2)+ ... ++1(й) +... (7.93) Полагаем символически 1ь — '1(е), Й=О, 1, 2, ..., (7.94) где — ' означает, что член справа заменяется на члены слева. Тогда разложение (7.93) запишется символически так (полагаем 1о = 1): 1'(г)=1+г1+ —,1т+ ... + —,1'+ ... е*~. (7.95) Исходя из (7.95), можно построить символическое исчисление, приводящее к интересным упрощениям. Например, если 1 (г)=е'~, д'(г)=е'е, (7.96) Р'(г) =1 (г) д (г)=е™+а'= -1+ (1+а)++(1+3)'+ ". + а) (1+а)'+ .... (7.97) то, полагая 1" — '1(й) а' — 'а(й).
1 — 1(0) а(0), имеем (1+а) 13 + А1 д + ... +СЦ "3'+ ... +1од (7.98) и ГЯ= 1(й) д(0)+ lг1()с — 1) д(1) + 1()т — 2)д(2)+ ... ... +С»1(й — г)д(г)+ ... +1(0)д(й). (799) Можно определить произведение экспоненциальных разложений Р (и) =,Е~ С'1(п — г) д (г) = ~ С"„1 (г) д (и — г). (7.100) т 0 1=о Это символическое разложение обобщается на любое число функций: 6$ ( ы Р'(г) = Ц 11(г) = ехр'(г ~~~ 15 (г) ), (7.101) ') Мы ае будем различать символы а» а ахр(»).
где суммирование производится по всем целым неотрицательным Й!, Аз, ..., й таким, что й!+Аз+...+ й = й. Переходя к несимволическому соотношению, получаем Р( )=Х „И,Ы, Уйдый,) ... 1„(й„). (7.103) Это символическое зкспоненциальное исчисление может быть использовано для вычисления по последовательности )(и) такой последовательности д(а), что 1'(г) а'(г) = 1. (7,104) Чтобы получить д(п), исходя из (7.104), можно, очевидно, воспользоваться экспоненциальным г-преобразованием, отыскивая последовательность, соответствующую Ц«(г), но можно также использовать символическое разложение: ... +Се! а + ...
+)од =О, А) 1, (7.105) добавляя условие )ойо (7. 106) Это дает а(0) =+. По) [(ц у(о)р ' 2 = — Т (~) 2 У ( Ц! У(О)Р + У(О)Р ат(6) = — — + 6 1(з) )(2)1(Ц У(ЦР у(о)р у(о)1 у(о)1» — 6 (7.107) УПРАЖНЕНИЯ 7А. Найти г.преобразование следующих функций, где в О, О, п=о, а) /(и) =а+1; б) !(л) ! в) 7(п) =— л+1 — п) 0; п1 лз ' 7Б. указать функцию !(л), соответствующую функции р (я): а) !'(а) 1 1 (! — яр ' ; б) 7'(я) = (1 + я)з; в) Р (я) !и !+я 7В. Используя я-преобразование, решить следующие уравнения в ко- нечных разностях: а) 1(л+ 1) — 31(л) = 2, где [(0) = 1; б) 1(я+ 2)— — 1(л) = я, где 1(0) = О, 1( Ц = 2; в) 1(п + 2) — 21(п + Ц + 1(в) = О, где ) (0) = 1, 1(Ц = 2.
7Г. Следующее конечноразностное уравнение порождает последова- тельность !(я), я О, 1, 2, ..., называемую «последовательностью Фнбо- наччию 1(п+ 2) — 1(и+ Ц вЂ” )(л) О, )(0) О, 1(Ц = 1, Полагаем Ф(а) =)(2а), Ч'(а) = ((2а+ 1). а) Найти г-преобразования Ф(а) н Ч'(а). б) Указать соотношение между Ф" (г) и Ч"'(г). в) Выписать в явном виде последовательности ((а), Ф(а) и Чг(а). 7Д. Получить эксноненциальное г-преобразование следующих функций !(а), п=О, 1, 2, ...: а) )(и) = а!, б) )(и) = 1, в) ((а) =а 7Е. Пусть а а-1 !(а)= ~С,,Э+П а=О, 1, 2, 3, ..., и д(а)=~~ С„)++1~, а=!, 2, 3, ... г=е г=е а) Показать, что )(а+1) =)(а) -(-й(а+ !), д(а-'Г 1) =((а)-~-д(а), учитывая, что 1(0) = 1 и д (0) = О. б) Показать, что для функций !'(г) и К*(г) выполняются соотношения: (*(г) — )=гр(г)+д" (г), г" (г) =г!'(г)+гЫ*(г). в) Показать, что 1 — г г Г (г) = и д'(г) = ге=э -т гз:*'7:т' 7Ж.
Числа Бернулли. Рассмотрим последовательность В(а): г» В (г) = гт В (а) — е», л е Вл ° В(а), а=1, 2 3, Вэ В(0) 1 где в«( ) г е» вЂ” 1 ' Приравнивая соответствующие коэффициенты в правой и левой частях ра. венства В« е» 1 пол аем соотношение уч (В+ !)" — В(а) =беы где В" — В(а), а 1, 2, 3, ..., В'= В(0) 1, 6„1— - О, а ~ 1, 0„1 = 1, а = 1. Исходя из этого соотношения, вычислить последовательность В(а), которая известна под названием «числа Бернулли».
Показать, что прн и > 2 все нечетные числа Бернулли равны нулю. $8. Применение производящей функции. Энумераторы и денумераторы сочетаний Рассмотрим некоторое множество объектов А = (Аь Аш ... ..., Ап); этому множеству сопоставим последовательность а; (! = 1, 2, ..., и) так, что а! соответствует Ао Образуем производящую функцию е'(г) =(1+ а1г)(1+ а„г) ... (! +а„г). (8.!) 37 Осуществим разложение (8.1): е'(г) = 1 + (а, + аз + ... + а„) г + (а а,+ а а, +... + а„,а„) г'+ + (аза,аз+ а,азаз+... + а„,а„заз) гз+... + а,азаз ...
а„г . (8.2) Полагаем Ез=1, Е,=а,+аз+ ... +а„, Е,=а,а,+а,а,+ .. +а„,а„, Е,=а,а,а,+а,а,а,+ ... +а„,а„,а„ (8.3) Е„ = а,азаз . а„. Коэффициенты Е„, г = 1, 2, ..., н, дают перечисление неупорядоченных т-выборок без повторения, или сочетаний без повто- РениЯ из и объектов Аз по т, если заменить аз на Аь ПРоизводЯ- щую функцию вида (8.1) назовем энумератором. Положим в (8.1) (8.4) а,=а,= ...
=а„=1 Тогда 4('„(г) = (1+ г)" = 1+ С'„г+ С'„г'+ ... + С'„'г". (8.5) Если положим теперь то коэффициенты а„г = 1, 2, ..., н, дают пересчет неупорядоченных г-выборок без повторения, или сочетаний без повторения из а объектов А; по г. Производящую функцию вида (8.5) назовем денуззератором, Рассмотрим сначала, как используются некоторые денумераторы, а к энумераторам вернемся несколько позднее. Подставим в (8.5) г = 1. Получаем Сз+ С,+ С,+ ... + С„"= 2".
(8.7) Подставим теперь в (8.5) г = — 1: Сз — Сз+Сз+ +( — 1)" Сз=О. (8.8) Складывая (8.7) и (8.8) и деля результат на 2, получаем Се+С„+С,+ ... +С"„= 2", если а четно, (8.9) Сз+С'„+С',+ ... +С"„= 2", если а нечетно. (8.10) Вычитая, получаем С,'+С'„+С',+ ... +С",= 2" ',.если п нечетно, (8.11) С„+С„+С',+ ... +С„" =2" ', если и четно.
(8.12) Зв Подставим теперь денумератор (8.5) так: Ы'„ (г) = (1 + г) д'„ , (г) = д„' ,(г) + гд"„ , (г). В силу (8.5) имеем сГ (г) = Х С" г». г О Подставим (8.14) в (8.13): в а-~ л ! с.", Сдг" = ~ Сп-1г'+ ~,'~ Сл-~г + . г=О Во второй сумме справа в (8.15) заменяем г + 1 на ьи В а-1 и ;~, С'„г' = ~ С„' ~г'+ ~ С"„:!г". г 0 (8.13) (8.14) (8.15) (8.16) Заметим, что С~=С~ ~=1 и С"„=С"„:~~=1. Сокращаем члены с соответствующими коэффициентами в (8.16): с-! л-! ~Саг = Х(Сл ~+Си ~)г. ,=! " ~! (8.17) Это тождество относительно г дает Си=Си-~+Се-~ т=! 2, и Разлагая (1+ г)", (1+ г)" и (1+ г)" согласно (8.14), получаем в левой и правой частях выражения (1 + г)" (1 + г) (1 + г) следующие коэффициенты при г'.
Г С"„= ~С~ С' ~'). С-е Для удобства будем пользоваться обозначением С", = ( — 1)'С,',.„, (8.21) (8.22) ввиду следующего свойства. По определению ч (а — 1) ... (а — т + !) С„= ы '~н р „р, „, „„,*„„р„„„„,в,,р. нонла». (8.23) 39 (8.18) Найденное соотношение хорошо известно из треугольника Паскаля. Запишем теперь (8.5) по-другому: с(„'(г) =с("„(г) Н' (г) ==(1+ г)" '"(1+ г), (8.19) Ничто не препятствует в этой формуле взять и отрицательным (С'„ не будет тогда числом сочетаний из и по г) и обозначить через С , величину г (- л) ( — л — 1) ...
(- л — г+ 1) С „— г! ( ()г л(л+ !) (л+ г 1) ( ()г (и+ г 1)! ( 1)»С» г) — ! (л !)! лег-!. (8.24) Посмотрим теперь, как нспользуются другие производящие функций для сочетаний с повторением. Пусть г(;,(г) =(1+ «+ г'+ )л=(! — г) ". (8.25) Осуществляя разложение (1 — г)' и заменяя затем т на — и, имеем 4(„(г) = ~~.", С' л ( — г)", » =э (8.26) т. е. С,-! г = и, и + ), П р и м ер. Даны два объекта А и В.
Сколько всего суще- ствует четырехэлементных сочетаний из этих двух объектов, в которых каждый объект встречается не менее одного раза? Это число равно г-л 4-» З 3! С, !=С,,=Сз= — = 3, 2!!! Выписываем эти сочетания: [АААВ[, [ААВВ[ и [АВВВ[. 40 г(л (г) = Х С~+»-!г". (8.27) »=0 Таким образом, способом, отличным от 5 3, мы опять получили число С'„.», » сочетаний с повторением (число неупорядоченных г-выборок с повторением). Попытаемся подсчитать число неупорядоченных г-выборок с повторением, в которых каждый объект встречается не менее одного раза, С этой целью рассмотрим такой денумератор: г(„(г) =(г+« + г' + ...) =гл(1 — г) "=гл ~! С',+, !г'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
