Элементы комбинаторики. Ежов И.И., Скороход А.В., Ядренко М.И. М.: Наука, 1977 г. 80 с.
Оглавление
Предисловие
§ 1. Введение. Основной принцип комбинаторики
§ 2. Конечные множества и операции над ними
§ 3. Подмножества данного множества
§ 4. Упорядоченные множества. Перестановки и размещения
§ 5. Перестановки с повторениями
§ 6. Взаимно однозначное соответствие. Сочетания с повторениями
§ 7. Прямое произведение множеств
§ 8. Бином Ньютона и полиномиальная формула
§ 9. Метод рекуррентных соотношений
§ 10. Метод производящих функций
§ 11. Метод включения и исключения
§ 12. Метод траекторий
Ответы, указания, решения
Литература
Текст
                    И.Н.ЕЖОВ, ШКОРОХОД, NJilFEflKO
ЭЛЕМЕНТЫ
КОМБИНАТОРИКИ


И, И, ЕЖОВ, А. В. СКОРОХОД, М, И. ЯДРЕНКО ЭЛЕМЕНТЫ КОМБИНАТОРИКИ Перевод с украинского 3. Л. Кулик ИЗДАТЕЛЬСТВО «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ Москва 1 977
ОГЛАВЛЕНИЕ Предисловие * . 4 , , 4 § 1. Введение. Основной принцип комбинаторики 5 § 2. Конечные множества и операции над ними 9 § 3. Подмножества данного множества 15 § 4. Упорядоченные множества. Перестановки и размещения 22 § 5. Перестановки с повторениями . . . 26 § 6. Взаимно однозначное соответствие. Сочетания с повто- рениями 29 § 7. Прямое произведение множеств . „ . . ....... 33 § 8. Бином Ньютона и полиномиальная формула 35 § 9. Метод рекуррентных соотношений 45 § 10. Метод производящих функций , . 47 § 11. Метод включения и исключения. . . . . 5Э § 12. Метод траекторий 64 Ответы, указан и я, решения . . 75 Литература , . . '. . , . . . . 8Э
ПРЕДИСЛОВИЕ Комбинаторика — один из разделов дискретной математики, который приобрел важное значение в связи с использованием его в теории вероятностей, математической логике, теории чисел, вычислитель- ной технике, кибернетике. Между тем программа средней школы не уделяет должного внимания этой полезной и интересной математической дисциплине. Цель этой книжки — ознакомить учащихся с основ- ными понятиями комбинаторики и методами решения комбинаторных задач. При изучении комбинаторики мы считали целесо- образным систематически использовать понятия мно- жества и операции над множествами, поскольку боль- шинство задач комбинаторики можно сформулиро- вать как задачи теории конечных множеств. При решении комбинаторных задач следует особо отметить метод производящих функций и метод тра- екторий. Эти методы важны сами по себе, так как на- ходят широкое применение не только в комбинатори- ке, но и во многих разделах современной математики. В основу книги положены лекции, прочитанные авторами учащимся республиканской заочной физико- математической школы. Книга предназначена учащимся средних школ и студентам младших курсов университетов. Она может быть полезна и лицам, занимающимся комбинатор- ными расчетами. В настоящее издание внесены неко- торые исправления и добавлены новые задачи. Авторы искренне благодарят М. X. Клина и А. Ф. Лапко, внимательно прочитавших украинское издание книги и сделавших большое число полезных замечаний. Авторы
§ 1. ВВЕДЕНИЕ. ОСНОВНОЙ ПРИНЦИП КОМБИНАТОРИКИ Человеку часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или чи- сло всех возможных способов осуществления некото- рого действия. Сколькими способами можно располо- жить 50 человек в очереди в кассу кино? Сколькими способами могут быть распределены золотая, сере- бряная и бронзовая медали на чемпионате мира по футболу? Задачи такого типа называются комбина- торными. С комбинаторными вычислениями приходится иметь дела представителям многих специальностей: ученому-химику при рассмотрении различных воз- можных типов связи атомов в молекулах, биологу чпри изучении различных возможных последователь- ностей чередования ахминокислот в белковых соедине- ниях, конструктору вычислительных машин, агроному, рассматривающему различные_зозможные способы посевов на нескольких участках, диспетчеру при со- ставлении графика движения. Комбинаторные сооб- ражения лежат в основе решения многих задач теории вероятностей — важного раздела современной мате- матики, посвященного изучению случайных явлений. Усиленный интерес к комбинаторике в последнее вре- мя обусловлен бурным развитием кибернетики, вычи- слительной техники. Установим сначала очень важное правило, кото- рое часто применяется при комбинаторных расчетах. Начнем с такой задачи. Задача 1. Из Киева до Чернигова можно до- браться пароходом, поездом, автобусом, самолетом; из Чернигова до Новгорода-Северского — пароходом и автобусом. Сколькими способами можно осуществить 5
путешествие по маршруту Киев — Чернигов — Новго- род-Северский? Решение. Очевидно, число разных путей из Кие- ва до Новгорода-Северского равно 4X2 = 8, так как, выбрав один из четырех возможных способов путе- шествия от Киева до Чернигова, имеем два возмож- ных способа путешествия от Чернигова до Новгорода- Северского (рис. 1). Рис 1. Соображения, которые были приведены при реше- нии задачи 1, доказывают справедливость следую- щего простого утверждения, которое будем называть основным правилом комбинаторики. Если некоторый выбор А можно осуществить пг различными способами, а для каждого из этих спо- собов некоторый другой выбор В можно осуществить п способами, то выбор А и В (в указанном порядке) можно осуществить пг X п способами. Иначе говоря, если некоторое действие (например, выбор пути от Киева до Чернигова) можно осущест- вить пг различными способами, после чего другое действие (выбор пути от Чернигова до Новгорода-Се- верского) можно осуществить п способами, то два действия вместе (выбор пути от Киева до Чернигова, выбор пути от Чернигова до Новгорода-Северского) можно осуществить пг X я способами. Задача 2. В розыгрыше первенства страны по футболу принимает участие 16 команд. Сколькими способами могут быть распределены золотая и сере- бряная медали? Решение. Золотую медаль может получить одна из 16 команд. После того как определен владелец зо- лотой медали, серебряную медаль может иметь одна из 15 команд. Следовательно, общее число способов, которыми могут быть распределены золотая и сере- бряная медали, равно 16 X 15 ==240, G
Сформулируем теперь основное- пра-вило комбина- торики (правило умножения) в общем виде. Пусть требуется выполнить одно за другим k дей- ствий. Если первое действие можно выполнить П\ спо- собами, второе действие — п2 способами, третье дей- ствие — пъ способами и так до k-го действия, которое можно выполнить nk способами, то все k действий вместе могут быть выполнены п{Хп2Хп3Х ... Xnk способами. Задача 3. Сколько четырехзначных чисел мож- но составить из цифр 0, 1, 2, 3, 4, 5, если: а) ни одна из цифр не повторяется более одного раза; б) цифры могут повторяться; в) числа должны быть нечетными (цифры могут повторяться)? т Решение, а) Первой цифрой числа может быть одна из 5 цифр 1, 2, 3, 4, 5 (0 не может быть первой цифрой, потому что в таком случае число не четырех- значное); если первая цифра выбрана, то вторая мо- жет быть выбрана 5 способами, третья — 4 способами, четвертая—3 способами. Согласно правилу умноже- ния общее число способов равно 5X5X4X3 = 300., б) Первой цифрой может быть одна из цифр 1, 2, 3, 4, 5 (5 возможностей), для каждой из следующих цифр имеем 6 возможностей (0, 1, 2, 3, 4, 5). Следо- вательно, число искомых чисел равно 5X6X6X6 = _5Х63= 1080. в) Первой цифрой может быть одна из цифр 1, 2, 3, 4, 5, а последней — одна' из цифр 1, 3, 5 (числа дол- жны быть нечетными). Следовательно, общее количе- ство чисел равно 5X6X6X3 = 540. Для того чтобы хорошо усвоить основное правило комбинаторики, советуем обязательно решить предло- женные ниже упражнения. УПРАЖНЕНИЯ 1. На вершину горы ведет 7 дорог. Сколькими способами ту- рист может подняться на гору и спуститься с нее? Дайте ответ на тот жег самый вопрос, если подъем и спуск осуществляются различными путями. 7
2. Сколько трехзначных чисел можно составить из цифр !, 2, 3, 4, 5? 3. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5, если каждую из этих цифр можно использовать не более одного раза? 4. Сколькими способами 7 человек могут разместиться в оче- реди в кассу? 5. В классе изучают 10 предметов. В понедельник 6 уроков, причем все уроки разные. Сколькими способами можно составить расписание на понедельник? 6. Сколько имеется пятизначных чисел, которые делятся на 5? 7. На одной из боковых сторон треугольника взято п точек, на другой — т точек. Каждая из вершин при основании треуголь- ника соединена прямыми с точками, взятыми на противополож- ной стороне, а) Сколько точек пересечения этих прямых обра- зуется внутри треугольника? б) На сколько частей делят тре- угольник эти прямые? 8. Сколько есть двузначных чисел, у которых обе цифры четные? 9. Сколько есть пятизначных чисел, у которых все цифры нечетные? 10. Сколько четырехзначных чисел можно написать с по- мощью цифр 0, 1, 2, 3, 4, 5? Найти сумму всех этих чисел. 11. Сколько есть трехзначных чисел, которые записываются с помощью цифр 0, 1, 2, 3, 4, 5 и делятся на 3? 12. Сколько есть пятизначных чисел, которые одинаково чи- таются слева направо и справа налево (например, таких, как 67876, 17071)? 13. 5 мальчиков и 5 девочек садятся в ряд на 10 располо- женных подряд стульев, причем мальчики садятся на места с не- четными номерами, а девочки — на места с четными номерами. Сколькими способами это можно сделать? 14. Сколько разных слов можно составить перестановкой букв в слове «математика»? 15. Автомобильные номера составляются из одной, двух или трех букв и четырех цифр. Найти число таких номеров, исполь- зуя 32 буквы русского алфавита. 16. В селении живут 1500 жителей. Доказать, что по крайней мере двое из них имеют одинаковые инициалы. 17. а) Сколько разных делителей имеет число З3 X 54? б) Пусть pi, ..., рп — различные простые числа. Сколько делите- лей имеет число а1 ч^ чх ап т=р{хХ ... X Рпп, где oti, ..., ап — некоторые натуральные числа? 18. От А до В 999 км. Вдоль дороги стоят столбы, на кото- рых указаны расстояния до А и до В 0 999 |; | 1,998 |; | 2,997 | ; ...; [999,0 Сколько среди них таких, на которых есть только 2 различные цифры? 8
19. Пассажир оставил вещи в автоматической камере хране- ния, а когда пришел получать вещи, выяснилось, что он забыл номер. Он только помнит, что в номере были числа 23 и 37, Что* бы открыть камеру, нужно правильно набрать пятизначный но- мер. Какое наибольшее количество номеров нужно перебрать, чтобы открыть камеру? 20. В прямоугольной таблице из т строк и п столбцов запи- саны числа +1 и —1 так, что произведение чисел в каждой строке и каждом столбце равно 1. Сколькими способами это можно сделать? § 2. КОНЕЧНЫЕ МНОЖЕСТВА И ОПЕРАЦИИ НАД НИМИ Всякая совокупность элементов произвольного рода образует множество. Можно рассматривать мно- жество всех действительных чисел, множество нату- ральных чисел, множество всех учащихся данной школы, множество парт в данном классе, множество всех жителей данного города и т. д. Множество счи- тается определенным, если указаны все его элементы. Эти элементы могут быть указаны с помощью некото- рого общего признака или просто с помощью некото- рого списка, где обозначены все элементы. Последний способ возможен лишь в том случае, если множество имеет конечное число элементов; такие множества будем называть конечными. Комбинаторика есть тео- рия конечных множеств. Поэтому далее мы будем иметь дело лишь с конечными множествами. Основной характеристикой конечного множества является число его элементов. Теория конечных множеств изучает правила: как, зная количество элементов некоторых множеств, вы* числить количество элементов других множеств, кото- рые составлены из первых с помощью некоторых опе- раций. Операции над множествами мы введем не- много позднее. Введем основные обозначения, которыми будем пользоваться в дальнейшем. Множества будем обо- значать большими латинскими буквами, их элемен- ты— малыми: а&А: а есть элемент А, или а принад- лежит А; а ША: а не есть элемент Л, или а не принад- лежит Л, Количество элементов множества будем обозначать N(A)m 2.1. Операции над множествами. Два множества равны между собой§ если элементы первого являются 9
элементами второго и, наоборот, элементы второго являются элементами первого. Если Л и В—два множества, то множество С, ко- торому принадлежат все те и только те элементы, ко- торые входят либо в Л, либо в В, называется суммой или объединением множеств Л и В и обозначается С = A U В. Эта операция «сложения» множеств удовлетворяет коммутативному и ассоциативному закону: А[)В=В[]А, A[)(B\JC) = (AUB)[}C. (1) Первое из этих равенств вытекает из определения суммы. Второе есть следствие того, что и A U (В U С) и (A U В) U С есть совокупность элементов, входящих хотя бы в одно из множеств Л, либо В, либо С. По- этому можно рассматривать сумму любого числа мно- жеств А\ U Л2 U ... Ui4n, это будет множество, в ко- торое входят элементы каждого из множеств Ль Л2, ..., Ап и только они (общие элементы счи- таются только по одному разу). Однако это «сложение» отличается от обычного сложения. Чтобы пояснить это, рассмотрим числовые множества. Если х\, ..., хп — некоторые числа, то че- рез {лгь ..., хп} обозначим множество, которое со- стоит из элементов хь ..., хп. Предположим, что даны два множества {1, 2, 3} и {2, 3, 4}. Тогда {1, 2, 3} U {2, 3, 4} = {1, 2, 3, 4}. Если множества Л и В имеют общие элементы, то каждый из этих эле- ментов входит в Л UB только один раз. Итак, число элементов в сумме множеств не обязательно равно сумме чисел элементов первого и второго множеств, а может быть меньше ее. В частности, сложение мно- жеств приводит к такой необычной для чисел фор- муле: лил = л, лили ... ил = л. Множество С, которому принадлежат те и только те элементы, которые являются общими для множеств А я В (элементы, которые входят в оба эти множе- ства), называется пересечением множеств Л и В и обозначается С = Л П В. Например, {1,2, 3} П (2, 3,4} = {2,3}. ю
Если Ль ..., Ап — некоторые множества, то А\{\ ... ПЛП является множеством, состоящим из элементов, которые входят в каждое из множеств Ль ..., Ап (являются общими для этих множеств). Опять-таки пересечение множеств удовлетворяет ком- мутативному и ассоциативному законам: ЛПВ=ВЛЛ, ЛП(ВПС)=(ЛПВ)ПС. (2) Отметим, что Л П Л = Л, и потому Л П Л П ... пл = л. Покажем, что операции объединения и пересече- ния множеств удовлетворяют также дистрибутивному закону: ЛП(ВиС) = (ЛПВ)и(ЛГ)С). (3) Действительно, множество Л Г) (В U С) содержит элементы, которые входят в множество Лив множе- ство В U С, т. е. принадлежат Л и либо множеству В, либо множеству С. Тогда они принадлежат либо Л и В, либо Л и С, т. е. либо Л Л В, либо Л П С. Каждый элемент Л П (В U С) принадлежит множеству (Л Г)В) U U (Л Г) С). Наоборот, элементы (Л П В) U (Л П С) при- надлежат либо Л П В, либо Л П С, т. е. принадлежат Л и либо В, либо С, т.е. Л Г) (В U С). Равенство (3) до- казано. Примем во внимание то, что множество Л П В мо- жет быть неопределенным, если Л и В не имеют об- щих элементов. Чтобы избежать этого, будем рассма- тривать еще пустое множество 0, не содержащее ни одного элемента. Тогда будем считать, что ЛПВ = 0, если Л и В не имеют общих элементов. Пустое мно- жество играет роль нуля в операциях над множе- ствами: Ли0<=Л, ЛП0 = 0. Наглядно операции над множествами можно ил- люстрировать, изображая множества в виде кругов (иногда их называют кругами Эйлера) либо других фигур на плоскости (рис. 2). 2.2. Нахождение числа элементов суммы множеств. Будем обозначать через N(A) количество элементов множества Л. 11
Основная формула, которой пользуются при на- хождении числа элементов суммы двух множеств, та- кова; N {A[jB) = N(A) + N (В)- N (АПВ). (4) Действительно, N(A)-\-N(B) есть число, которое мы получим, перечислив все элементы множества Л, а за- тем— все элементы множества В. Но в этом случае В подмножество А Сумма множеств Пересечение Я и В множеств ЛиВ Рис. 2. общие элементы (их число N(AJ)B)) будут перечне* лены дважды, т. е. N(Ay+N(B) = N(A[}B) + N(A(]B). Отсюда и следует равенство (4). С помощью фор- мулы (4) можем получить формулу для числа эле- ментов суммы любого числа множеств. Например, для трех множеств имеем N(AUB{JC) = N{A{j(B[jC)}^ = N(A) + N(B[)C)-N{(A(}B){}(AriC)} = = N (Л) + N {В) + N (С) - N {В ПС) — " -{N(A()B) + N{AnC)-N((A()B){){Af)C))}=* = N {А) + N {В) + N {С) - N {А(} В) - N (А()С) -~ -N(B()C) + N(A(}B(}C). Задача 1. Каждый ученик класса — либо девоч- ка, либо блондин, либо любит математику. В классе 20 девочек, из них 12 блондинок, и одна блондинка любит математику. Всего в классе 24 ученика-блон- дина, математику из них любят 12, а всего учеников (мальчиков и девочек), которые любят математику, 12
Щ из них 6 девочек. Сколько учеников в данном классе? Решение- Если А — множество девочек, В — блондинов, С — учеников, которые любят математику, то N (А 1) В V С) — искомое число. А П В — множество блондинок, Л ПС — множество девочек, которые лю- бят математику, В [\ С — множество всех блондинов ;(мальчиков и девочек), которые любят математику, А П В П С — множество блондинок, которые любят математику. Тогда N{Al)B[)C) = N{A) + N(B) + N(C)-N{A()B)- -N{A(]C)-N(B(]C) + N{A(]B(]C)^ = 20 + 24 + 17 - (12 + 6 + 12) + 1 = 32. Установим теперь общую формулу для нахожде- ния числа элементов суммы нескольких множеств. Теорема. Если Аи ..., Ап — некоторые множе- ства, то N(A{[] ... [}An) = N(Al)+ ... + N{An)~ ~{N(Al()A2) + N{Al()A3)+ ... + N(Arl-lf\An)} + + {N(AinA2nA3) + N(Al[]A2i]A4)+ ... ... +N(An-2(]An-{(}An)}- ... ... +(-i)*-[N(Ai[) ... П4). (5) Правая часть равенства (5) является суммой п слагаемых, k-e по порядку слагаемое имеет вид (_l)*-iSjk(Alf ..., А*), где Sh(Аи *V., Ап) есть сумма чисел N(At[ Г) ... П Alh) по всем возможным пересечениям ровно k разных множеств из множеств Аь ..., Ап. Доказательство. Из формулы (4) следует, что формула (5) справедлива для двух множеств. Предположим, что она справедлива для п— 1 множе- ства, и покажем, что она выполняется и для п мно- жеств (т.е. проведем доказательство по индукции). 13
По предположению NiAU ... [jAn) = N(Al) + N(A2{J ... UA,)- -^{(Л.П^и ... и(л,лл,)} = = ЛГ(Л1) + {51(4>, .... Л)-52(Л2, ..., Л,)+ ... ... +(-ir2Sn.1042) ..., Д,)}- -{Sl(Alf\A2 Alr\An)-S2(Al[)A2,...,Aif]An) + ... ... +(-ir2s(I.l(yi1n4 .... АЛА)} Для того чтобы отсюда получить формулу (5), остается принять во внимание, что iV(A) + 5,(A, ..., Л„) = 51(Л1) .... Ап), S2(A2t ..., Ап) + Sx (Л, П Л2, ..., А1[\Ап) = — «S2 (ль ..., Л„), 5ПЛ, ...,. AJ + Sjfc-jMnA*, ..., АГШ = = S*(A> ...., At), Sn^l(Al(]A2i ..., АПА) = 5«(А> А2, ..., А.). Теорема доказана. УПРАЖНЕНИЯ 1. Разностью множеств Л и В (обозначается Л — В) назы- вается множество тех элементов Л, которые не принадлежат В. Доказать соотношения (А{)В)-В = А-В, Af)(B[JC) = A-(A-B)(}(A-C), (Л-£)ПС = (ЛПС)-(£ПС), лпвле = л-(л-(впс)), (ЛПС)~В = (ЛПС)-(ВПС), (А-В)и(Л-С) = Л-(ВПС)- 2. Доказать, что А — В = 0 тогда и только тогда, когда Л П В = А 3. Пусть Л — множество корней уравнения х2 — Зх + 2 = О, а5 = {0, 2}. Найти А О В, А I) В, А — В, В — А. 4. Пусть Л — множество значений функции [ 1 при х > О, // = sign х= \ 0 при х = О, I —1 при я < О, 14
а В — множество корней уравнения х(х — 1) (х + 2) = 0. Найти А Г) В, A UB, А— В, В — А. 5. На экскурсии были семиклассники и восьмиклассники. Все они были либо с комсомольскими значками, либо в пионерских галстуках. Мальчиков было 16, а комсомольцев 24. Пионерок было ровно столько, сколько мальчиков-комсомольцев. Сколько учащихся было на экскурсии? 6. В классе 35 учащихся. Из них 20 посещают математиче- ский кружок, 11—физический, 10 учащихся не посещают ни од- ного из этих кружков. Сколько учеников посещают и математи- ческий, и физический кружок? Сколько учащихся посещают толь- ко математический кружок? 7. Из 100 студентов английский язык знают 28 студентов, не- мецкий— 30, французский — 42, английский и немецкий — 8, анг- лийский и французский—10, немецкий и французский — 5, все три языка знают 3 студента. Сколько студентов не знают ни одного из трех языков? § 3. ПОДМНОЖЕСТВА ДАННОГО МНОЖЕСТВА 3.1. Количество fe-элементных подмножеств дан- ного множества. Если каждый элемент множества В принадлежит множеству Л, то В называется подмно- жеством множества А, Это обозначается так: A id В, либо В с А (читается: А содержит В, В входит в А)* Будем считать, что пустое множество является под- множеством любого множества: 0 а А. Для всякого множества А имеет место соотношение AczA. Если A cz В и ВсД, то А = Вщ Подмножество В множе- ства А называется собственным, если В Ф А и В ф 0, Если задано некоторое множество Л, то можно рассматривать новое множество М(А)—множество всех его подмножеств. Через Mh(A) будем обозначать множество всех подмножеств Л, которые имеют k эле- ментов: В czMk(A), если В аМ(А) и N(B) = k. Пример. Пусть Л = {а, 6, с). Тогда М(А) = {{а}, {&}, {с}, {а, Ь), {а, с), {Ь, с), {а, Ь, с}, 0}; М2(Л) = {{а, Ь},{а,с), {Ь, с}}. Убеждаемся, что N (М (А)) = 8 = 23, N {М2 (А)) = 3. Естественно задать вопрос: сколько разных ^-эле- ментных подмножеств имеет множество из п эле- ментов? Будем обозначать символом п\ (читается п-факто« риал) произведение всех натуральных чисел от 1 до 15
п включительно: п\ = 1 -2 ... п. Удобно считать (да- лее мы убедимся, по каким именно причинам), что 0!= 1. Теорема. Число всех k-элементных подмножеств множества из п элементов равно *<ц<^-'"~'.':;-.?:г>+"-тп£1|г- с) Доказательство. Обозначим N (Mk (А)) = С*. Чтобы построить ^-элементное подмножество множе- ства Л, нужно к (/г — 1)-элементному подмножеству присоединить один из п — £+1 элементов, которые не входят в это подмножество. Поскольку (k— ^-эле- ментных подмножеств имеется Скп~х и каждое из них можно сделать ^-элементным п — k + 1 способами, то таким образом мы получим {п — k + \)С\~{ подмно- жеств. Но не все они будут разными, так как каждое /г-элементное множество можно так построить k спо- собами: присоединением каждого из k его элементов. Поэтому вычисленное нами число в k раз больше, чем число Сп ^-элементных подмножеств. Следовательно, kCkn = {n-k+l)Ckn-\, Отсюда найдем * rk п — k+ 1 rk-\ (ft — k+ 1) (ft — k + 2)rfc-2 ^n — k ^n — k(k-\) ~Un — "•• _ (ft-fe + l)...(ft-l) r\ ••• ~ &(/e-l)...2 rtV Но число одноэлементных подмножеств множества А равно количеству элементов, т. е. п. Подставив вместо Схп число п, получим (1). Произвольное fe-элементное подмножество я-эле- ментного множества называется сочетанием из п элементов по k. Порядок элементов в подмножестве не имеет значения. Иногда вместо слова «сочетание» употребляется термин — комбинация из п элементов по k. Мы установили, что число сочетаний из п элемен- тов по k равно С**"~" k\(n-k)\ • 16
Задача 1. Сколькими способами читатель мо- жет выбрать 3 книжки из 5? Решение. Искомое число способов равно числу трехэлементных подмножеств множества из 5 эле- ментов; Задача 2. Сколькими способами из 7 человек можно выбрать комиссию, состоящую из 3 человек? Решение. Чтобы рассмотреть все возможные ко- миссии, нужно рассмотреть все возможные 3-элемент- ные подмножества множества, состоящего из 7 чело- век. Искомое число способов равно Задача 3. В турнире принимали участие п шах- матистов, и каждые 2 шахматиста встретились 1 раз. Сколько партий было сыграно в турнире? Решение. Партий было сыграно столько, сколь- ко можно выделить 2-элементных подмножеств в мно- жестве из п элементов, т. е. Г2 п(п — 1) Задача 4. В скольких точках пересекаются диа- гонали выпуклого n-угольника, если никакие 3 из них не пересекаются в одной точке? Решение. Каждой точке пересечения двух диа- гоналей соответствует 4 вершины я-угольника, а каж- дым 4 вершинам я-угольника соответствует 1 точка пересечения (точка пересечения диагоналей четырех- угольника с вершинами в данных 4 точках)щ Поэтому число всех точек пересечения равно числу способов» которыми среди п вершин можно выбрать 4 вершиньц га _ п (п— 1) (/г — 2>(/г — 3) _ п(п— 1) (/г — 2) (/г — 3) Ln~ Ь2.3-4 ~~ 24 Следующая задача дает интересную геометриче- скую интерпретацию для чисел С*. Задача 5. Рассмотрим прямоугольную сетку квадратов размерами тХп («шахматный город», 17
1 (о} л) /7 \ (rrijri) -—1,. О т Рис. 3. (т;о) состоящий из га X п прямоугольных кварталов, разде- ленных п — 1 «горизонтальными» и га — 1 «вертикаль- ными» улицами (рис. 3). Каково число различных кратчайших путей на этой сетке, ведущих из левого нижнего угла (точки (0;0)) в правый верхний угол (точку (га; п))? Решение. Каждый кратчайший путь из точки (0; 0) в точку (га; п) состо- ит из m + п отрезков, при- чем среди них есть га гори- зонтальных и п вертикаль- ных отрезков. Разные пути отличаются лишь порядком чередования горизонталь- ных и вертикальных отрез- ков. Поэтому общее число путей равно числу спо- собов, которыми из га + n отрезков можно выбрать п вертикальных отрезков, т. е. С%,+п. Можно было бы рассматривать число способов выбора не п вертикальных, а га горизонтальных от- резков, и мы получили бы тогда ответ С^+п* Итак, мы установили геометрически равенство Сты — Ст+п* в справедливости которого нетрудно убедиться и не- посредственно, выражая число комбинаций через фак- ториалы. Итак/ число кратчайших путей из точки (0; 0) в точку (га; п) равно С%+п = Спт+п. Теорема. Имеет место равенство с* = с*-, + с*:1. (2) Легко убедиться в справедливости равенства (2), используя формулу Скп=- п\ k\(n — k)\ Советуем читателю сделать это самостоятельно. Приведем еще два других доказательства. Доказательство 1. Рассмотрим некоторый элемент а множества Л, состоящего из п элементов, и все /^-элементные подмножества множества А (чис- 18
ло таких подмножеств равно Сп). Все ^-элементные подмножества множества А разделим на 2 группы: подмножества, в состав которых входит а, и подмно- жества, в состав которых а не входит. Число подмно- жеств в первой группе равно Cn-lt так как каждое такое подмножество получается присоединением к а некоторого (k — 1) -элементного подмножества мно- жества А. Число подмножеств во второй группе равно ^п-и так как каждое такое подмножество есть k-эле- ментное подмножество множества А — {а}. Следова- тельно, Доказательство 2. Число кратчайших путей из точки О(0; 0) в точку A(k\ n — k) равноСкл-(п-к)-= = Сп (рис. 4). Все такие пути можно разделить на 2 ^ / h 3 S ( A(k >*г 4t*. •k) л Рис. 4. группы: пути, проходящие через точку Ai(k—1; n—k) (число их равно С^-11)+(я-й) = С*-1)э и пути, проходя- щие через точку A2(k; n — k—А) (число их равно >*+(»-*■ -D = Crt-i). Следовательно, Cfe s>k — 1 i^ >ofe /г — W-1 "Г W- Задача 6. Доказать тождество a=(c°)2+(ci)2+...+(c)2. (3) Решение. Число кратчайших путей из точки О(0;0) в точку А(п;п) равно С"п- Каждый такой путь проходит через одну и только одну из точек 19
в A 0 JO Рис. 5. X Ak(k\ n — k), лежащих на диагонали BD (рис. 5)* Число путей из точки О в точку Ah равноCk+(n-k) — Cn, а из точки Ah в точку А равно Cn-k+k^Cn) поэтому число путей из О в Л, проходящих через Ak, равно Сп'Сп = (СпУ (правило умножения!). Прибавив ко- личество путей, проходя* щих через каждую из точек Ak (fe = 0, 1, ..., п), полу- чим общее количество пу- тей из О в Л, т. е. С£п. Это соображение и доказывает равенство (3). 3.2. Количество подмно- жеств данного множества. Выясним теперь, сколько всего подмножеств имеет множество Л, состоящее из п элементов (пустое мно- жество также является подмножеством Л). Теорема. Число всех подмножеств множества из п элементов равно 2П. Приведем два различных доказательства. Доказательство 1. Пусть Ма — множество всех подмножеств множества Л, которые содержат элемент а. Очевидно, что каждое такое подмножество полностью определено, если указаны все его осталь- ные (кроме а) элементы. Поэтому таких подмножеств будет столько, сколько будет подмножеств в множе- стве А' = А — {а}, которое содержит все элементы Л, кроме а. Это множество имеет п —- 1 элементов. По- этому, если qn — число подмножеств множества из п элементов, то N(Ma) = qn-\. Если Ма— множество всех подмножеств множе- ства Л, не содержащих а, то N(Ma) также будет рав- но qn-u Поскольку М(А) = Ма + Ма1 то N(M(A)) = = 2qn-\. Отсюда находим qn = 2qn-\. Таким образом, qn = 2qn-i = 22qn-2 = ... = 2n~lqi. Множество, со- стоящее из 1 элемента, имеет 2 подмножества (все множество и пустое множество). Поэтому q\ = 2. Сле- довательно, qn = 2п. Доказательство 2. Перенумеруем элементы множества Л и для каждого подмножества множе- ства Л построим последовательность длины п из ну- 20
лей и единиц по следующему правилу: на /г-м месте пишем 1, если элемент с номером k входит в подмно- жество, и 0, если элемент с номером k не входит в подмножество. Итак, каждому подмножеству соответ- ствует своя последовательность нулей и единиц. На- пример, пустому множеству соответствует последова- тельность из одних нулей. Число всех возможных последовательностей длины п, составленных из ну- лей и единиц, равно, согласно правилу умножения, 2*2 ... 2 = 2". Следовательно, и число всех подмно- п раз жеств множества А равно 2П. Как было указано выше, удобно считать 0! = 1. При этом предположении формула rk — п! С/г — k\(n — k)\ остается в силе и при k = п и при k = 0. Следствие. Имеет место равенство tckn = 2n. В самом деле, поскольку С\ — число ^-элемент- ных подмножеств множества из п элементов, то сум- ма в левой части есть число всех подмножеств. УПРАЖНЕНИЯ 1. Сколькими способами из 30 учащихся можно выбрать де- легацию, состоящую из 3 учащихся? 2. В комнате п лампочек. Сколько всего разных способов освещения комнаты, при которых горит ровно k лампочек? Сколь- ко всего может быть различных способов освещения комнаты? 3. Дано п точек, никакие 3 из которых не лежат на одной прямой. Сколько прямых можно провести, соединяя точки по- парно? 4. На плоскости проведено п прямых так, что никакие 2 из них не параллельны и никакие 3 не пересекаются в одной точке, а) Найти количество точек пересечения этих прямых; б) Сколько треугольников образуют эти прямые? в) На сколько частей делят плоскость эти прямые? г) Сколько среди них ограниченных ча- стей и сколько неограниченных? 5. Сколько имеется четырехзначных чисел, у которых каждая следующая цифра больше предыдущей? 6. Сколько имеется четырехзначных чисел, у которых каждая следующая цифра меньше предыдущей? 21
7. Международная комиссия состоит из 9 человек. Материалы комиссии хранятся в сейфе. Сколько замков должен иметь сейф, сколько ключей для них нужно изготовить и как их разделить между членами комиссии, чтобы доступ к сейфу был возможен тогда и только тогда, когда соберутся не менее 6 членов комис- сии? Рассмотреть задачу также в том случае, когда комиссия со- стоит из п человек, а сейф можно открыть при наличии т членов комиссии. 8. Имеется р белых и q черных шаров. Сколькими способами можно выложить в ряд все шары так, чтобы никакие 2 черных шара не лежали рядом? 9. В выпуклом n-угольнике проведены все диагонали. Извест- но, что никакие 3 из них не пересекаются в одной точке. На сколько частей разделится при этом многоугольник? § 4. УПОРЯДОЧЕННЫЕ МНОЖЕСТВА. ПЕРЕСТАНОВКИ И РАЗМЕЩЕНИЯ 4.1. Перестановки данного множества. Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое число (номер элемента) от 1 до /г, где п — число эле- ментов множества, так что различным элементам со- ответствуют различные числа. Всякое "конечное мно- жество можно сделать упорядоченным, если, напри- мер, переписать все элементы множества в некоторый список (а, Ь, с, ...), а затем поставить в соответствие каждому элементу номер места, на котором он стоит в списке. Будем обозначать упорядоченное множе- ство, которое получено из множества Л, через А. Оче- видно, что каждое множество, содержащее более од- ного элемента, можно упорядочить не единственным способом. Упорядоченные множества считаются раз- личными, если они отличаются либо своими элемен- тами, либо их порядком. Различные упорядоченные множества, которые отличаются лишь порядком эле- ментов (т. е. могут быть получены из того же самого множества), называются перестановками этого мно- жества. Пример. Перестановки множества А = {а, &, с} из 3 элементов имеют вид (а, 6, с), (а, с, Ь), (6, а, с), (Ь, с, а), {с, а, Ь), {с, Ь, а). 22
Найдем число различных способов, которыми мо- жет быть упорядочено данное множество, т. е. чис- ло перестановок множества А. Пусть множество А имеет п элементов. Обозначим число его перестановок через Рп. Теорема. Рп=П\. Доказательство 1. Выберем некоторый эле- мент а из множества А. Рассмотрим все перестановки, в которых а имеет номер 1. Число таких перестановок будет равно числу перестановок из п — 1 элементов множества'Л, которые остаются после исключения из множества элемента а. Поэтому число перестановок, для которых а имеет номер 1, равно Рп-\- Обозначим через М множество всех перестановок множества Л, а через Ма — множество перестановок, в которых а имеет номер 1. Тогда M = Ma[)Mb{J ... l)Mf, где а, Ь, ..., / — все элементы множества А. Посколь- ку никакие 2 множества из множеств Ма, Мъ, ..., Mf не имеют общих элементов (напомним, что элементы этих множеств — перестановки, в различных множе- ствах на первом месте стоят различные элементы, следовательно, и соответствующие перестановки бу- дут различными), то N{M)=~N(Ma) + N{Mb)+ ... +N(Mf). Следовательно, Яя = я •/>„-!= л!. Доказательство 2. Будем последовательно выбирать элементы множества А и размещать их в определенном порядке-на п местах. На первое место можно поставить любой из п элементов. После того как заполнено первое место, на второе место можно поставить любой из оставшихся п ■— 1 элементов и т. д.; По правилу умножения все п мест можно заполнить п(п—1)(п — 2) ... 2- l=/i! способами. Следовательно, множество А из п элемен- тов можно упорядочить п! способами. 23
Задача 1. Сколькими способами можно разме- стить на полке 4 книги (обозначим их Л, В, С, D)? Решение. Искомое число способов равно числу способов упорядочения множества, состоящего из 4 элементов, т. е. р4 = 1 . 2 . 3 • 4 = 24. Задача 2. Сколькими способами можно упоря- дочить множество {1, 2, ..., 2я} так, чтобы каждое четное число имело четный номер? Решение. Четные числа можно расставить на местах с четными номерами (таких мест я) я! спосо- бами; каждому способу размещения четных чисел на местах с четными номерами соответствует я! способов размещения нечетных чисел на местах с нечетными номерами. Поэтому общее число перестановок ука- занного типа по правилу умножения равно п\-п\ = = (я!)2. Задача 3. Сколько можно составить перестано- вок из я элементов, в которых данные 2 элемента не стоят рядом? Решение. Определим число перестановок, в ко- торых данные 2 элемента а и Ь стоят рядом. Могут быть следующие случаи: а стоит на первом месте, а стоит на втором месте, ..., а стоит на (я — 1)-м ме- сте, а Ь стоит,правее а; число таких случаев равно я— 1. Кроме того, а и Ъ можно поменять местами, и, следовательно, существует 2(я— 1) способов разме- щения а и b рядом. Каждому из этих способов соот- ветствует (я —■ 2)! перестановок других элементов. Следовательно, число перестановок, в которых а и Ь стоят рядом, равно 2-(я—1).-(я —2)! == 2-(я—1)1. Поэтому искомое число перестановок равно я! - 2 • (я - 1)! = (я - 1)! • (я — 2). Задача 4. Сколькими способами можно распо- ложить на шахматной доске 8 ладей так, чтобы они не могли бить друг друга? Решение. При указанном расположении ладей на каждой вертикали и каждой горизонтали стоит лишь одна ладья. Рассмотрим одно из таких располо- жений ладей. Пусть а\ — номер вертикали, в которой стоит ладья из первой горизонтали, а^-— Номер верти- 24
кали, в которой стоит ладья из второй горизонта* ли, ..., а8 — номер вертикали, в которой стоит ладья из последней, восьмой, горизонтали. Тогда (аь ..., а8) есть некоторая перестановка чисел 1, ,*., 8. Среди чи- сел аь ..., а8 нет ни одной пары равных, иначе 2 ла- дьи попали бы в одну вертикаль. Следовательно, каж- дому расположению ладей соответствует определен- ная перестановка чисел 1, .»., 8. Наоборот, каждой перестановке чисел 1, .,*, 8 соответствует такое рас- положение ладей, при котором они не бьют друг дру- га. Следовательно, число искомых расположений ла- дей равно Р8 = 8! = 40 320. 4.2. Упорядоченные подмножества данного множе- ства (размещения). Рассмотрим теперь упорядочен- ные подмножества данного множества А. Само мно- жество А считаем неупорядоченным, поэтому каждое его подмножество может быть упорядочено каким- либо возможным способом. Число всех ^-элементных подмножеств множества А равно С*. Каждое такое подмножество можно упорядочить k\ способами. Таким образом получим все упорядоченные /^-элементные подмножества множества А. Следовательно, их чис- ло будет k\ • Сп* Теорема. Число упорядоченных k-элементных подмножеств множества, состоящего из п, элементов, равно Al^k\.Cl^—^w = n{n-\) ... (д-Л+1). Упорядоченные fe-элементные подмножества мно- жества из п элементов называются размещениями из п элементов по k. Различные размещения из п по k отличаются количеством элементов либо их поряд- ком/ Следовательно, число различных размещений из п по k равно Л* = я(л—1) ... (л —ft'+l). Задача 5. Сколькими способами можно расса- дить 4 учащихся на 25 местах? Решение. Искомое число способов равно числу размещений из 25 по 4; А\ъ = 25 • 24 • 23 . 22 = 303 600. 25
Задача 6. Учащемуся необходимо сдать 4 экза- мена на протяжении 8 дней. Сколькими способами это можно сделать? Решение. Искомое число способов равно числу 4-элементных упорядоченных подмножеств (дни сда- чи экзаменов) множества из 8 элементов, т.е. Лв — = 8 • 7 • 6 • 5 = 1680 способов. Если известно, что по- следний экзамен будет сдаваться на восьмой день, то число способов равно 4.^7 = 7.6.5.4 = 840. УПРАЖНЕНИЯ 1. Сколькими способами можно упорядочить множество {1, 2, .,., п} так, чтобы числа 1, 2, 3 стояли рядом и в порядке возрастания? 2. Сколькими способами могут разместиться 5 покупателей в очереди в кассу? 3. Сколько существует перестановок из п элементов, в кото-* рых между двумя данными элементами стоит г элементов? 4. На собрании должны выступить 4 человека Л, Ву С, ZX Сколькими способами их можно разместить в списке ораторов, если В не может выступать до того момента, пока не выступит Л? 5. Сколькими способами можно рассадить п гостей за круг- лым столом? 6. Сколькими способами можно упорядочить множество {1, 2, ..., п} так, чтобы каждое число, кратное 2, и каждое число, кратное 3, имело номер, кратный 2 и 3? 7. Если повернуть лист белой бумаги на 180°, то цифры 0, 1, 8 не изменяются, цифры б и 9 переходят друг в друга, а осталь- ные цифры теряют смысл. Сколько существует семизначных чи- сел, величина которых не изменяется при повороте листа бумаги на 180°? 8. В розыгрыше первенства страны по футболу в высшей лиге класса «А» участвует 10 команд. Команды, которые займут пер- вое, второе и третье места, награждаются соответственно золотой, серебряной и бронзовой медалями, а команды, которые займут последние 2 места, покинут высшую лигу. Сколько разных резуль- татов первенства может быть? § 5. ПЕРЕСТАНОВКИ С ПОВТОРЕНИЯМИ Поставим такой вопрос. Сколькими способами мо- жно разложить множество Л, состоящее из п элемен- тов, на сумму т подмножеств л=в1ив2и ... \}Вт так, чтобы N(В{) = ku N(B2) = k2i ..., N(Bm) = km, где ku k2i ..., km — данные числа (&г^0, k\ +. „•> 26
...r-£km = n)'> Множества Ви В2, ..., Вт не должны иметь общих элементов. Все описанные выше разбиения множества А на т групп Ви В2, ..., Вт можно получить так: возь- мем произвольное ^-элементное подмножество В{ множества А (это можно сделать С« способами); среди п — k\ оставшихся элементов возьмем ^-эле- ментное подмножество В2 (это можно сделать С^-^ способами) и т.д. Общее число способов выбора раз- личных множеств Ви ..., Вт по правилу умножения равно _ /г! (я —*i)! &i!(# —- &i)l k2\ {п — k\ — k2)\ (n — k{ — ... (лг — ^i — &2)! &3! (n — ki~ k2 — kz)\ _r".^i-.i)! _ rt! ______ &m! (« — £i — ... ~ #m)-r &i! /г2! . •. &ml (напомним, что 0! = 1). Итак, мы доказали следующую теорему. Теорема. Пусть ku k2, ..., km— целые неотри- цательные числа, причем k\-{-k2-\-. v.'-{• km = п. Чи- сло способов, которыми можно представить множе- ство А из п элементов в виде суммы m множеств Ви 52, ..., Вт, число элементов которых составляет соответственно ku k2, *,., km, равно ^п \#b • • • > km) === k\\ ... kfn\ Числа Cn(ku .,,, km) называются полиномиальны- ми коэффициентами. Они имеют еще одну очень важ- ную комбинаторную интерпретацию. Пусть имеется п букв: k\— букв аи k2— букв a2t .. -, km — букв аш (k\ + k2 + ... + km = п). Опре- делим, сколько различных слов можно составить из этих букв. Перенумеруем места, на которых стоят буквы, числами 1, 2, ..., п. Каждое слово опреде- ляется множествами В\ (номера мест, где стоит буква tfi), В2 (номера мест, где стоит буква а2), ..., Вт (но- мера мест, где стоит буква ат). Следовательно, число различных слов равно числу способов, которыми мож- но представить множество А = {1, 2, ,,., п) в виде 27
суммы множеств Ви В2, ..., Вт, т. е Пример 1. Число различных слов, которое полу- чим, переставляя буквы слова «математика», равно -2^=151200. Пример 2. Число слов, которые можно составить из 12 букв (4 буквы а, 4 буквы б, 2 буквы в, 2 буквы г), равно 12! 4!-4!-2!-2! = 207 900. Утверждение, установленное выше, можно сформу* лировать в виде следующей теоремы. Теорема. Число различных перестановок, кото* рые можно составить из п элементов, среди которых имеется k\ элементов первого типа, k2 элементов вто- рого типа, ..,, km элементов m-го типа, равно сп{К ..., km)= kiluu%kml • В связи с важностью теоремы приведем еще одно доказательство. Рассмотрим одну перестановку и за- меним в ней все одинаковые элементы разными. То- гда число различных перестановок, которые можно составить из рассматриваемой ищи перестановки, равно k\\-k2\ ... km\. Проделав это для каждой пере- становки, получим п\ перестановок. Следовательно, Cn{ku ..., km)- kx\ ... kml = nl, что и доказывает утверждение теоремы. УПРАЖНЕНИЯ 1. Сколько различных слов можно составить, переставляя буквы слова «мама»? Напишите все эти слова. 2. Сколькими способами можно разделить m + п + s предме- тов на 3 группы так, чтобы в одной группе было m предметов, в другой — п предметов, в третьей — s предметов? 3. Сколькими способами можно разделить Зп различных пред- метов между тремя людьми так, чтобы каждый человек получил п предметов? 4. Сколько пятибуквенных слов можно составить из букв а, Ь, с, если известно, что буква а встречается в слове не более 28
двух раз, буква Ъ — не более одного раза, буква с — не более трех раз? 5. Сколько различных слов можно составить, переставляя буквы слова «комбинаторика»? § 6. ВЗАИМНО ОДНОЗНАЧНОЕ СООТВЕТСТВИЕ. СОЧЕТАНИЯ С ПОВТОРЕНИЯМИ 6.1. Взаимно однозначное соответствие. Предполо- жим, что заданы 2 множества А и В. Будем считать, что между этими множествами установлено соответ- ствие, если каждому элементу а из Л соответствует некоторый элемент Ь из В и, наоборот, для каждого элемента b из В существует такой элемент а из Л, что Ь соответствует а. Это соответствие будет взаимно однозначным, если каждому элементу из А соответ- ствует только один элемент из В и различным элемен- там множества А соответствуют различные элементы множества В. Пример 1. А— множество учащихся класса, В — множество парт. Каждому учащемуся соответствует парта, за которой он сидит (это не взаимно однознач- ное соответствие). Пример 2. А — множество всех городских жите- лей СССР, В — множество всех городов СССР. Каж- дому элементу А соответствует город, в котором он живет (это также не взаимно однозначное соответ- ствие) . Примером взаимно однозначного соответствия мо- жет быть соответствие между элементами упорядо- ченного множества А из п элементов и числами 1, 2, ..., п\ каждому элементу соответствует его но- мер. Определение. Множества, для которых суще- ствует взаимно однозначное соответствие, называются эквивалентными. Теорема. Л ля того чтобы два множества были эквивалентными, необходимо и достаточно, чтобы они имели одинаковое число элементов. Доказательство. Если множества А и В имеют одинаковое число элементов я, то, упорядочи- вая каждое из них некоторым образом и ставя h соот- -> ветствие /г-му элементу множества A k-k элемент 29
множества fi, получим взаимно однозначное соответ- ствие между множествами А и 5, т. е. множества А и В эквивалентны. Допустим теперь, что А имеет п элементов и суще- ствует взаимно однозначное соответствие между А и В. Упорядочим множество А: пусть элементами А бу- дут fli, а2, ..., ап. Обозначим через bk тот элемент 5, который соответствует а&. Поскольку каждому эле- менту из А соответствует элемент из 5, различным элементам из А соответствуют различные элементы из В, и каждый элемент из В соответствует некоторому элементу из Л, то В состоит из элементов Ьь Ь2, ..., Ьпу следовательно, В имеет п элементов. Следствие. Если два множества эквивалентны, то они имеют одинаковое чивло элементов. Это свойство эквивалентных множеств очень часто используют для вычисления количества элементов различных множеств. Пример 3. Рассмотрим множество А последова- тельностей х\9 #2, ..., хп из п чисел, где числа Х\ при- нимают только значения 0 и 1 и среди них ровно k единиц. Чтобы вычислить число элементов нашего множества, обратим внимание, что оно эквивалентно множеству В всех ^-элементных подмножеств множе- ства {1, 2, ..., п}\ подмножество чисел {i'i, ..., ik) соответствует той последовательности х\у х2, ..., хп, у которой xt = 1, Xt2 = l, ..., xik = l. Следовательно, N(A) = Ci Пример 4. Найти число размещений п одинако- вых предметов в m урнах. Перенумеруем урны. Поставим в соответствие каждому размещению предметов в урнах последова- тельность из нулей и единиц следующим образом: сначала последовательность имеет группу нулей, ко- личество которых равно числу предметов в первой урне, затем записываем единицу и далее пишем столь- ко нулей, сколько предметов во второй урне, снова единицу, затем столько нулей, сколько предметов в третьей урне, и т.д. Заканчивается последователь- ность группой нулей, которая является числом пред- метов в последней урне. Следовательно, последова- тельность имеет п нулей и m — 1 единиц, всего 30
п'+m—l чисел. Например, при n=10, т = 4 по- следовательность 1011000000000 соответствует разме- щению: первая урна пустая, вторая урна имеет 1 пред- мет, третья урна пустая, чет&ертад урна имеет 9 предметов; а последовательность 0010010000001 соот- ветствует размещению: первая урна пкеет 2 предмета, вторая — 2 предмета, третья — 6 предметов, четвер- тая — пустая. Используя предыдущий пример, получаем, что ис- комое число размещений будет Cj+m-i- 6.2. Сочетания с повторениями. Сочетаниями из m элементов по п элементов с повторениями называются группы, содержащие п элементов, причем каждый эле- мент принадлежит к одному из m типов. Например, из трех элементов a, ft, с можно соста* вить такие сочетания по два с повторениями: аа, ас, be, ab, bby ее. Теорема. Число различных сочетаний из m эле- ментов по п с повторениями равно 'm m+n—l m+n-l' Доказательство. Каждое сочетание пол- ностью определяется, если указать, сколько элемен- тов каждого из m типов в него входит. Поставим в соответствие каждому сочетанию последовательность нулей и единиц, составленную по такому правилу: на- пишем подряд столько единиц, сколько элементов первого типа входит в сочетание, далее поставим нуль и после него напишем сколько единиц, сколько эле- ментов второго типа содержит это сочетание и т.д. Например, написанным выше сочетаниям из трех букв по две будут соответствовать такие последовательно- сти: 1100, 1001, 0101, 1010, ОНО, ООП. Таким образом, каждому сочетанию из ш по п со* ответствует последовательность из п единиц и m — 1 нулей, и наоборот, по каждой такой последовательно- сти однозначно восстанавливается такое сочетание. Поэтому число сочетаний из га по п с повторениями 31
равно числу последовательностей из п единиц и т — Т нулей, т. е. равно Cm+n-i- Пример 1. Кости домино можно рассматривать как сочетания с повторениями по два из семи цифр! О, 1, 2, 3, 4, 5, 6. Число всех таких сочетаний равно /2 = !lL=28. Пример 2. Сколько целых неотрицательных ре- шений имеет уравнение Существует тесная связь между решениями ука- занного уравнения и сочетаниями из т элементов по п. Если имеем целые неотрицательные числа Х\, ... ,.., хт такие, что *i + • • • +хт = п, то можем соста- вить сочетание из т элементов по п, взяв Х\ элемен- тов первого типа, х% — второго типа, ..., хт — т-го типа. Наоборот, имея сочетание из m элементов по п, получим решение уравнения Х\ + ... + xm = п (*i — число элементов первого типа,' х2 — число элементов второго типа, ..., хт — число элементов т-го типа) в целых неотрицательных числах. Следовательно, ме- жду множеством всех сочетаний из т элементов по п с повторениями и множеством всех целых неотрица- тельных решений уравнения Х\ + ... + хт = п уста- навливается взаимно однозначное соответствие. По- этому число решений равно £.П рП 'т m+n-V УПРАЖНЕНИЯ 1. Напишите все сочетания с повторениями из трех элементов а, Ь, с по 3. 2. Сколькими способами можно выбрать 6 одинаковых или разных пирожных в кондитерской, где есть 11 разных сортов пи- рожных? 3. Сколько можно сделать костей домино, используя числа О, 1, ..., г? 4. Сколько целых положительных решений имеет уравнение х\ + ... + хт = п? 5. Сколько целых неотрицательных решений имеет неравен- ство *i+ ... +хт^п? 32
§ 7. ПРЯМОЕ ПРОИЗВЕДЕНИЕ МНОЖЕСТВ Допустим, что заданы множества Ль ..., Ак. Мно- жество всех элементов вида (аь ..., ак), где а\^Аи а2 еЛ2, ..., fiftG Ак, называется прямым произведе- нием множеств Ль ..., Ак и обозначается ЛХЛХ ....ХЛь. Пример 1. Если Л = {а, й}, В = {с, d, е), то ЛХ5 = {(а, с), (a, d), (а, е), (6, с), (6, d), (6, е)}. Пример 2. Пусть имеется множество Л из п эле- ментов. Возьмем из Л какой-нибудь элемент, обозна- чим его через а\ и вернем снова в множество Л. Да- лее возьмем из Л некоторый элемент, обозначим его . через а2 (в частности, может случиться, что попадется снова элемент а{). Проделав эту операцию k раз, по- лучим набор {аи ..., ак), который называют k-сло* вом, составленным из элементов множества Л. Мно- жество всех &-слов, составленных из элементов Л, яв- ляется прямым произведением Л X А X • • • X А и кратко обозначается Ak. Например, если Л — множе- ство из двух букв {а, &}, то множество Л2 всех слов имеет вид {аа, ab, ba, bb}. С й-словами мы часто стал- киваемся в различных ситуациях. Все десятичные за- писи чисел являются словами, составленными из цифр 0, ..., 9; обычные слова — это слова, состоя- щие, например, из букв русского алфавита; фразы—« это «слова», состоящие из русских слов, и т. д. Естественно задать вопрос: сколько различных &-слов можно составить из. элементов множества Л, имеющего п элементов? Следующая теорема дает ответ на этот и на более общий вопрос: сколько элементов содержит прямое произведение А\ X А2 X ... X Ак? Теорема. N(AX X ... ХАк) = N(AX). ..N(Ah). Доказательство. Покажем сначала, что N{AlXA2) = N(Al)^N{A2). Обозначим через BCl подмножество множества Л1ХЛ2, которое состоит из элементов вида (си cl2), где С\ — фиксированный элемент из Ль а а2 — произ- вольный элемент из А2. Тогда N {BCl) = N (Л2), так как 33
ВСх эквивалентно А2 (элементу (<$ь а2) соответствует а2). Если аь&ь ..., fi — все элементы множества Аи то AiXA2 = Bail)Bbll) ... [)Bfl. Множества Bai, В&1? ,.., Bfx попарно не имеют общих элементов. Поэтому N{AlXA2) = N{Bai) + 'N(Bbi)+ ... + N(Bh) = ^N(A{)-N(A2). Примем теперь во внимание, что множества Ах X X (А2 X ... X Ah) и А\ X А2 X .*. X Ah эквивалентны: элементу [аи (аъ . . ., ak)\ соответствует элемент (аи а2, ..., ak). Поэтому N(A,X ... XAk) = N(Al).N(A2X ... ХЛ*) = «^(А^.АГ^.ЛГ^Х ... X4k)- = АГ(Л,).АГ(Л2)...ЛГ(ЛЛ)> что и требовалось доказать* Пример 3. Число й-слов, составленных из эле- ментов множества А, равно N(Ak) = [N(A)]\ Пример 4. Дадим ответ на вопрос, сколькими способами можно распределить k разных предметов среди п лиц? Пусть А — множество лиц, среди которых распре- деляют предметы. Перенумеруем предметы и поста- вим в соответствие каждому способу распределения символ (аи ..., аи), где а\ — лицо, которое получило первый предмет, ..., аи — лицоп которое получило k-& предмет. Очевидно, (аи .., ^и)—&-слово, составлен- ное из элементов множества А. Установленное соот- ветствие является взаимно однозначным, и поэтому число способов распределения k предметов среди п лиц равно числу й-слов, которые можно составить из элементов множества Л, т. е. равно пк. Пример 5. Пусть имеем множество X = = {#ь ..., Хь), состоящее из k элементов, и множе- ство Y= {уи ..., Уп}> состоящее из п элементов. До- пустим, что каждому элементу множества X постав- лен в соответствие некоторый элемент множества У« 34
Тогда говорят, что на множестве X задана функция с областью значений У. Множество X называется об* ластью определения функции. Естественно возникает вопрос: сколько всего имеется различных функций с областью определения X и областью значений У? Каждую функцию можно задать таблицей значений: Xi \ун х2 У12 • • • . . . Xs УЧ . . . . . . Xk % где t/i — это тот элемент множества У, который по- ставлен в соответствие xs. Поскольку каждый из эле- ментов ytl, ..., yik может быть одним из элементов множества У, то всего имеется nh различных таблиц., (Можно рассуждать еще и так: нижняя строка таб- лицы {ijix, ..., yif^ есть &-слово, составленное из эле- ментов множества У, а, как известно, различных &-» слов, составленных из элементов множества У такого, что N(Y)=n, имеется nk.) Следовательно, имеется nk различных функций с областью определения X и областью значений У. УПРАЖНЕНИЯ 1. Пусть А = {а, Ь}, В = {а, Ь, с}. Указать все элементы мно- жества л х в. 2. Пусть А = [0, 1), В ==(0, 1)U [2, 3]. Изобразить в декар- товой системе координат XOY множество Л X В. § 8. БИНОМ НЬЮТОНА И ПОЛИНОМИАЛЬНАЯ ФОРМУЛА 8.1. Бином Ньютона. Известно, что (a + b)2 = a2 + 2ab + b29 (а + 6)3 = а3 + За2Ь + ЗаЬ2 + Ъ\ Как раскрыть скобки при вычислении выражения (а + Ь)п? Ответ на этот вопрос дает следующая Теорема. Имеет место равенство (а + b)n = C°nanb° + Clnan'lbl + ... ... +cUn-kbk+ ... +Cnna°bn> (1) 35
где rk п\ ^п ~~ k\(n-k)\ * Эту теорему иногда называют биномиальной тео- ремой, а числа Скп — биномиальными коэффициент тами. Равенство (1) часто называют биномом Нью* тона, хотя это название исторически не является спра- ведливым, так как формулу для (а+Ь)п знали еще среднеазиатские математики Омар Хайям (1048—- 1131), Гийае ад-Дин Джемшид ал-Каши (ум. ок, 1430). В западной Европе до Ньютона ее знал Пас- каль (1623—1662). Заслуга Ньютона в том, что он обобщил формулу (1) для нецелого показателя п. Вид формулы бинома в этом случае рассмотрен в § 9. На- помним, что С\ есть число А-элементных подмно- жеств множества из п элементов. Формулу (1) можно записать в виде (a + b)n=tcknan'kbk. Доказательство. Перемножим последователь- но (а + b) п раз. Тогда получим сумму 2п слагае- мых вида d\d<i ... dni где dx (i = 1, ..., п) равно либо а, либо Ь. Разобьем все слагаемые на n-fl группу Я0, Ви .-., Вп, отнеся к Bk все те произведе- ния, в которых Ь встречается множителем k раз, а а — (п — k) раз. Число произведений в Bk равно, оче- видно, С\ (таким числом способов среди п множите- лей du ..., dn можно выбрать k множителей, которые будут равны 6), а каждое слагаемое в Bk равно an-kfykt Поэтому (a + b)n=tcknan~kbk. Теорема доказана. Напомним следующее важное свойство биноми- альных коэффициентов: Ckn+l = Ckn + CkrTl. (2) Оно было установлено в § 3, 36
Равенство (2) показывает, что биномиальные ко- эффициенты можно последовательно выписывать в виде треугольной таблицы, которая называется тре- угольником Паскаля: 1 1 л = 1 1 2 1 п=2 13 3 1 п=3 14 6 4 1 п = 4 1 5 10 10 5 1 л = 5 В п-й строке треугольника Паскаля стоят коэффи- циенты разложения (а + Ь)п, причем каждый коэф- фициент, кроме крайних двух, которые равны 1, ра- вен сумме соответствующих коэффициентов из преды- дущей строки. 8.2. Полиномиальная теорема. Рассмотрим вопрос о том, как раскрывать скобки при вычислении выра- жения вида (а{ + а2 + ... +ak)n. Полиномиальная теорема. Выражение- (а{ + а2 + ... + ak)n равно сумме всех возможных слагаемых вида rx\r2\...rk\ ai a2 ••• afe» где r\ + r2+... +rk==n, т. е. {а{ + а2+ ... +ak)n — = V nl <fi....'arA (3) Z-/ гЛ... гъ\ 1 & v ' r,>0. ...,rk>0 1 * Доказательство. Перемножим последователь- но а\ + ... -Ь aft п раз. Тогда получим &п слагаемых вида d\d2 ... dn, где каждый множитель d{ равен или аи или а2, ..., или аи. Обозначим через В(ги ..., Гь) совокупность всех тех слагаемых, где а\ встречается множителем г\ раз, а2 — г2 раз, ..., ah — г* раз. зг
Число таких слагаемых равно Сп(ги ..., г*)'--*числу способов представления множества из п элементов {1, 2, ..., п] в виде суммы k множеств Ви В2, .,., Вк так, чтобы множество Bs имело rs элементов (rs ^ О, П + г2 + ... + rk = я; множество Bs — это множество тех i} для которых df = а8). В § 5 было показано, что Cfivi» •••> rk) = ~, 77 • Следовательно, (а,+ ... + а*Г = £ л! •а'1 ... а; При k = 2 равенство (3) имеет вид rj>0 гЛ>0 х Л (в4 4-atT — 2 7ГоГ=1ТГ«Г-Гв5- Следовательно, мы получили формулу бинома Нью- тона. 8.3. Биномиальные тождества. Числа С\ имеют ряд важных свойств. Укажем некоторые из них и установим ряд интересных тождеств, которым удов- летворяют биномиальные коэффициенты. Напомним в первую очередь следующие равенства: Ckn = Cnn~k> (4) Ck s>k I s>k— 1 /r\ C°n + Cln+ ... +Cnn^2\ (6) C°n-Cln + Cl- ... +(—1)ЛС2==0. (7) Равенство (4) легко проверяется вычислением. Оно следует также из того, что число ^-элементных под- множеств множества из п элементов равно числу (л — &)-элементных подмножеств. Равенство (5) мы доказали в п. 3.1. Равенство (6) получим, взяв в фор- муле бинома а = 6». 1. Оно следует также из ком- бинаторных соображений, которые были проведены в п. 3.1. Если в формуле бинома Ньютона положить а = 1, Ь = —1, получим равенство (7)4 38
Иногда при доказательстве некоторых тождеств полезно иметь в виду геометрическую чисел С*, которая была приведена в п. Докажем еще несколько важных тождеств. Задача 1. Доказать, что интерпретацию 3.1. биномиальных Сп = Сл_1 + Сп-2'+ ..• + сг г-\ (8) класса Тъ. Доказательство 1. Рассмотрим все г-эле- ментные подмножества множества А = {аь ..., ап}. Число их равно Сгп. Разобьем все эти подмножества на классы Гь ..., Гп_г+Ь отнеся к классу Тк все те r-элементные подмножества множества Л, в которых элемент с наименьшим индексом равен ак. Поскольку каждое подмножество из может быть получено присоединением к ак некото- рого (г—1)-элементного подмножества множества {cLh+u cth+2, ..., cin}, то класс Tk состоит из CrnZlk под- множеств. Следовательно, получаем равенство (8). Доказательство 2. п- Рассмотрим все кратчайшие ломаные, соединяющие точ- ку (0; 0) сточкой (г;п — г). Число всех таких ломаных равно Сгп. Отнесем к клас- су Вк те ломаные, которые пересекают прямую х = 1/2 в точке (1/2; k) (k = Q, ... ..., п — 1). Очевидно, класс Вк состоит из CrnZ\-i ло- маных (рис. 6). Поэтому п-г Сп = £и ^n-k-h fe=Q Задача 2. Доказать, что i "г" ^п\чп ""Г • • • "т" ^rv^m — ^n+m- У> /f { j__ (Г; П-Г) 4fc~ б 1/2 r X Рис. 6. CO s^k (9) Доказательство 1. Все ^-элементные подмно- жества множества A = {al9 ап> ап+1> а> пЛ-ш. } 39
(число их равно Сп+т) разобьем на k + 1 класс Vo, Vu • •♦, Vk, отнеся к классу Vi все те подмноже- ства, в состав которых входит ровно i элементов с индексами, не большими чем п. Каждое подмножество из класса Vi можно получить, присоединяя к не- которому t-элементному подмножеству множества {аи ..., ап} {k — i)-элементное подмножество множе- ства {ап+\9 ♦ .., an+m}. Поэтому в состав Vi входит подмножеств. Следовательно, k Ck VI r^i s>k.— i n+m — Z-* ^n^m • i=0 Считая в (9) k = n = m, имеем тождество * (c°„)2 + (^)2+ ... +(C)2 = c2"„, (io) которое уже было доказано с помощью геометриче- ских соображений в п. 3.1 (задача 6). Доказательство 2. Воспользуемся следую- щим замечанием: если два многочлена Р(х) и Q(x) равны при всех х, то коэффициенты этих многочле- нов при одинаковых степенях х равны. Действитель- но, если P(x)= Q(x) и при некоторой степени х ко- эффициенты не равны, то многочлен Р(х)—Q(x) будет многочленом с ненулевыми коэффициентами, имеющим бесчисленное множество действительных корней, что противоречит основной теореме алгебры. Запишем равенство (l+x)n(l+x)m = {l+x)m+n. (11) Используя формулу бинома Ньютона, убеждаемся, что коэффициент при xk в правой части равенства (11) равен Ст+п, а коэффициент при xh в левой ча- сти этого равенства имеет вид СО г>к _\ f>\ s>k— 1 i^ i^ *->kr>SS tv^m ~T~ ^n^m i • •■ • i^n^tn» Равенство (9) доказано. Задача 3. Доказать, что т 40
(сумма в левой части вычисляется до тех пор, пока верхний индекс не станет больше нижнего). . Доказательство. Пусть еь •»,, е™ — корни уравнения хт— 1 = 0, т. е, e* = cos-^ + /sin-^p (£ = 1, 2, ..., m). (13) Заметим, что для каждого натурального г ( т9 если г делится на га, г\+ ... + e'={ А (14) 1 10, если г не делится на т. Действительно, согласно (13), гк — г\, и поэтому ej + ... +e^ = ej + ef + ... e^-1*'+ 1. (15) Если г делится на га, то все слагаемые в правой ча- сти равенства (15) равны 1. Если жег не делится на га (г = qm + р, 1 ^ р ^ ш — 1), то 8r = &qm+p :===гр=г^ф1 поскольку е™ = 1. Равенство (14) доказано. Из равенства (14) следует, что (1+80*+ ... +(l+em)»=Zc!;(e?+ ... +erm) = = т(с°„ + С + сГ + ... +С„ВЙ)' (16) Поскольку + zk = 1 + cos h i sin—:- = ~ fort / &jt , . . kn \ = 2cos — { cos h г sin ■— , TO (1+6^+ ... +(l+emr = > 2 cos —(cos Hsin }. (17) n kn ( nkzi . . . nk%' к" l 41
Из равенства (16) следует, что правая часть в (17) — действительное число. Поэтому &=1 (18) Сравнивая (16) и (17), получим (12). Задача 4. Доказать, что C?C5l + C?ri1CUi+ .-• +С0п-тСТ+т = С%+ш- (19) Доказательство. Рассмотрим все кратчайшие пути, которые ведут из точки (0; 0) в точку (n — m + k+U т). Разобьем все такие пути на классы Lo, Lu ..., Lm, отнеся к классу Lr все те пути, которые пересекают прямую х — k + 0,5 в точке (&-j-0,5; г) (рис. 7). Поскольку каждую ломаную из Yi (И; <>—н> (rj~m+k+/; rri), (кН;г)\ h к+l Рис. 7. Lr можно разбить на 3 части (ломаную, соединяющую (0;0) с (Jfe;r), горизонтальный отрезок, соединяющий точки (й;г) и (&+1; г), и ломаную, соединяющую (k + l; г) с (л — m + fc+1; m)> то общее число ло- маных, из которых состоит класс Lrt равно Общее же число всех путей из точки (0; 0) в точку (rt_m-j-/5+ 1; m) равно Сд+л+i. Поэтому имеет ме- сто (19). 42
УПРАЖНЕНИЯ 1. Доказать формулу бинома Ньютона, применяя метод ма тематической индукции. 2. а) Доказать, что С* + 1 > с\ при k < ~?г^ и Ck+l<c\ при & > g—• б) Указать наибольшее среди чисел с\ (k = 0, 1,«.., п). 3. Найти я, если известно, что в разложении (1 +х)п коэф- фициенты при х5 и х12 равны. 4. Сколько рациональных членов содержит разложение ( _ 4 -Л100 W2+V3J ? 5. Пользуясь полиномиальной теоремой, вычислить {x + y + fy. 6. Чему равен коэффициент при x2y3z2 в выражении {x + y + zy? 7. Найти коэффициент при xhyr в разложении (1 -\-х + у)п. 8. Найти коэффициенты при х17 и л:18 в разложении (4+х5 + *7)п. 9. Доказать, что Cn+i(i, U А) = Сд(/-1, /,(А) + СЯ(/, / — 1, Лк) -ЬСЛ(£, /, А-1). 10. Сколько членов содержит полиномиальное разложение (формула (3) в п. 8.2)? 11. Доказать, что сумма всех коэффициентов полиномиаль- ного разложения равна kn. 12. Доказать, что числа Схр, С2р, ..., С%~1 делятся на /?, если р — простое число. 13. Доказать, что разность а?—а при любом целом а де- лится на р, если р — простое число (малая теорема Ферма). 14. Доказать, что разность [(2 + У 5 )Р] — 2Р+1 делится на р. если р ~~ простое число (р > 2). (Символ [х] обозначает целую часть х.) 15. Обозначим а (а — А) (а — 2А) (а — ЗА) ... (а — (и — 1) А) = а"/Л (в частности, ап1° = art). Доказать, что (а + b)nlh = a*'* + Clna{n~mb + ... + &*//l. Доказать тождества: .0.1 „I . • 1 - Й^'-1 16. с„ + уС„+ ... 4-^qrj-c^: -+1 17. С^ + 2С^ + ... + пСпп = п2"-1. 43
19. С» + С2 + ... + С2Гп/2' = = С^ + С* + ... +С2[("+1>/21-,=2"-1. го. с*:2 + 2с*:2 +...+(„- k +1) cjtil=с*. 91 A»fe —3/^2 I /-»&—3/-»2 _| !_ •>& — 3/о2 , /о& 22.С« + С«+1 + ... +С* + -{ с2+ш+1 при * = "• 23. cc + c^+m + c:+2"l+ ... - п — х cos" — cos при т > 1. 2" V4 Вычислить суммы: 24. C°-C; + C2- ... + (-l)mC™ 26. (c°„)2 - (clf+ (c2)2 -...+(- 1)» (c«)2 27. <*+C* + C* + ... 28. 4+C^ + C^+ ... 29. C°„ + C*+C*+ ... 30. cl + c7n + clnl+ ... зк с2+ с5„ + с*+ „. 32. 1 + C\ cos ф + C2 cos 2ф + ... + C£ cos яф. 33. Cjj sin ф + C2 sin 2ф + ... + Cnn sin лф. 34. Найти все корни уравнения 1 х *(*-- 1) п„*(* — 1) ... (л: — п+ 1) _ 1 1! "*" 2! •••-1-v U п, —". 35. Пусть а, р, а — натуральные числа, а + Р < т, а + р < п. Доказать, что а-1 6 ^a+m-kbn-a-l+k'r L* ^m+a-a+l^n+a-a-l^ fe=0 fe=»l m—a-ft Л-0 44
36. В классе изучают 2п предметов. Все ученики учатся на 4 И 5. Никакие 2 из них не учатся одинаково, ни о каких двух из них нельзя сказать, что один из них учится лучше другого. До- казать, что число учеников в классе не превышает С^. 37.' Пусть Q — некоторое множество, содержащее п элемен- тов, a Ait ..., Ak — подмножества этого множества. Набор под- множеств Л4, ,,,, Ak будем называть коллекцией Шпернера, если ни одно из множеств А и ..., Ak не является частью другого. а) Пусть Q = {#, Ь, с}. Какие из указанных ниже наборов являются коллекциями Шпернера: * 1 = [{а}, {&}, {с}], К2=1[а, Ь], {а, с}, {&, с}], Къ = [{а}, {а, с}, {Ь, с}]? б) Пусть Q = (а, Ъ). Указать все возможные коллекции Шпернера этого множества. 38. (Теорема Шпернера.) Пусть Q — множество, состоящее из п элементов, Ait ..., Ak — коллекция Шпернера этого множества. Тогда k < С^2К Доказать это. 39. Пусть Q — множество, состоящее из п элементов, А и ..# ♦.., Ak — коллекция Шпернера этого множества, iit ..., ik — соответственно числа элементов множеств Ль ..., А^ Доказать, что -4.+4-+...+-VO- <• <2 с* 40. Получить из утверждения задачи 39 утверждение зада- чи 38. .41. Пусть An—число различных коллекций Шпернера для множества из п элементов. Доказать, что 2Тп<Ап<СТтп. 2 П 42. Пусть хи ..., хп — действительные числа, \Хг\ ^ 1. До- казать, что в любом интервале длины 2 имеется не более чем С^/21 сумм вида Yiekxk> r#e &* = ±*- 43. Доказать тождества: ^9Ь ^9 С* 4" к=0 б) £(-d* к"й 2fe+l <»+l)Cj,+1 45
§ 9. МЕТОД РЕКУРРЕНТНЫХ СООТНОШЕНИЙ Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с п предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого со- отношения, которое называется рекуррентным (воз- вратным). Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для небольшого количества предметов (одного, двух)' ре- шение задачи легко находится. Проиллюстрируем метод рекуррентных соотноше- ний на примерах. Пример 1. {Сочетания с повторениями.) Сочета- ние из п предметов по г с повторениями — это группы по г предметов, взятых из данных п предметов, при- чем каждый предмет может повторяться какое угодно число раз (порядок предметов в группе безразличен).; Например, все сочетания из четырех чисел 1, 2, 3, 4 по два с повторениями имеют вид 11, 12, 13, 14, 22, 23, 24, 33, 34, 44. Таким образом, число сочетаний из 4 по 2 с повторениями равно 10. Обозначим число сочетаний из п предметов {аи ..., ап} по г с повторениями через frn. Каждое сочетание из п по г либо содержит, либо не содер- жит а\. Число сочетаний, которые не содержат аь равно frn_{ (это сочетания из предметов а2, ..., ап по г). Каждое сочетание, содержащее аи может быть получено присоединением к а\ некоторого сочетания из п предметов по г — 1 (число таких сочетаний рав- но fr~l). Следовательно, К = Гп-1 + К-1. (1) Мы получили рекуррентное соотношение, из которого можно найти frn. Последовательно применяя (1), по- лучим Г» = К'1 + U-1 = К'1 + (К-\ + К-2) = =/г1+/;-,.+ ---г1+/[. (2) Очевидно, /;=". fi = i. (3) 46
Считая в (2) г = 2, получим fn = n + {n-l)+ ... + 2+1 = _ п(п+\) _ р2 /,ч При г — 3 из равенства (2) получим f я = СЛ-и + С/1 + ••• +Сз+С2 = Сп+2 (мы использовали равенство (8) из п. 8.3). Повторяя эти же соображения далее, на (г—1)-м шаге будем иметь fn — C'n+r-U (б) Пример 2. Найдем число частей, на которые п окружностей делят плоскость, если каждые две окружности имеют общую хорду и никакие три окруж- ности не пересекаются в одной точке. Пусть Ап— искомое число частей. На сколько увеличится число частей, если провести (/г+1)-ю окружность так, что- бы она пересекала все окружности и не проходила через точку пересечения каких-либо двух других окружностей? Поскольку (п+1)-я окружность пере- секается с каждой окружностью в двух точках, то она разделится точками пересечения на 2п дуг, ка- ждая из которых делит пополам одну из частей, ко- торая имеется в Ап. Следовательно, число частей уве- личится на 2п: Ап+1=Ап + 2п. (6) Из этого рекуррентного соотношения получим Ап = 2(п-1) + Ап-1 = 2(п-1) + 2(п-2) + Ап-2=а = 2(п-1) + 2(п-2) + ... + 2.1+Ль Но А\ = 2, и поэтому Ап = п2 — п + 2. § 10. МЕТОД ПРОИЗВОДЯЩИХ ФУНКЦИЙ Метод производящих функций на является элементарным, так как при его использований приходится иметь дело с некоторыми понятиями математического анализа. Остановимся кратко и на этом методе, поскольку он является одним из наиболее эффек- тивных методов решения комбинаторных задач. Далее придется рассматривать суммы бесконечного числа слагаемых. В математическом анализе такие суммы называются рядами. 47
Пусть имеем бесконечную сумму а\ + а2+ ... + ak+ ... 0) Часто такие суммы записывают в виде оо Как же понимать сумму бесконечного числа слагаемых? При\ мем следующее определение. Пусть S/i = ai + ... +ап. (2) Если существует lim sn = s, то ряд (1) называется сходящимся- П->оо и число 5 называется суммой этого ряда: а{ + ... + ак + ... = s. Если же lim sn не существует, то ряд называется расходя* П-»оо щимся. Пример 1. Рассмотрим ряд оо 1.1. . 1 *"" 2-3 + •'• + k(k+ 1) + '•' ~"Zj k(k+\)* 1-2 ' 2-3 j •'• ' /г(/г + 1) fe-i Имеем %=Т72-+^Тз+ ••• + п(п+\) =(1_Т) + +а-|)+-+(4-тЬ-)-'- л+1* Видим, что lim s^ = 1. Таким образом, тг-»оо " 1.1. . 1 ... =1. 1-2 ^ 2-3 ^ "# ^ £.(£ + 1) Пример 2. Рассмотрим ряд оо ,+7т+7Г+-+7Г+-==2^ (3) Имеем неравенство Sn = 1 + ■ -—- + ... + —=->л- —7=- = V». У2 Л/я Vя которое показывает, что Пт5Л = + с». Таким образом, ряд (3) расходится. 48
Пример 3. Рассмотрим ряд оо ' £ (~l)fe""1=l + (-D+l + (-l)+ ... (4) Нетрудно убедиться в том, что если п — четное число, \l если п —- нечетное число. Следовательно, lim sn не существует, и ряд (4) расходится. П->оо Следующие примеры имеют очень большое значение. Пример 4. (Сумма бесконечно убывающей геометрической прогрессии.) В школьном курсе алгебры при изучении геометри- ческой прогрессии рассматривается ряд оо \+х + х2 + ... +xk+ ... =2 **""*• <5> Выясним, при каких х этот ряд сходится, и вычислим его сумму. По формуле суммы членов геометрической прогрессии (при хф\). Если | х\ <1, то lim /=0и lim sft=-j . Если же - л;->оо п->оо 1 л: | л: | > 1, то lim х11 = со, Hm srt не существует, и ряд (5) рас- тг->оо тг-»оо ходится. Ряд (5) расходится также при х = — 1 (пример 3) и при х = 1 (в последнем случае sn = п и Hm srt = + со). П->оо Следовательно, ряд (5) сходится при | х | < 1, и в этом случае \ + х + х2+ ,„ + xk + ... =у^Г7. (6) Пример 5. (Биномиальный ряд Ньютона.) В курсах мате- матического анализа с помощью методов дифференциального ис- числения выводится следующая формула, которая была открыта впервые Ньютоном: (1 + *)а=1+а* + + а(а-±х2+ _ + «(«-l).„(«-fe+l) %k + _ (?) Формула имеет место при |х| < 1. Если а = п — натуральное число, то все слагаемые в правой части равенства (7), начиная с (п + 2) -го, равны- 0, так как все они содержат множитель (п — п). Формула (7) в этом случае обращается в биномиальную формулу, которую мы установили выше. При а = —1 формула (7) принимает вид 1 .=*1-х + х2- ... +(-1)кхк+ ... (8) 1 + * 49
Эта формула вытекает из (6) (достаточно заменить в (6J х на —х). Доказывать формулу (7) в общем случае не будем, а уста- новим ее ниже лишь для целых отрицательных а. Пример 6. (Степенные ряды.) Ряд вида а0 + ахх + а2х2+ ... + akxk + ... (9) называется степенным. Ряды (6), (7), (8) являются примерами степенных рядов. В курсах математического анализе доказывают- ся следующие важные свойства степенных рядов: 1) Областью сходимости (т. е. множеством7 тех х, при кото- рых ряд сходится) является множество вида {xi \х\ < с}, к ко- торому могут иногда принадлежать точки х — -^с и ^ = 0 или одна из этих точек. 2) Степенные ряды можно перемножать, собирая коэффици- енты при одинаковых Степенях х Так, как это делается при умно- жении многочлейов. 3) Если два степенных ряда имеют одинаковую сумму при всех х из области сходимости этих рядов; то коэффицйвйты при соответствующих степенях х этих рядов равны. Пример 7. Выведем формулу {lJ.x)n=l + Cinx + C2n+lx*+ ... +OJt+lk_1**+ ... (Ю) (при \х\ < 1), которая является частным случаем бнйрмиа^ной формулы (7). " ^ ^ ~ ^al.«* Воспользуемся методом полной математической ТрДуШйи! При п= 1 формула (10) имеет место (формула (6)). Допустим, что (10) имеет место. 1*огда 1 = 1 1 ^ (Г- x)n+l (l-xf 1 ~ X "" = (1 + С^ + С|+1^+ .„ +Cku+k^xk+ ...)• «(1+* + л;2 + ... +xk+ •..). Перемножим эти ряды и соберем коэффициенты при одинаковых Степенях X, Коэффициент при х* равен Сп-\ + С« + Ся+1 + ♦♦' +Cn+k-l* Используя равенство Сп-1 + Сл + Сп+1 + «•• ^ Cu+k-i==:Cri+k* которое вытекает из равенства (8) в п. 8.3, имеем (1-1)*-И = 1 + С»+1* + С'+2*2 + ..- + <&.*** + .... что и доказывает формулу (10), 50
Определение. Производящей функцией последовательно- сти {ап} называется сумма степенного ряда оо /1=0 Пример 8. Производящей функцией последовательности ап = ап (п = 0, 1, , ♦.) является A (s) = -г-Ц • Действительно, оо ZaHn = t 1 1 — as тг=0 (сумма бесконечно убывающей геометрической прогрессии; ряд в левой части сходится при \as\ < 1). Пример 9. Производящая функция последовательности ak = С\ (k = 0, 1, ..., п) равна A(s)=f,Cknsk = (l + sy. Пример 10. Производящая функция последовательности ak==:Cn+k (k = °> Ь ...) равна 1 A(s) = (\-s)n+l * Это следует из равенства (10). Пример 11. Производящая функция последовательности авна С 0 при 0 ^ п < kt йп = \ Ckn при п > k sk (\-s)k+l о» Считая в этой сумме я = & + i, где i = 0, 1, ,♦., будем иметь, принимая во внимание пример 10» А (.) = S» % <*+,.' - ** ^ Cj[+y - (i J$)k+l. (II) 51
Идея применения метода производящих функций такова: не- обходимо вычислить все члены некоторой последовательности {ап}. С помощью рекуррентного соотношения для ап или исходя непосредственно из комбинаторных соображений вычисляют про- изводящую функцию A (s) = § а^П' л-0 Раскладывая затем A(s) в ряд и находя коэффициент при sn, тем самым находят ап- Пример 12. (Сочетания с повторениями.) Пусть fn — число сочетаний из п предметов по г с повторениями. Мы установили (см. пример 1 в § 9), что Гп-Г-1 +£_,. 02) При этом ^ = л;для того чтобы (12) имело место и при г=1, достаточно считать, что fn = 1. Пусть оо 4,(»)-Е£л 03) Умножим обе части равенств (12) на sr (г = 1, 2, ...) и сло- жим почленно все равенства; тогда получим Но оо £Г„/ = л„(5)-1, оо оо _ . Е C^""' - Е ^s' = Л« (») (где ' = г - 1), Г-1 1-0 оо E^V-^-iW-J. г-1 и, подставляя эти суммы в (14), будем иметь An(s)^14—An^l{s). (15) Отсюда Л"(s) - TT^F Лп-г (s) = TT^F Лв~3 (s) = ТГ^Р1"' Б2
Отметим теперь, что fx = 1 при всех г, и поэтому оо со 1 Следовательно,; 1-s" г«=0 г=0 Л (1-4 Из равенства (10) следует, что fr = Гг Лп^= п1*п- (16) П р и м е р 13. Найдем все члены последовательности Фибо- наччи, которая задается по закону J3o = l, Вх =2, (17) ВЛ = Бя-1.+ 5я-2 (при л>2). .(18) Рассмотрим функцию В (S) = ^ 5Я5» л=0 Умножив обе части равенства (18) на sn и сложив затем все полученные равенства, будем иметь оо сю оо ^В/ = ^ВЯ-/-' + ^Вл-/-2. (19) «=2 п>=2 п=2 Принимая во внимание то, что оо £ gns" = В (s) - 1 - 2s, rt=2 оо оо £ Bn-lSn~l = £ Bmsm = В (s)- 1 - (где га=п- 1), п=2 т=»1 оо оо £ Bn-2sn~2 = 2 Bps' = 5 (s) (где р = п - 2), п*»2 р=0 получим из равенства (19) В (s) - 1 - 2s = s [В (s) - 1] + s2£ (5), откуда *«-т=£Ь-- (20) Вычислив коэффициент при s71 в разложении функции В {s) в ряд, найдем Вп. 53
Разложим в ряд функцию 1 1 1—-S-—S2 (S— Si) (S — S2) ' где -1 —V6 -1 + Y5 51 = 2 ' S2 : Имеем 1 / 1 (S — Si) (5 — S2) \S~Si S 1 / 1 !_)_J — s2 J s2 — Si V5 /J 1 1 - 1 \- I Sl 1 _ J- S2 j £_ Г \ sx s2 J Используя равенство будем иметь 1-х я=0 Z*" Поэтому коэффициент при s" в разложении функции (20J равен Вп=~VT (ip" ~ 1р")+"VT ( 4" ~ ~Щ)' После упрощений получим формулу Замечание. Во многих задачах производящая функция является рациональной функцией, т. е. функцией вида л(*)= p(s) Q(s)' где P(s) и Q(s)—многочлены относительно s. В том случае, если многочлен Q(s) имеет лишь простые корни, можно указать про- стой метод разложения такой функции в ряд по степеням s. Допустим, что Q(s) — многочлен степени т, а степень много* члена P(s) меньше, чем степень Q(s) (этого всегда можно до- стигнуть, разделив P(s) на Q(s)). Тогда 54
Приведя к общему знаменателю дроби в правой части, получим в знаменателе многочлен Q(s) (допустим, что коэффициент при старшем члене Q(s) равен 1; это допущение не является ограни- чением), а в числителе — некоторый многочлен. Приравнивая коэффициенты этого многочлена соответствующим коэффициейтам многочлена P(s), можно подобрать Ah так, чтобы равенство (21) выполнялось при всех тех s, при которых оно имеет смысл. Иногда производящую функцию можно найти, не пользуясь рекуррентными соотношениями, а исходя из некоторых комбинат торных соображений. Пример 14. (Производящая функция для числа сочетаний.) Пусть аи а2, а3 — некоторые числа. Рассмотрим произведение (1 +ais) (1 +a2s) (1 + a3s). Перемножив и собрав коэффициенты при одинаковых степенях s, будем иметь (1 + ais) (1 + a2s) (1 + a^s) = = 1 + s (ai + a2 + a2) + s2 (a\a2 + aia3 + a2az) + sza\a2az — = 1 + Ais + A2s2 + Ass3. (22) Отметим, что число слагаемых в каждом коэффициенте Аг равно числу сочетаний из 3 по г. Например, выписав соответствующие индексы при ai в каждом слагаемом А% ((1,2), (1,3), (2,3)), получим все сочетания из трех чисел 1, 2, 3 по два. Будем считать, что в выражении (22) а4 = а* = аз = 1; тогда коэффициент при sr будет равен числу сочетаний из 3 по г. Следовательно, (1-f-s)^ является производящей функцией для числа сочетаний из трех предметов. Пример 15. Рассмотрим сочетания из трех предметов 1, 2, 3, причем 1, 2 могут встречаться не более двух раз, а 3 — не более одного раза. Рассмотрим произведение (l + a{s + ttjS2) (l + a2s + a\s*) (1 + ass) = = 1 + 5 (ax + a2 + a3) + s2 (a2{ + a{a2 + a{a3 + a2a3 -f af) + + s3 {a\a2 '+ a\a3 + axa\ + o,xa2a3 + а|аз) + + s4 (a\a\ + a2a2a3 + а^аЛ + s^a\a\a3 = = \+A{s + A2s2 + A3s* + A^ + Abs\ Опять же число слагаемых в каждом Аг равно числу всех воз- можных комбинаций из 3 предметов по г при сделанных выше ограничениях. Например, выписав соответствующие индексы в каждом слагаемом Л3, получим все возможные сочетания из трех чисел 1, 2, 3 по три: 112, ИЗ, 122, 123, 223. Поэтому при я4 = = а2 =' а3 = 1 каждый коэффициент Аг будет равен числу соот- ветствующих сочетаний. Следовательно, производящая функция числа всех сочетаний с указанными ограничениями равна (1 + S + S2) (1 + S + S2) (1 + S) = (1 + S + S2)2 (1 + s). Б5
Рассмотренные примеры дают представление о том, как на* писать производящую функцию для числа сочетаний при наличии других ограничений. Так, производящая функция для числа сочетаний из п пред- метов с повторениями при условии, что каждый предмет встре- чается любое число раз, равна (1+S + S2+ ... +sk+ Mif= (i^5)„» (23). Коэффициент при sr в разложении функции (23) равен (это следует из равенства (10)). Снова получили формулу Для числа сочетаний с повторениями. Производящая функция для числа сочетаний из п предметов по г при условии, что каждый предмет встречается по крайней мере 1 раз, равна (S + s2 + S3+...)n = _T-£Lr. Используя равенство (10), получим оо оо (i-s)« s LL^^S LL«+l^s * Положив n + i **= г, будем иметь oo oo : _==, V сг~пчг a V rn~ur Коэффициент при sr и есть искомое число сочетаний. Следова- тельно, число сочетаний из п предметов по г при условии, что каждый предмет встречается по крайней мере 1 раз, равно 0, если г < я, и равно C?Zi> если г ^ п. Пример 16. Пусть Ап — число целых неотрицательных ре- шений уравнения &i#i + k2x2 + ... + krxr = п, (24) где ki} k2, , •*♦, kr-— данные натуральные числа. Обозначим A (s) = £ Ans\ п=0 Легко видеть, что A{s) = (i-/00-V»)...(i-A)# 56
Запишем равенства 1 1 J_el+Sfc* + S2*,+ 1 шл\+8кГ+82кГ+ ., 1 kr 1 — s r Если перемножить их почленно, то показатели при степенях 5 будут иметь вид 11 2 2 "•" * * * ' ^ т т где все Хг получают натуральные значения (такой показатель по- лучится, если в правой части каждого из написанных равенств выбрать соответственно s 1 *, s 2 2, ..., s г г и перемножить их). Число всех возможных представлений п в выражении (24) как раз и будет коэффициентом при sn в том разложении, кото- рое получим после перемножения всех равенств. Рассмотрим следующую теорему о производящих функциях, которая является полезной при решении некоторых задач. Определение. Сверткой двух последовательностей \ап} и {Ьп} называется последовательность {сп}, общий член которой имеет вид c« = a(Ai + aA-i+ — +4bn-k+ ••• +flA <25) Теорема. Производящая функция свертки двух последова- тельностей равна произведению производящих функций этих по* следовательностей. Доказательство. Пусть {сп} — свертка последователь* ностей {ап} и {&n}, а оо оо оо A(s)=Yians», B(s)=£&„s«, C(S)=2C»S" /г=0 л=0 «=0 — производящие функции последовательностей {ап}> {Ьп}, {сп} со* ответственно. Требуется доказать, что С (s) = A (s) В ($). Перемножим два ряда сх> оо A(s)=]?ansn и В (s) = % bns". Коэффициент при s" в полученном произведении равен а0Ьп + аА-1+ •■■ +akbn-k+ ■■■ +аЛ Следовательно, A(s)B(s)=*C(s). 67
Для иллюстрации теоремы рассмотрим следующий пример. Пример 17. На окружности взято 2п точек. Сколькими способами можно соединить попарно эти точки п хордами, не пересекающимися внутри круга? Обозначим через ап число способов, которыми можно раз- бить на пары 2п точек, взятых на окружности, так, чтобы хорды, соединяющие эти пары точек, не пересекались. Обозначим точки буквами в таком порядке, в каком они размещены на окружно- сти: Ai, А2, ..., Л2п. Точку Ai можно соединить лишь с одной из точек Л2, Л4, ..., Л2п, в противном случае по каждую сторону от хорды, выходящей из Ль будет размещено нечетное число точек и, значит, при попарном соединении точек между собой по крайней мере одна хорда пересечет хорду, выходящую из Ль Определим, сколько существует различных способов соедине- ния точек, при которых Л4 соединена с Л2&. По одну сторону от AiA2k размещено 2& —2 точек; их можно соединить попарно cth-i способами. По другую сторону от А^Агк размещено 2(п — k) то- чек; их можно соединить попарно ап_ь способами. Комбинируя каждый из dh-i способов соединения точек Л2, ..., A2k-i с каж- дым из ctn-h способов соединения точек A2k+u ...» Мп, получим, что число таких способов попарного соединения, при которых Ai соединено с Л2а, равно ak-icin-k- Но к может принимать значе- ния 1, 2, ..., п, и поэтому ап==ап-1 + ап-2а1+ •'• +V-A-1+ •'• +aian~2 + an~V Везьмем ао = 1, и пусть оо Л(5)=5>П5* — производящая функция последовательности {ап}. Тогда an = aoan-i + aian-2+ •" +akan-k+ ••• +ап-1ао> где п ^ 1. Умножим обе части предыдущего равенства на sn И просуммируем по п. Тогда оо оо ]Г a„s" = s£ sn~l (a0an-i + «ifl/i-2 + ... +%-i«o). Поскольку оо v %ап8п=*А(8)-и то, применяя теорему о свертке, имеем A (s) - 1 = sA2 (5). (26) Решая квадратное уравнение относительно A(s), получим A(s) = l±^EE. (27) 58
Поскольку Л(0)= 1, так как а0 = 1, то в формуле (27) нужно выбрать знак минус. Примем во внимание, что l-VT^T^ 1 + Vl - 4s nm • =1 и jim _ — oo# s->o 2s 5_>о 2s Следовательно, производящая функция последовательности {ап} равна ^ 1 — Vl — 4s A(s)= 1 У21 (28) Теперь остается найти коэффициент при sn в разложении функ- ции (28). Для этого воспользуемся формулой (7). Согласно (7) будем иметь (1 - 4.)"» -1+£ ^(т-О-Ст^+О М)» 4V= = 1-Ec^id-rsft- <29) Отсюда, согласно (28), Л(с)- l-VF^ls 1 yi ft 1 fe-l_ Л(5)"" 2^^~ 2Z-/ С2*Ж"=П~5 ~ /5 = 1 оо - Т Z с^ агЬ"s" (где " = * " !>- Следовательно, -2/г+2 2/1 + 1 /г=0 п J__ рп+1 * * f>tt а/г - 2 С2«+2 2я + 1 — Л + 1 2rt* § И. МЕТОД ВКЛЮЧЕНИЯ И ИСКЛЮЧЕНИЯ Пусть N (А) —число элементов множества Л. В § 2 была установлена формула N(AX[)A2[} ... [}Aa) = N{Ax)+ ... +N{An)- -{N(AinA2) + N(Al[}A3)+ ... ... +N(Al(]An)+ ... + N{Aa-l(\An)} + + {^(Л1ПЛПЛ3) + ^(Л1ПЛ2ПЛ)+ ... ... Ч-А^Л^ПА^НА,)}- ... ... +{-l)n-lN{Al[)A2() ... flAi-ifM*). (1) 59
Метод подсчета по формуле (1), состоящий в по- очередном сложении и вычитании, называется мето- дом включения и исключения. Равенство (1) можно записать в виде N(AX[) ... U^) = = Z NiAi)- £ N(Aix(]Ai2) + 1 < i 1 < п К i1 < i2 < п + Е NiAi^AtMA^- ... ... +(-1)я"1 I ^ОМ^П ... ПЛЛ), где Z Л^ЛЛ'зП ... пл-,) — сумма всех тех N(At1 f]AinJ] ... f]А^), У которых индексы /ь ,.., ik удовлетворяют неравенству 1 < i\ <i2< ... < ik < п. Например, Z # И/, П Л,2) = N (Ах П 4>) + ЛГ (i*i П ДО + + ^(Л1ПЛ4) + ^(Л2ПЛ3) + ЛГ(Л2ПЛ4) + ^ИзПЛ). Равенство (1) доказано в § 2 с помощью метода ма- тематической индукции. Рассмотрим еще одно доказа- тельство этого важного равенства. Чтобы доказать (1), достаточно доказать, что ка- ждый элемент из Ai\J...[)An учитывается в правой части равенства (1) ровно один раз. Рассмотрим про- извольный элемент а из А\ U ... U Ап и допустим, что а входит ровно в m множеств Лг-. Тогда элемент а под- считывается в правой части (1) m ^m~T ^чп ••• i\ *■) ^m раз. Но /-.1 г»2 _1_/°3 _1_ ( \\m-\ f>m L,m — L,m-f L,m ... ~Т \ l) ^rn — = i-[i-cL + c2m-...+(-irc] = = 1-(1-1Г = 1. 60
Следовательно, каждый элемент а из А\ U ... U Ап учитывается в правой части равенства (1) один раз. Это и доказывает равенство (1). Пример 1. Рассматриваются все перестановки п чисел 1, 2, ..., /г. Пусть Dn — число тех перестано- вок, в которых по крайней мере одно число стоит на своем месте. Найти Dn. Обозначим через Ак совокупность тех перестано- вок, в которых на &-м месте стоит k. Тогда Dn = N(A{[}A2[} ... \}Ап). Множество Aix П ... {\Aik содержит те перестанов- ки, в которых на местах iu ..., ik стоят числа t'i, ..♦ ..., ik, а на других местах — остальные n — k чисел, упорядоченные произвольно. Поэтому N{Ah[\ ... (\Aik) = (n-k)l, а £ N(Al{(] ... ()Aik) = Ckn(n-k)\=^. l<l1<i2<...<ik<n Из равенства (1) следует, что лкли... U4,)= = "!(тг-4-+-г--+(-1)""1^)- Пример 2. Пусть аь .,,, ап — взаимно простые натуральные числа, а N— некоторое натуральное чис- ло. Найти число натуральных чисел, не превышаю- щих Я и не делящихся ни на одно из чисел а\, . .« Пусть А{ — множество натуральных чисел, не пре- вышающих N и делящихся на а*. Тогда количество чисел, делящихся по крайней мере на одно из чисел #ь *.*э ^п, равно N(AXU ..• иЛЛ). Очевидно, где [л:] — наибольшее целое число, не превосходящее х. 61
Множество Aii(]Ai2(] ... ПМк — это множество тех чисел, которые делятся на ai{ ... aik. Поскольку числа ai{, ...,' aik взаимно простые, то В силу равенства (1) количество чисел, не превы- шающих N и делящихся по крайней мере на одно из чисел аи *. •, «п» равно *(л,и...ил„>=1[Х]- £[£] + + £ t^]-•■■•+<-«■-■ fc^: Количество чисел, не превышающих Л/" и которые не делятся ни на одно из чисел аи ».., ап, равно N-N&U ... [}Ап) = - Е fc£r]+ - +<-""[^У- <2> Пример 3. Пусть п — натуральное число, разло- жение которого на простые множители имеет вид \ (ри «*,, ph — простые числа), а ц)(п)—число состав- ных натуральных чисел, не превышающих п и взаим* но простых с п. Доказать, что (Функция ф(п) называется функцией Эйлера.) 62
Числа, взаимно простые с /г, не делятся ни на одно из чисел ри ..., ph. Поэтому в силу (2) <?(п)=п- £ -f- + £ -£--... ККк l l<i,<h<k 'l н ■Рк -0-i)0-i)-('-K> Рассмотрим теперь еще один способ применения метода включения и исключения. Теорема. Пусть N[m){A\\J ... UЛЛ) —- число эле- ментов, входящих ровно в m множеств из Аи ..., Ап. Тогда NimiiAiU ... UAn) = = CZ Z N(Ah(\ ... r)Aim)- -C+I I Лг(Л-П...ПЛш+1) + ... 1<*,<*2<---<*т+1<д ...+(-1)я"тС? Z iV^n.-.n^J. (3) Доказательство. Пусть a — произвольный элемент, входящий в k множеств из множеств Аи .-* ..., Ап. Для доказательства теоремы достаточно по- казать, что элемент а учитывается в правой части равенства (3) один раз, если k = га,(и не учитывается ни разу, если кфш. Если k <. т, то а не учиты- вается в сумме (3) ни разу; если k = га, то а учиты- вается в (3) один раз, так как а входит лишь в одно из множеств вида Л^ П ... f] Aik. Пусть теперь k > га. Элемент а учитывается С™ раз в сумме Z kN(A{l(]...(]A{m), С%+1 раз в сумме £ N(Ah П ... П Л*да+1), . Kil<t2<"'<im+\<k и т. д. С\ раз в сумме Z #0M ... л л,,). 63
В остальных суммах в правой части (3) элемент а не учитывается, так как он входит лишь в k мно- жеств. Таким образом, а учитывается в (3) гтпт пт пт + \ \ л>т пт+2 ... +(-l)k-mC%Ckk (4) раз. Остается доказать, что эта сумма равна нулю. Действительно, поскольку Ьг bk — m\{r-m)\ r\(k-r)\ — C* Lk-m> то сумма (4) при k > m равна Cm (r>k—m /->k—m—\ t • / i\&—m/~»0 \ k \bk-m — ^k-m + ... +^— lj bfc-mj = = C£(1 — l)*~m = 0. .Пример 4. Найти число всех перестановок чи- сел I, 2, ..., п, в которых m чисел стоят на своих местах. Пусть А{ — множество тех перестановок, в кото- рых на i-м месте стоит и Тогда имеем N[m](AxU ... U4) = CC(«-m)!- - C2+xCFl (n-m- 1)! + ...+(_ 1Г m&nn = ml L П. 2! 3!^ "• T* *' (n~m)!j m! L2! 3! ^ V" ^ K l} (n — m)\y § 12. МЕТОД ТРАЕКТОРИЙ Для многих комбинаторных задач можно указать такую геометрическую интерпретацию, которая сво- дит задачу к подсчету числа путей (траекторий), об- ладающих определенным свойство^. В этом и состоит метод траекторий1). В § 3 мы пользовались методом ]) Термин «метод траекторий» ввел J3. В. Гнеденко. В 1951-^ 1954 гг. Б. В. Гнеденко и его ученики (В. С. Королюк, В. С. Ми- халевич, Е. Л. Рвачёва (Ющенко)) успешно применяли метод траекторий при решении некоторых важных задач математиче* ской статистики. ... ■ 64
траекторий при доказательстве некоторых биномиаль- ных тождеств. Преимуществом этого метода является чрезвычайная наглядность. Задача 1. Возле кассы собралось т + п чело- век, причем п из них имеют монеты стоимостью 50 коп., а другие т имеют лишь по рублю. Сначала в кассе нет денег, билет стоит 50 коп. Сколько всего имеется способов размещения т-\-п покупателей в очереди так, чтобы ни один покупатель не ждал сда- чи (т ^ /г)? Допустим, что покупатели расположены в очереди некоторым образом. Пусть Г 1, если z-й покупатель имеет 50 коп., V \ —1, если i-й покупатель имеет рубль. Рассмотрим . S* = 8i+ ••• +8*. (1) Вдумчивый читатель уже заметил, что Sh является разностью между количеством 50-копеечных монет и количеством рублей, которые поданы в кассу первьь ми k покупателями. t _J \ \ 4» \ К 9»»- (п=4>гп=2) й'6 Рис. 8. Рассмотрим теперь систему координат XOY. По- строим в ней точки Ak = {k;sk) (k=\, ..., m'+n) и рассмотрим ломаную, соединяющую точку О =! = (0;0) с точкой Ап+т = {т + щ п — т) и проходя- щую через точки Ль ..., Am+n-i (рис. 8). Будем на- зывать такую ломаную траекторией, соответствующей 65
данному способу размещения покупателей в очереди. Каждая траектория состоит из m + n отрезков, й ИЗ которых направлены вверх, а т направлены вниз. Если указать номера тех отрезков, которые направле- ны вверх, то тем самым траектория будет полностью определена. Следовательно, общее число траекторий равно Сп+т- Траектории, соответствующие тем способам раз- мещения покупателей, при которых ни один покупа- тель не ждет сдачи, не пересекают прямую у =—1. Действительно, если для некоторого k Sh-i = О, sk = = — 1, то это означает, что первые k— 1 покупателей подали в кассу одинаковое количество полтинников и рублей, а &-й покупатель подал рубль и вынужден ожидать сдачу. Определим число траекторий, пересекающих пря- мую у = —-1. Поставим в соответствие каждой траек- тории Г, пересекающей прямую у = — 1 или имеющей с ней общую точку, новую траекторию Т по следую- щему правилу: до первой точки пересечения с прямой у = — 1 траектория V совпадает с Г, а далее V яв- ляется симметричным отображением траектории Г относительно прямой у = — 1 (на рис. 8 траектория V обозначена пунктирной линией). Все траектории V заканчиваются в точке Л^+„ = (т + п; т — п — 2), являющейся симметричным отображением точки Ат+п относительно прямой у = —1. Установленное соответствие является взаимно одозначным, поэтому число траекторий, пересекающих прямую у = — 1, равно числу ломаных, соединяющих точки О и А'т+п. Это число легко подсчитать: если ломаная состоит из у отрезков, направленных вниз, и х отрезков, направ- ленных вверх, то х + у = т-\-п, у — х = п + 2 — т, откуда */ = /г-{-1. Таким образом, число траекторий, пересекающих прямую г/ = —1, равно Сй£+л» Иско- мое число траекторий равно Рассмотренная задача имеет важное значение в математической статистике, в частности в теории ста- 66
тистического контроля качества продукции. С ней также тесно связана так называемая задача о балло- тировании, которую еще в 1887 г. рассматривал из- вестный французский математик Бертран. Недавно стало известно, что эта задача имеет интересные применения при изучении некоторых случайных про- цессов. Задача 2. (Задача о баллотировании.) Канди- дат А собрал на выборах а голосов, кандидат В со- брал Ь голосов (а>Ь). Избиратели голосовали по- следовательно. Сколько существует таких способов подачи голосов, при которых А всегда будет впере- ди В по количеству поданных за него голосов? Пусть Ei = +1, если 1-й голос подан за Л, и е* = = •—1, если t-й голос подан за В. Возьмем sk — = 8l _jl # ф # _(-. Sk и рассмотрим в системе координат XOY ломаную, соединяющую точки О, (l;$i), ... ..., (k;sh), ..., (a + b; sa+b) (рис. 9). Очевидно, Y\ О Рис. 9. sa+b = a — b. Каждому способу подачи голосов соот- ветствует определенная ломаная линия (траектория), соединяющая точки О и (а + Ь; а — b). Траектория состоит из а + Ъ отрезков, причем а из них направле- ны вверх. Поэтому общее число траекторий равно Са+ь- Кандидат А всегда будет впереди В, если соот- ветствующая траектория проходит через точку (1; 1) (первый голос должен быть подан за А) и не пере- секает ось ОХ. Число таких траекторий может быть подсчитано по формуле (2), где следует взять п = = а — 1, m = b. Следовательно, искомое число *~х 67
способов подачи голосов равно па-\ а— 1 + 1 — Ь a~b па /о\ Рассмотренные задачи показывают, насколько по- лезной может быть интерпретация задачи в терминах траекторий. Рассмотрим теперь некоторые общие утверждения, касающиеся подсчета числа траекторий. Пусть х > 0 и у— целые числа. Траекторией из начала координат в точку (х\ у) будем называть ло- маную, соединяющую точки О, (l;si), ,'.., {k\ sk), ... .. •, (*; $х), где f + 1, St — si-l=ei = ^ _ j sx*=y. (4) Пусть M^y — число всех траекторий, сооединяю- щих точку (0; 0) с точкой (х;у). Имеют местр сле- дующие теоремы. Теорема 1.. Nx,y = р±»),(^),' если числа х и у — одинаковой четности, и Nx,y = 0, если х и у — разной четности. Доказательство. Допустим, что траектория состоит из р отрезков, направленных вверх, и q от- резков, направленных вниз (это означает, что среди чисел 8ь ..., &х Р чисел равны + 1, a q чисел рав* ны —1). Тогда 'p + q = x, p — q = y, откуда х + у х — у (поскольку р и q — целые числа, х и у должны быть числами одинаковой четности). Так как траектория 68
полностью определяется, если указать, какие отрезки направлены вверх, общее число траекторий из точ- ки О в точку (х; у) равно AT _г<*+0>/2 Х\ Теорема 2. (Принцип зеркального отображе- ния.) Пусть А =(а; а), В ===(&; Р) — точки с целочис- ленными координатами, причем Ь > а ^ 0, а > О, р > 0, а А' = (а; —-а)—точка, симметричная А от- носительно оси ОХ. Тогда число тех траекторий из А в В, которые пересекают ось ОХ или имеют с ней об- щую точку, равно числу траекторий из А' в В. Доказательство. Каждой траектории Т из Л в В, пересекающей ось ОХ или имеющей с ней общую точку, поставим в соответствие траекторию из Л' в В по следующему правилу (рис. 10): берем участок У О А' Рис. 10. траектории Т до первой точки встречи с осью ОХ и симметрично отображаем его относительно оси ОХ, а далее траектории Г и Г7 совпадают. Таким образом, каждой траектории Т из А в В, пересекающей ось ОХ, соответствует определенная траектория Г' из А' в В. Наоборот, каждой траектории из А' в В соответ- ствует одна и только одна траектория из А в В, пере- секающая ось ОХ (берем участок траектории из Аг в В до первой встречи с осью ОХ и симметрично ото- бражаем его относительно оси ОХ). Следовательно, между множеством траекторий из Л в В, пересекаю- щих ось ОХ или имеющих с ней общую точку, и \ А / / В 69
множеством всех траекторий из 'А' в В установлено взаимно однозначное соответствие. Теорема дока- зана. Теорема 3. Пусть х > 0, у > 0. Тогда число траекторий из О в (х;у), не имеющих вершин на оси ОХ (кроме точки О), равно х "Х'У' До казательство. Все траектории, соединяющие точ- ку О с точкой (х; у) и не пе- ресекающие ось ОХ, проходят Яг через точку А = (\;\) (рис. 11). Общее число траек- торий, ведущих из Л в В, рав- но Nx-\fy-\. Общее число тра- екторий, ведущих из Л в В и пересекающих ось ОХ, равно, согласно теореме 2, числу траекторий, ведущих из А! в В, т. е. Nx-\iy+u Следовательно, искомое чис- ло траекторий равно У> 0< \ Л —с )— \ feb Рис. II N х-1, у-\ — N х-\,у+\ '■ (*-!)! х\ №)№)■ х,у Теорема доказана. Установим теперь несколько свойств траекторий, соединяющих точку О с точкой (2/г; 0) на оси ОХ Пусть -2/1 : П+\ Сп 2л* Теорема 4. Среди С^п траекторий, соединяю- щих точку О с точкой (2п; 0), существует а) ровно L2n~2 траекторий, лежащих выше оси ОХ и не имеющих общих точек с ОХ, кроме точек О и (2/г;0); 70
б) ровно L^n траекторий, не имеющих вершин ни- же оси ОХ. Доказательство, а) Все траектории, соеди- няющие О с (2/г;0), лежащие выше оси ОХ и не имеющие других общих точек с осью ОХ, обязатель- но проходят через точку (2п— 1, 1). Согласно теоре- ме 3 число траекторий, соединяющих О с (2/г-— 1; 1) и не пересекающих ось ОХ, равно ^ZTf^-b 1 = з^ГТ С£г-1 =- СгЛ"Л = £2/1-2. б) Рассмотрим траекторию, соединяющую О с М(2п\0) и не имеющую вершин ниже оси ОХ (рис. 12). Добавим еще один отрезок, соединяю- у щий О с Oi(—1;—1). 7 Примем 0\ за новое на- чало системы координат X\0\Y\. В новой системе точка М имеет кобрди- # наты (2/г+1;1), а точка ' О — координаты (1; 1). Число траекторий, соеди- няющих точку О с точкой М и не имеющих вершин ниже оси ОХ, равно числу траекторий, соединяющих Oj с М и лежащих выше оси 0\Х\. Последнее число в силу теоремы 3 равно 2^рт • N**+*- * = "2^+Т C^+I = Т+Т С^ = L2n' Теорема доказана. Рассмотрим пример применения доказанных выше теорем. Задача 3. Решим задачу, рассмотренную выше (задача 1), допуская, что перед началом работы в кассе имеется р монет стоимостью 50 коп. Очевидно, задача сводится к подсчету числа траек- торий из точки О в точку (пг+п; п — пг), не пересе-. кающих прямую г/= --(/?+1). Согласно теореме 2 число тех траекторий, которые пересекают эту пря- мую, равно числу траекторий из точки (0; — 2(р -f: 1)) п 71
в точку (п + щ; n — m), т. е. СЙ-^1 ^Cm+Г1. Иско- мое число траекторий равно Cm f>m—p—\ УПРАЖНЕНИЯ К § 9—12 1. На какое наибольшее число частей могут разделить пло- скость п прямых? 2. На какое наибольшее число частей могут разделить про* странство п плоскостей? 3. На какое наибольшее число частей могут разделить про* странство п сфер? 4. Сколькими способами г различных предметов можно раз- местить в п ящиках? 5. Сколькими способами г пассажиров могут разместиться в п вагонах поезда? 6. Пусть А(г,п) число таких способов размещения г различ- ных предметов в п ящиках (А (г, п) = 0, если г < п), при кото- рых нет пустых ящиков. Доказать, что Л (г, л+1) = £ C*A(r-kt п). Как следствие установить, что А (г, п) = ^{-\)1;с1п{п-1)\ 7. Доказать, что число способов размещения г различных предметов в п ящиках, при которых ровно т ящиков пустые, равно п—т C™A(r, n-m) = CZY, (-^С1п_т(п-т-1)\ 1=0 г I 8. Сколько существует способов размещения г пассажиров в п вагонах поезда, при которых ровно т вагонов будут свободны? 9. Используя результат задачи 6, вычислить сумму Вычислить производящие функции последовательностей! 10. __Г1 при 0<n<iV, \ 0 при n>N. 11. _ Г qn при 0<я<#, ап~~\ о при n>N. Производящая функция последовательности \ап} равна /4(s). Вычислить производящие функции последовательностей; 72
.2. fc,-{0 "' при n<r, при я>г. 13. bri = £а«. 14. &„ = ап + Ь. 15. bn = ап + an-i + ... + а0- 16. 6а ~ап + an-ia + л^-гя2 + ... + а0ап. 17. 6а = а2п< 18. Сколькими способами выпуклый я-угольник можно раз- бить на треугольники диагоналями, не пересекающимися внутри «-угольника? 19. Вычислить а) ор(ЮО); б) ф(1000); б) <р{р), где р — про- стое число. 20. Каждый читатель библиотеки прочитал по крайней мере одну книгу из этой библиотеки. О любых k книгах из библиотеки (1 ^ k ^ п, п — число книг в библиотеке) можно сказать, сколь- ко читателей прочитали все эти книги. Как по этим данным уста- новить, сколько читателей в библиотеке? 21. Используя метод включения и исключения, найти число способов размещения г различных предметов в п ящиках, при которых нет пустых ящиков. 22. Используя метод включения и исключения, найти число способов размещения г различных предметов в п ящиках, при которых ровно т ящиков являются пустыми. 23. Пусть Nm(Au ..., Ап)—число тех элементов, которые входят по крайней мере в т из множеств А и ..., Ап- Доказать, что Nm(Al,..., Л„)= £ N(Ai{(\ ... ЛЛ/J- - Ktl<t2< ... <im<n -cr1 ' S ^,n ...пл/т+1) + lm+\ <n + СЙ I ^(АНП ... (\Atm+,)- <im+2<n \)"-mcZ-i L м(АчП ••• (\лы). 24. Найти число способов размещения 8 ладей на шахматной доске так, чтобы они не могли бить друг друга и чтобы ни одна из них не стояла на белой главной диагонали. 25. Будем называть траекторией из точки (0; 0) в точку (х; у) ломаную, соединяющую точки (0;0), (l;si), ..*, (k;sk)t где ..-,..-{J Sb=*t/. 73
Пусть Тх, »'— число траекторий из (0; 0J в \х\ у). Доказать, что а) ?х, у = б) Пусть Л=(а;а), £ =(&; Р)-~точки с целочисленными координатами, причем Ь > л > 0, ее > 0, fr>0, а Л'=(я; — а) — точка, симметричная А относительно оси ОХ. Доказать, что число траекторий из А в В равно числу траекторий из Л' в В. в) Пусть х > 0, у > 0. Доказать, что число всех траекторий из (0; 0) в (х; //), не имеющих вершин на оси ОХ, равно Tx~\t y-i —- £*-i, #+!• г} Доказать, что среди Гп,б траекторий, соединяющих (0; 0J с (я; 0), существует: 1) ровно Ln-i = Гп-2, о*— ^п-2,2 траекторий, не имеющих вершин на оси ОХ, кроме крайних точек (0; 0) и (/г; 0); 2) ровно Ln+i *= Тп,о — Тп,2 траекторий, не пересекающих ось ОХ. 26. а) Доказать, что, среди любых шести лиц найдется или трое знакомых или трое незнакомых. - б) Если 17 ученых переписываются друг с другом по трем различным научным темам, причем каждая пара ученых ведет переписку лишь по одной теме, то всегда найдутся трое ученых, переписывающихся по одной и той же теме. Доказать это. в) Пусть ап — последовательность натуральных чисел, обра- зованная по следующему закону: аг=2 ап+] = (я + 1)ап + 1. Предположим, что имеется ап + I точек, никакие три из которых не лежат на одной прямой. Каждые две точки соединены отрез- ком одного из п цветов. Доказать, что существует треугольник с вершинами в данных точках, стороны которого имеют один и тот же цвет. г) Доказать, что ял<[е«л!], где в — основание натуральных логарифмов. 27. Рассмотрим на плоскости множество точек, никакие три из которых не лежат на одной прямой; соединим каждые две точки отрезком одного из цветов — красного или черного. Пусть l(k,m)—наименьшее натуральное число такое, что среди любых l(kym) точек найдется или к точек, соединенных красными отрез* ками, или m точек, соединенных черными отрезками, Доказать, что: а) l(k. т)</(&-1, m) + l{kt m~ 1); б) l(k,m)^Ckk+lm_2.
ОТВЕТЫ, УКАЗАНИЯ, РЕШЕНИЯ § I 1.49; 42. 5. 109-8.7-6-5 =* 151 200. 6. 18000. 7. а) тп; б) (m+l)(/i+l). 8. 20. 9. 55. 10. 1080, 11. 60. 12. 900. 17, б) (ai + 1) ... (ап + О- 18. 40. 19. 60. 20. Все таблицы, имеющие указанное в условии задачи свой- ство, можно составить так. Всюду, кроме последней строки и по- следнего столбца, произвольно выписываем +1 и —1. Это можно сделать 2^m~1^n~i) способами. Пусть р— произведение всех выпи- санных чисел. Теперь в каждой из первых т—1 строк на пере- сечении с п-и столбцом выписываем +1 или —1 так, чтобы произведение чисел во всей строке было равно 1. Обозначим про- изведение чисел, которые будут выписаны в п-м столбце, через х. Теперь в каждом из первых п— 1 столбцов на пересечении с т-й строкой выпишем также +1 или —1 так, чтобы произведение в столбце было равно 1. Произведение чисел, которые будут вы- писаны в т-й строке, обозначим через у. Заметим, что х и у имеют одинаковые знаки. Действительно, рх = 1, ру = 1, и по- этому р2ху = 1, и, значит, ху >» 0. Выпишем на пересечении т-й строки и п-го столбца число 1 с тем же знаком, который имеют х и у. Составили таблицу, имеющую указанное свойство. Число всех таких таблиц равно. 2(n-1Hm-1). 5, 40. 6. 6; 14. 7, 20. * Г2 — п(п—\) §2 §3 4, а) С2п, б) Съп. в) Будем проводить прямые последова- тельно одну за другой. Заметим, что если проводить k-ю пря- мую, то общее количество частей плоскости увеличится на (к— 1) + 1, где k— 1 — количество точек пересечения этой пря- мой с ранее проведенными прямыми. Отсюда следует, что если провести все п прямых, то общее количество частей плоскости увеличится на количество всех точек пересечения (их будет С^) плюс количество самих прямых. Вначале была одна часть (вся плоскость). Поэтому после. проведения п прямых получим 75
1 + С\ + п = (я2 + п + 2)/2 частей, г] Представим себе, что мы построили окружность, охватывающую все ограниченные части плоскости. Из этой окружности будет выходить 2/г лучей, которые разделят внешность окружности на 2/г частей. Таким образом, количество неограниченных частей равно 2п. Следовательно, огра- ниченных частей будет 1 + С2 — п = {п2 — Зя + 2)/2. 5. С^=126. 6. С|0 = 210. 7. Какие бы т — 1 членов комиссии ни собрались, должен найтись замок, который они не могут открыть, но ключ от этого замка имеется у каждого из остальных п — т + 1 членов комис- сии (появление кого-нибудь из которых дает возможность от- крыть сейф). Поэтому число замков равно С™~\ а число ключей равно (/i — m+ 1)С™-1. 9. Если не проведено ни одной диагонали, имеем одну часть. Будем последовательно проводить диагонали. Заметим, что после проведения каждой диагонали число частей увеличивается на еди- ницу плюс количество точек пересечения с теми диагоналями, ко- торые уже проведены. Поэтому число частей, которые получаются после проведения всех диагоналей, равно 1 плюс число точек пе- ресечения плюс число всех диагоналей. Если никакие 3 диагонали не пересекаются в одной точке, число точек пересечения равно Сп (см. задачу 4 в § 3). Число диагоналей равно п(п — 3)/2, следо- вательно, . 4 , п (п — 3) __ (п —\)(п — 2) (п2 — Зп + 12) 1 "г Ln + 2 """ 24 §8 1. Воспользоваться формулой Ckn+l = Скп + С^""1. Ckn+l n-k n-'k 2. Имеем г—= ; поэтому при >1 имеем С\ k + Г к + 1 Сп+1> Сп> а ПРИ ТТТ < * ИМееМ Сп+1<Сп- Из первого усло- вия имеем k < —-—, а из второго k > —-—. Гаким образом, биномиальные коэффициенты сначала возрастают, а затем убы- вают. Если я—нечетное число (п = 2т + 1), то наибольших би- номиальных коэффициентов два: С™т+ j = С^+ v Если же п — четное (п = 2т), то наибольшим будет коэффициент С™т. 3. п = 17. 4. 26. 6. 210. 7. „ • nt . гг. /г! г! (п — /г — г)! о v д,А I? я- п(п— \)(п — 2) 8. Коэффициент при *17 равен 1{2!(„_3)1в 2 ' гак как 17 = 5 + 5 + 7. Коэффициент при х1* равен нулю. 9. Надо воспользоваться соображениями, аналогичными тем, которые использованы при доказательстве равенства (2) в п. 3.1. 11. Положить в равенстве (3) (п. 8.2) ах == ... = ак = 1. 76
12. Пусть 1 ^ k ^ р — 1. Имеем nk_ р(р-\) ... (p-fe+D Lp - . . Поскольку р — простое число, р не делится на kl Поэтому (р — 1) ... (р —k + t) делится на k\, а значит, С^ делится на р. 13. При а = 1 теорема справедлива. Допустим, что ар — а делится на р, и докажем, что тогда (а+\)Р — (а + 1) делится на р. Действительно, (a+l)^-(a+l)as = (ap~a) + C],>-I + c2aP-2+ ... +^-2^ + 0^-^ делится на р, поскольку ар — а делится на р по предположению, а Ср (1 <!& s^p-- 1) делится на р (см. задачу 12). 14. Применив формулу бинома Ньютона, найдем, что — целое число. Поскольку — 1 < < (2— V5 ) < 0 (так как р — нечетное), то [(2 + V5)р] = (2 + V6)P + (2 - V6 У = ==2(2р + с22р-25 + С^-452+ ... +С^-12.5~Т~). Из этого равенства, используя задачу 12, найдем, что [(2+У5) ] — — 2Р+1 делится на р. 15. Использовать равенство С^+1 = Скп + Скп~{ и метод мате- матической индукции. 16. Поскольку £+1 c«-c«+l> то —jtt(c^« + c^>+ - +с^1)=ттг(2"+'-1)- 17. Использовать равенство kC^ = nC^Z\» 18. Использовать равенство &С^==гсС^~[. 19. Рассмотреть (1 — 1)л. 20. Рассмотрим все ^-элементные подмножества множества {1, ..., п}. Разобьем их на классы Tk-u Th, ..., Тп-и отнеся к 'классу Тт те подмножества, для которых максимальная раз- ность двух элементов равна т. Будем считать, что элементы всех рассматриваемых подмножеств упорядочены согласно их величи- не. Каждое подмножество, входящее в Тт, начинается с некото- 77
рого I [i = 1, ..., n — m), а заканчивается t + m, остальные к — 2 элемента выбираются произвольно из чисел i+l, ... ...» i + m—1 (это можно сделать C^l^ способами). Следова- тельно, Тт состоит из (п — т) С^^{ подмножеств. Поэтому с» = "Ё" (n-m)Ckm-_\. 21. Все упорядоченные ^-элементные подмножества множе- ства {1, ..., п} разбить на классы 7\_2, ,.., rn-2> отнеся к клас- су Тт те подмножества, у которых разность между предпослед- ним и первым элементами равна т. Подсчитать число элементов Тт (см. решение задачи 20). 22. Рассмотреть коэффициент при хк в сумме (\ + х)п+ ... +(1+*)*+"*. 23. Пусть вь ... ет — корни уравнения *ш — 1 = 0. Рас- смотрим сумму fc»0 Поскольку ь-r I i k-r __ / m если ^ ~" А Делится на т, 1 К ( если # — г не делится на т то Подставив вместо е^ его значение 2я£ , . . 2nk еь = cos h l sin и проделав вычисления получим ' т с- + <*+« + сгп+2т +'...- — V cos» -^ cos Si: - 2r) kn т 24. (—l)mC£Lj при /и<я— 1; 0 при m = /i. 25. 1 при п = 3&; 0 при п = 3k + \; — 1 при /г = 3k — 1 26. Вычислить коэффициент при я" в обеих частях равенства (I - х)п (I + х)п = (I - х2)п 27. 2^""L Указание- Рассмотреть (1 + \)п и (1—i)rt. 28. 2"""1. Указание. Рассмотреть (1 + \)п и (1—.1)*. Можно воспользоваться задачей 27. 73
29. 2»-2 + 2(e-2)/2Sos-5p-. 30. 2»-2-2<я-2,/2соз.-25-. 4 3,. ^|2" + 2соз("~4)Я' 1.1(2" + : 36. Табель успеваемости каждого ученика состоит из 2п граф, причем в каждой графе стоит 4 или 5. По условию задачи каж- дый ученик имеет одно и то же число k пятерок. Поскольку двух учеников с одинаковым табелем не существует, то число учеников не превышает С^^С^. 39. К каждой из t'i! перестановок элементов множества Ai присоединим любую из (п — ii)! перестановок элементов, не вхо- дящих в Ai. Проделаем то же самое для каждого из множеств А 2| ,«,, Л а. Тогда получим V (л - /i)! + У (* - У1 + — + V. (* - lk)[ перестановок элементов множества Q. Все эти перестановки раз* личны, так как Ait ..., Ah —- коллекция Шпернера. Поэтому V (* -h)1 + У (п - У1 + • • • + V (л - У1 >! Разделив обе части этого неравенства на n\t получим утвержде- ние задачи. 40. Так как С^<С^/2], то k - L-+ 1 ! <1 -[/г/21 откуда С1л/21. 'Л §9 — 12 18. Пусть ац — искомое число способов) A (s) -— производя- щая функция {ал}. Написать рекуррентные соотношения для ая и доказать, что A2 (s) — $Л (s) + s3 = 0, откуда Л (s) = Используя разложение (7) из § 10, получим 1 x>rt-2 л/s2 — 4s3 <-9 2л — 3 2rt~3' 26. в) Проведем доказательство методом математической ин- дукции. Для п=2 теорема верна (а2 + 1 =6). Предположим, что теорема верна для я = k, т. е. среди любых «а + 1 точек каждые две из которых соединены отрезком одного из к цветов, найдутся 3 точки, являющиеся вершинами одноцветного треугольника. 79
Пусть теперь есть ctk+i + 1 точек и каждые две точки соединены отрезком одного из k + 1 цветов. Рассмотрим одну из этих точек и обозначим ее через А. Из точки А выходит ah+i=(k + 1)ял+ 1 отрезков, каждый из которых окрашен одним из k + 1 цветов. Среди этих отрезков обязательно найдется ак + 1 отрезков од- ного цвета (будем называть этот цвет для определенности крас- ным). Выделим ак+ \ точс, соединенных с Л отрезками красного цвета. Если среди этих точек найдутся две, соединенные красным отрезком, то вместе с точкой А они образуют искомый треуголь- ник. Если же среди выделенных ак + 1 точек никакие две не соединены красным отрезком, то мы имеем ак + 1 точек, каждые две из которых соединены отрезком одного из k цветов. В силу предположения индукции среди них найдутся 3 точки, являю- щиеся вершинами одноцветного треугольника, что и требовалось. ЛИТЕРАТУРА Более подробное изложение некоторых вопросов комбинато- рики учащийся сможет найти в следующих книгах: ^ Виленкин, Комбинаторика, М., «Наука», 1969. арлбертсон, Математика и логика цифровых ус Просвещение», 1965. :: я л е н к и н, Популярная комбинаторика, М., «Нау- ка», ,:. 4. ТХ ж. Кемени, Д ж. С н е л л, Д ж. Томпсон, Введе- ние в конечную математику, М., ИЛ, 1963. 5. Ф. М о с т е л л е р, Р. Р у р к е, Д ж. Томас, Вероятность, М., «Мир», 1969. 6. В. Ф е л л е р, Введение в теорию вероятностей, т. I, М., «Мир», 1964. 7. Л. Я. Савельев, Комбинаторика и вероятность, Ново- сибирск, «Наука», 1975. Много интересных комбинаторных задач вы найдете в книге: 8. А. М. Я гл ом, И. М. Яглом, Неэлементарные задачи в элементарном изложении, М., Гостехиздат, 1954. ЛюбознателШый и настойчивый учащийся может ознакомить- ся с современным состояййек комбинаторики, изучая следующие монографии: 9. Г. Р а й з е р, Комбинаторная математика, М., «Мир», 1966. 10. М. Холл, Комбинаторика, М., «Мир», 1970. 11. Д ж. Р и о р д а н, Введение в комбинаторный анализ, М., ИЛ, 1963.
517.8 Е41 УДК 519 Элементы комбинаторики. Ежов И. И., Скоро- ход А. В., Ядренко М. И., перев. с укр. М, Глав- ная редакция физико-математической - литературы издательства «Наука», 1977, 80 стр. Комбинаторика — один из разделов математики, играющий важную роль при решении некоторых совре- менных проблем теории вероятностей, кибернетики, математической логики, теории чисел. Знание комбина- торики необходимо представителям самых разных спе- циальностей. С комбинаторными задачами приходится иметь дело физикам, химикам, биологам, лингвистам, специалистам по теории кодов. В книге изложены основ- ные понятия и методы комбинаторики. Изложение ма-* териала построено на систематическом использовании теоретико-множественных понятий. Книга рассчитана на учащихся средних школ и студентов младших курсов университетов. Она может быть полезна и для лиц, за- нимающихся комбинаторными расчетами. Илл, 12г библ, 12, Игорь Иванович Ежов Анатолий Владимирович Скороход Михаил Иосифович Ядренко ЭЛЕМЕНТЫ КОМБИНАТОРИКИ М., 1977 г., 80 стр. с илл. Редактор А. Ф. Лапко Техн. редактор Е. В. Морозова. Корректор Л. С. Сомова Сдано в набор 01.11.76. Подписано к печати 18.04.77. Бумага 84X108V^2 тип. №3. Физ. печ. л. 2,5. Усл. печ. л. 4,2. Уч.-изд. л. 4,07. Тираж 150000 экз, Т-08423. Цена книги 12 коп. Заказ № 375. Издательство «Наука» Главная редакция физико-математической литературы 117071, Москва, В-71, Ленинский проспект, 15 . Ордена Трудового Красного Знамени Ленинградская типография № 2 имени Евгении Соколовой Союзполиграфпрема при Государственном комитете Совета Министров СССР по делам издательств, полиграфии и книжной торговли^ 198052, Ленинград, Л-52, Измайловский проспект, 29^ 0П9П9—П74 © Главная редакция zuzuz иi<± g _ физико-математической литературы 053 (02Ь77 издательства «Наука», v ■' перевод на русский язык, 1977