Упражнения

\ b. Сколькими способами можно рассадить семь че­ловек по кругу? Два расположения считаются одинаковыми, если каждый имеет тех же соседей (не обязательно с той же стороны).

c. Сколько перестановок я: [6]-v[6] удовлетворяют

условию я(1) ф 2?

d. Сколько перестановок множества [6] имеют в точности два цикла (т. е. найти с(6, 2))?

e. Сколько разбиений множества [6] имеют в точ­ности три блока (найти S(6,3))?

f. Имеется четверо мужчин и шесть женщин. Каж­дый мужчина женился на одной из женщин. Сколь­кими способами можно это сделать?

g. Десять человек разбились на пять групп, по два в каждой. Сколькими способами это можно сде­лать?

h. Сколько разложений числа 19 состоит лишь из чи­сел 2 и 3?

i. Сколькими разными способами можно упорядо­чить буквы в слове МИССИССИППИ, так чтобы четыре буквы «С» не стояли подряд.

j. Сколько существует последовательностей (аі, а2, •• ■ а\2), состоящих из четырех нулей и восьми единиц, таких что никакие два последовательных члена не являются нулями? к. В коробке лежат три синих носка, три красных носка и четыре цвета «шартрез»'). Восемь носков убрали, по одному за один раз. Сколькими спосо­бами можно это сделать?   (Носки одинакового цвета неразличимы.) 1. Сколько существует функций /: [5] -»-[5], удовлет­воряющих условию card f~l (п) ^ 2 для всех п є

2. Дайте комбинаторные   доказательства следующих тождеств   (х,у,п,а,Ь — неотрицательные целые):

Видимо, зеленый цвет. Шартрез —ныне исчезнувший ликер. — Прим.

*£(?)(?-,вН-

=(Т)ГГ>

т = гтпп (а, Ь).

Сколько существует на плоскости путей из точки (0,0) в точку (^I,л)eNXN, если каждый отрезок пути имеет вид (1,0) или (0, 1) (т. е. является шагом длины 1 в восточном или северном направлениях)? Дайте комбинаторное доказательство. Установите обобщение этого факта на высшие размерности. Эта задача является прототипом результатов обширного предмета, касающегося подсчета путей в решетках, а. Покажите, что

Пусть / (т, п) — число путей из точки (0, 0) в точку (т, и)еМХМ, где каждый шаг имеет вид (1,0), (0, 1) или (1, 1).

a. Покажите, что Ет>0Е„>0^ (т> п) хтуп = (I - х--у-ху)~\

b. Найдите    простое    явное    выражение для

р-ичные разложения целых чисел т, п. Покажите,

Ь. Используйте (а), чтобы определить, когда

 

Ь. Найдите

чтонечетно. Для каких п число ( m ) нечетно при

всех 0 ^ т ^ п?

c. Из п. (а) следует (это можно также легко пока­зать непосредственно), что ^ ^ ^ — ^^(modр). Дайте комбинаторное доказательство того, что на самом деле ^ ^ ^ = ^ ^ ^ (mod р2).

d. Если р ^ 5, покажите, что фактически

Есть ли здесь комбинаторное доказательство?

e. Дайте простое описание наибольшей степени про-

( п\

стого числа р, делящей I „   I ■ Пусть /п, neN. Дайте комбинаторное доказатель­ство тождества ((2)) = ((Г-i ))' , а. Пусть fli, а2,       а«еР. Покажите, что если разложить произведение

П(>-^)!' m

i + i

в многочлен Лорана от переменных х\, а:я (допускаются отрицательные показатели степени), то постоянный член есть мультиномиальный коэф-

сначала докажите тождество

 

/а, + а2+ ... + а„\ фициент I )• Указание:

\      аи       ап )

'=Е11("-^)"'. (34,

а затем умножьте на выражение (33). Ь. Положите п = 3 и выведите тождество

(-пк(а+ЬЛ(Ь + с}(с + а) = (а + Ь + с}

1    ; \а +к)\Ь +к)\с +к )    \ а, Ь, с )'с. Пусть д — добавочная переменная. Покажите, что если разложить произведение

х0-#0-«-?■)-О<35>

в многочлен Лорана от Х\.....х„ (коэффициенты

которого здесь — многочлены от д), то свободный член   есть    ^-мультиномиальный коэффициент / а! + а2 + ... + а„ \

\    а1( а2, ..., а„ /

й. Пусть АєР. Если произведение

разложено, как описано выше, покажите, что его постоянный член есть

е. Пусть   /(аі,а2,       ап)   обозначает постоянный член многочлена Лорана

П0Г' + <Гг+Ч ... +яЧ

1=1

где все йі е N. Покажите, что

£     Г>і> •••• <К' ••• <п =

<*,.....ап>0

(1+*,) ... (1+*„) £ т--*? ' . -

9. а. Найдите число разложений числа п>1, имею­щих четное число четных частей. Естественно, предпочтительно комбинаторное доказательство. Ь. Пусть е(п), о(п) и &(п) обозначают соответствен­но число разбиений п с четным числом четных ча­стей, с нечетным числом четных слагаемых и са­мосопряженных разбиений. Покажите, что е(п) —о(п) = Іг(п). Есть ли здесь комбинаторное дока­зательство?і. Число последовательностей (81,62.....6П) из ну­лей, единиц и двоек, таких, что ни за одним ну­лем непосредственно не следует единица. Зафиксируем і,лєР. Найдите простое выражение, использующее числа Фибоначчи, для числа последо­вательностей (Ті, 7*2, ..., Тп) подмножеств Ті мно­жества \k], таких, что 7) £ 7*2 Э 7"з Е 7*4 э ...

Пусть Sm(n, k) обозначает шело Стирлинга вто­рого рода. Из производящей функции £nS(n,k)xn= = хкІ(\ — х) (1 — 2х) ... (1 — kx) следует тождество

S (п, k) = £ Iа'-1 • 2а'-1 ... k"k~\ (36)

где сумма берется по всем разложениям ах + + #2 ... + ак = п. Дайте комбинаторное доказа­тельство формулы (36), аналогичное второму до­казательству предложения 1.3.4. То есть мы хо­тим сопоставить с каждым разбиением я множе­ства [п\ на k блоков разложение ai + а2 +... -f ak = п, такое, что этому разложению соответ­ствуют в точности Iа»-12a*—1 ... kCk~l разбиений я.

a. Пусть яДєР, положим / = \k/2 J . Пусть S(n, k) обозначает число Стирлинга второго рода. Из рас­смотрения производящей функции докажите, что

/ п — і — 1 \ Щп, k)^{  п_к  J (mod 2).'.

b. Дайте комбинаторное доказательство.

c. Сформулируйте и докажите аналогичный резуль­тат для чисел Стирлинга первого рода.

Пусть S(n,k) обозначает число Стирлинга второго рода. Определим Кп условием S (ti, Кп) ^ 5 (п, k) для всех k. Пусть г —решение уравнения (t + 2) Hog (/ + 2) _„ Г+1 —

Докажите, что достаточно больших п Кп'= ItJ или

Кп=У}+1.

В этом упражнении мы рассмотрим один метод обобщения разложения перестановок на непересе­кающиеся циклы с множеств на мультимножества. Мультщикл — это последовательность С = (і\,І2, ... .... і'*) положительных целых с возможными повто­рениями, причем последовательности (i\, h, ik) и   (і/, f/+i,       ik, i\,       t'y-i)   при   l</s^A> счи­таются эквивалентными. Введем переменные х\, х2, ■.. и определим вес С формулой w(C) = Xii ... ... х{/}. Мультиперестановка есть мультимножество мультициклов. Например, мультимножество {1,1,2} допускает следующие мультиперестановки (1) (1) (2), (H)(2), (12) (1), (112). Вес w(n) мультипереста­новки n = CiC2 ... С, задается равенством ш(я) = = w(Ci) ... w(Cj).

a. Покажите, что

С я

где С пробегает множество всех мультициклов на р, а я— все мультиперестановки на Р.

b. Пусть рк = хк 4- х,\ + ... + . Покажите, что

Па-гв^г'^По-лг1.

С А>1

с. Пусть fh(n) обозначает число мультиперестановок на множестве Щ общего размера п. Например, f2(3) = 14; данные мультиперестановки: (1)(1)(1), (1)(1)(2), (1)(2)(2), (2) (2) (2), (H)(1), (H)(2), (12) (1), (12)(2), (22) (1), (22) (2), (111), (112), (222). Выведите из (Ь) формулу

I /(")*" = Па-**')-1.

d. Найдите прямое комбинаторное доказательство пп.  (Ь) или (с).

20. а. Имеется я квадратных конвертов разных разме-

ров. Сколькими способами их можно упорядочить по включению? Например, если я = 3, существует шесть способов, а именно: пометим конверты бук­вами А, В, С (буквой А самый большой, а буквой С — наименьший), и пусть запись /е / означает, что конверт / содержится в конверте /. Вот эти шесть способов: (1), 0, (2) ВеЛ, (3) Се Л, (4) СеВ, (5) ВеЛ, Се=Л, (6) CeBei b. Сколько существует размещений, в которых суще­ствует в точности k конвертов, не содержащихся ни в каком другом? Не содержащих никакого кон­верта?

21. Пусть Рк(п) обозначает число разбиений я на k ча­стей. Зафиксируем (2^0. Покажите, что при я->­

-> + со последовательность р„-({п) становится в конце концов постоянной. Чему равна эта константа /(г)? Каково наименьшее значение я, для которого рп-г(п) = }(г)? Ваши аргументы должны быть ком­бинаторными.

22. Пусть Рк(п) определено, как и выше, и пусть дк(п) — число разбиений п на /г различных частей. Например, <7з(8) = 2; соответствующие разбиения есть 1 + 2+5 и 1+3 + 4. Дайте простое комбинаторное доказа­тельство того, что <7А     + ^ ^     = Ръ. (п)-

23. Из огромного множества тождеств с разбиениями мы приводим здесь несколько похожих формул, имею­щих особенно простые и элегантные комбинаторные доказательства.

'■|п<'-^--1(-^-Х.(-^-

ь. П^-^"'^

і >1

V xk'qk

k>0 (i-x)...(l~xk)(\-qx)...(l-<ixk) '

d. TT (1+^гг_1)= У 7-2W   *kf   .-ьтг-

24. а Логарифмическая производная степенного ряда

F(x) определяется равенством -j^-logF(x) = = F' (x)/F (x). Взяв логарифмическую производную степенного ряда Zn>0— IL3.1 (1 — х*)~\ выведите рекуррентное соотношение

п

п- p(n)=Yi о (о р (я—о.

1 = 1

где а (і)— сумма всех делителей числа і. b. Дайте комбинаторное доказательство.

25. а. Дано множество 51= Р. Пусть ps(«) (соответ-

ственно qs(n)) обозначает число разбиений п (со­ответственно число разбиений п на попарно раз­личные слагаемые), части которых лежат в мно­жестве 5. (Это специальные случаи функций р(9',п) следствия 1.4.5) Назовем пару (5,7), где 5, Т = Р, парой Эйлера, если ps{n) = qr(n) для всех heN. Покажите, что (S, Т) пара Эйлера тогда и только тогда, когда 27 (где 2Т — = {2t: i€= 7}) и 5 = Г — 27\ Ь. Каков смысл случая S={1}, 7 = {1, 2, 4, 8, ...}?

26. Пусть X— разбиение целого числа п. Обозначим fk(X) — число появлений k в разбиении X, a gk(X) — число различных частей X, встречающихся по мень­шей мере k раз. Например, f2(3, 2,2,2,1,1)= 3 и ^(3,2,2,2, 1, 1) = 2.

Покажите, что£ fk!(X) = ^£,ёк М> где ^ е Р фиксиро­вано и суммирование в обоих случаях ведется по всем разбиениям X фиксированного целого пеР.

27. а. Пусть пеР и f{n) обозначает  число подмно-

жеств Z/nZ (вычетов по модулю я), сумма эле­ментов которых равна 0 в Z/raZ. Например, /(4) = 4; соответствующие подмножества — 0, {О}, {1,3}, {0, 1,3}. Покажите, что

d\n'd нечетно

где ф обозначает функцию Эйлера из теории чи­сел ').

b. Если п нечетно, то легко показать, исполь­зуя (а), что f(n) равно числу ожерелий (с точ­ностью до циклического поворота) из п бусин, каждая из которых покрашена в черный или бе­лый цвета. Дайте комбинаторное доказательство. (Это просто сделать, если п — простое число.)

c. Обобщите. Исследуйте, например, сколько под­множеств 5 множества Z/nZ удовлетворяет усло­вию Yi{f=s р(0 —a(m°d«), где р — фиксиро­ванный полином и число aeZ/nZ фиксировано.

28. Пусть f(n,k) обозначает число последовательностей а\а2 ... ап положительных целых чисел,' таких, что первое появление i ^ 1 встречается раньше, чем пер­вое появление числа j+1 (l^i^&—1), и при

ф(п) есть число чисел, меньших п и взаимно простых с п.—Прим,этом максимальное встречающееся число есть /г (Предполагается, что каждое число 1, 2, к встре­чается по меньшей мере один раз.) Выразите ](п, &) через знакомые числа. Дайте комбинаторное доказа­тельство.

29. Дайте комбинаторное доказательство того, что число разбиений множества [п], в которых ни одна пара последовательных целых чисел не оказывается в од­ном блоке, есть число Белла В(п— 1).

30. а. Пусть 1к{п) обозначает число перестановок я е ®„,

имеющих к инверсий. Покажите из комбинаторных соображений, что для п^-к

Ы"+1) = Ы")+ /*-!("+!).

b. Выведите из (а), что при п~^к /*(") есть поли­ном от п степени & и что его старший коэффици­ент равен Например, ^ (и) = у (п + 1) (п — 2) при п ^ 2.

c. Пусть gk{tl)—многочлен, значения которого при п^к равны ]к(п). Найдите А/й'й(—п), т. е. вы­числите коэффициент а, в разложении

31. Пусть т(п) обозначает число рекордов, а /(я) (как обычно)—число инверсий перестановки я. Вычис­лите производящую функцию

яе=б„

32. а. Перестановка а.\ ... ап множества [п] называется

неразложимой, если п есть наименьшее положи­тельное целое среди всех /, для которых {аи аъ ...

а,} = {1,2, /}• Пусть Цп)— число  неразложимых перестановок

множества [п], и положим Р{х) = Х„> 0 п\ хп. По­кажите, что

Ь. Элемент а,- называется сильной неподвижной точ­кой перестановки а\ ... ап, если (!) а/ < < а, и (2) />/=*- а/ > а;. Пусть ^(п) — числоперестановок множества [л], не имеющих сильных неподвижных точек. Покажите, что

£ g(n)xn = F(x)(l+xF(x))~l.

Пусть Ап(х) — многочлен Эйлера. Дайте комбина­торное доказательство того, что-g Лп(2) равно числу

упорядоченных разбиений (т. е. разбиений, блоки которых линейно упорядочены) n-элементного мно­жества.

На какой последовательности с= (сь ..., сп) s N"

с условием Yi i-ci — п достигается максимум числа перестановок я е €>„, имеющих тип с?

ПуСТЬ   / — ПрОСТОе   ЧИСЛО.    ПОЛОЖИМ   П = О0-{-йх1-\-

+ aj? +...=0о, 0^аг^/ — 1, для всех i^0. Пусть ki (п) обозначает число последовательностей

с = (С[, с2.....c„)eN", £t'Ct = «, таких, что число

перестановок я е ©„ типа с не делится на /. Покажите, что

h (п) = р(п) = р (оо) П («i + 1).

где р(а0) — число разбиений а<>. В частности, число последовательностей с, для которых нечетное число перестановок яе®я имеют тип с, равно 26, причем L«/2J имеет Ь единиц в двоичном разложении.

a. Пусть F(x) = J^n>Qf(n)xn/n\. Покажите, что

e-*F(x) = j:n>0[b»f{0)]xn/nl

b. Найдите единственную функцию f: Р->С, удов­летворяющую условиям /(1)=1 и An/(l)=f(n) для всех пеР.

a. Пусть F (х) = V     / (п) хп. Покажите, что . !_ X

хКт+т) = Еп>01дп^0^"

b. Найдите единственные функции f, g:N-+C, удо­влетворяющие условиям А"/ (0) = g (л), А2"^ (0) = = f(n), A2«+'g(0) = 0, f(0)=l.с. Найдите единственные функции {, М-»-С, удо­влетворяющие условиям Д*7(1) = £(«), Д2"£(0) = =        №+18(0) = 0, /(0)=1.

38. Пусть А — абелева группа всех многочленов р: 2-*-С,  таких  что  йкр: для всех

обозначает 6-ю производную). Тогда А имеет

базис вида рЛ*) — сп ( д )> гс^М, где константа сп

зависит только от п. Найдите явный вид с„.

39. Пусть % — комплексное число (или переменная), по­ложим

У=1+ £ !(п)хп,   у*= I ё(п)хп.

Покажите, что

п

£(") = ТЕ [*(Я+1)-«]/(А)в(п-*), я>1.

Это дает гораздо более эффективный метод подсчета коэффициентов у%, нежели непосредственное исполь­зование формулы (5).

40. Пусть ^, }2, ■■• — последовательность комплексных чисел. Покажите, что существует единственная по­следовательность комплексных чисел а.\, а2> что

Р(х):=1 + £ 7„*'*=П(1-*'Гв'.

Найдите выражение для а1 в терминах 1п-ых. Каковы а£-е, когда ^ (л;) = 1 + х и Р (х) = ех,{1~х)?

41. а. Пусть ^<-1>(дс) обозначает обратный относительно

композиций к ! (х) = х-{-^п>2апхп ^С[[х]] эле­мент С [[*]], т. е. Г-»&(х)) = Гф-ь(х)) = х. Покажите, что ^ (—/ (—х)) = х тогда и только тогда, когда существует ряд #(*) = *+ £„>2й„-Л такой,

что      = «<-»> (-*(-*)).

b. Покажите, что если К—Л—х)) = х, то существует единственный элемент #(х), удовлетворяющий ус­ловию п. (а) вида #(*) = * +£га>1 йг^2".

c. Заметьте, что если ?(х) =^^1х • то / (—Д—-^))=д;. Покажите, что       (—      х)) = . * .   тогда и, V1 bn+\xn только тогда, когда е~х > ——.— имеет вид

d. Определите коэффициенты b2n единственного ряда g(x) = x-\- £n>! b2nx2n, удовлетворяющего условию

£<~,>(_g(_x)) = _£_

42. Зафиксируем l^.k^.n. Сколько последователь­ностей целых чисел 1 о, < < ... <ак^.п удовлетворяют условию а,- = i (mod 2) для всех г?

43. а. Дано а0 = а, ах = р\ о„+1 = о„ + о„_, при п>1.

Вычислите У = ^Е,п>0апхп.

b. Дано «0=1  и о„+,=(« + 1)о„ — (j})an-2 при п^О. Вычислите г/ = Yn>0anxn/nl.

c. Дано 00 = ^ = 1,  2an+i = 2]._o(")aia«-i при

Вычислите у — 1£jn>0anxn/n\.

с . Дано Оо=1 и 2о„+1 = 2_(    I г- jdfin-t ПРИ "^0-Вычислите

44. Найдите простые замкнутые выражения для коэф­фициентов степенных рядов (разложения берутся в окрестности х = 0):

л /7+7

b. Ksin-'l)2,

c. sin (/ sin-1 я),

d. cos (t sin-1 x).

45. Следующая цитата — из «Нравоучений» Плутарха (VIII. 9, 732): «Хризипп говорит, что число сложных предложений, которые можно составить всего из де­сяти простых предложений превосходит миллион (Гиппарх, однако, опроверг это, показав, что утвер­дительных сложных предложений Т. Хис в «Истории греческой математики-», т. 2, стр. 245, пишет, что «невозможно, кажется, получить хоть какую-нибудь из этих цифр». (Хис также заме­чает, что один из вариантов чтения —. I

вариантов^ и элементов {х + г + 2, х + / + 3, ..., х + + *'+"+ 1}-