Введение в прикладную комбинаторику, Кофман А. (984071), страница 3
Текст из файла (страница 3)
Покажем теперь, что Ю (и, г + 1) = М (и, г) + У (и — 1, г) + ... + й((1, г). (3.17) Для доказательства (3.17) предварительно представим каждую выборку таким образом, чтобы индексы аз ее компонент Ел шли в неубывающем порядке слева направо. Тогда число аз (г+ 1)-выборок, начинающихся единицей, равно л7(и, г), число (г+ 1)-выборок, начинающихся двойкой, равно Я(п — 1, «), число (г+ 1)-выборок, начинающихся и, равно д1(1, г) = 1.
Действуем по индукции. Пусть У(г) означает, что соотношение У(и, г) =Слч., ~ (3.18) выполняется. Покажем, что У(г) Ф У(г+1). (3.19) Для й < п имеем Л1(л, г) =С~ат,, (3.20) Учитывая хорошо известное соотношение (треугольник Паскаля) с',+,,=с",+,',— с,', „ (3.21) получаем 7т' (й, г) = СД, — Са+', ь (3. 22) Подставим (3.22) в (3.17)1 Н(п, г+ 1) = Лт (и, г) + й1 (и — 1, г) + ... (- й1(1, г) = т+~ Гч-1 ты г-! ге! = С.+г — Сле.
1+ Сл+г-1 — Сл ~'-з + ... + С„.,— т+~ тз-~ т+~ — с,+,+с„+,— сл„. (3.23) ') Это число обозначается также ( 13 Итак, У(а, г+ 1) =С"„+'„ (3.24) (3.28) (3.29) (3. 30) т. е. У(г+ 1) выполняется и (3.15) доказано. Например, если Е= [А, В, С, Р, Е], то можно образовать Сз+з ~ =Сг=7!/314! =35 следующих неупорядоченных 5-выбо- рок с повторением: [А, А, А], [А, А, В], [А, А, С], [А, А, 0] [А, А, Е], [А, В, В], [А, В, С], [А, С, 0], „ [Е, Е, Е]. Число неупорядоченных г-выборок без повторения (соче- тания без повторения).
Число упорядоченных г-выборок без повторения (г(а) в силу (3.11) (с учетом (3,16)) равно а! А„=, =г! С„. (3.25) Следовательно, число неупорядоченных г-выборок без повто- рения равно А'„, деленному на г!, т, е, л' У(а. г) = — "" =С„. (3.26) Например, если Е = [А, В, С, О, Е], то можно образовать С'„= С', = 5!/3! 2! =!0 следующих неупорядоченных 3-выборок без повторения: [А, В, С], [А, В, О], [А, В, Е], [А, С, О], [А, С, Е], [А 0 Е] [В С О] [В С~ Е] [В 0 Е] [С 0 Е] (3 27) Число разбиений множества на а неупорядоченных г-вы- борок без повторения.
Отметим, что неупорядоченную г-вы- борку без повторения можно рассматривать как множество. Заметив это, разобьем конечное множество Е из а элементов на й подмножеств Е„Е.„..., Е„таких, что Е,ФЗ, Л=1, 2,..., /г, Е1ЙЕ„=О, Л, 9=1, 2,..., й, 0Е.=Е ] Е, ]= ап ~~.", п, = п, (3.31) ~=1 Каждое из подмножеств Ем Л = 1, 2, ..., й можно рассмат- ривать как неупорядоченную выборку без повторения.
Чему равно количество таких разбиений множества Еу Обозначим это число через У(п; пь и,, ..., аь) и докажем, что Для образования неупорядоченной п,-выборки элементы бе- рутся из всего множества Е и, следовательно, число таких вы- борок равно С„"', Для образования неупорядоченной пювыборки 14 в нашем распоряжении остается и — п! элементов Е, поэтому число таких выборок равно С"„' „, и т. д, Перемножая эти выражения, получаем число различных разбиений.
Выражение (3.32) можно упростить. В самом деле, л,)(л — л,)! ' " "' л,)(л — л,— лз)!' ''' Подставляя (3.33) в (3.32), ил!еем л! А((п; п„п„..., пэ) = Часто это выражение обозначают символически С"з' "з' "" "э '). П ример. Пусть Е = (А, В, С, О, Е). Найдем число разбиений Е с п! — — 1, пэ — — 2, пз =!. Имеем Аг(4; 1, 2, 1)= ))2)З! 12.
(3.33) Приведем их: ([А), [В, С), [О)), ([В), [А, С), [0)), ([В[, [А, 0], [С]), ([А), [С, О], [В]), ([С],[А, В), [О]), ([0], [А, В], [С[), ([О), [А, С], [В]), ([С], [В, О), [А]), ( [А], [В, О], [С] ), ([В], [С, О], [А]), ([С), [А, О), [В)), ([0], [В, С], [А]). УПРАЖНЕНИЯ ') Это число обозначается также(лз, лз, ..., лз).
Оно равно числу перестановок с повторением нз л элементов, среди которых лз равных между собой, лз равных между собой... „ лз равных между собой, и лз + лз + +... +лз=л. )5 ЗА. Пусть Е = (А, В, С, (), Е, Е). Сколько можно образовать из элементов Е: а) упорядоченных 3-выборок с повторением; б) упорядоченных 4-выбо рок с повторением; в) упорядоченных 3-выборов без повторения; г) неупорядо. чеиных 4-выборок с повторением; д) неупорядоченных 5-выборок с повторе. нием; е) неупорядоченных 5-выборон без повторения.
ЗБ. Пусть и = (А, В, С,з), Е, Е). Сколько можно образовать различных разбиений Е, если: а) лз = 3, лз = 2, лз (; б) лз = лз ... = лз = (; в) лз=лз=л»=2;г) лз=лз=з. ЗВ. Сколько четырехбуквенных слов можно образовать иэ букв слова ИНТЕГРАЛ? (Под «словом» понимается размещение.) ЗГ. Рассмотрим пять букв слова ГИПЕР. а) Сколько пятибуквенных слов можно образовать из букв этого слова (бунвы могут повторяться, порядок не существен); в скольких из этих слов. 6) либо одновременно не встречаются Г и И, либо не встречается какая-либо одна из этих букв; в) встречаются либо одновременно Г и И, либо одна из них; г) не встречаются одновременно П и Р; д) встречаются П и Р.
ЗД. Рассмотрим слово ФРАГМЕНТЫ. Сколько совокупностей из букв, не повторяя их, можно образовать, а) беря все буквы; б) беря восемь букв; в) беря две буквы. ЗЕ. В концерте участвуют три певца и две певицы, каждый участник с одним номером, Сколькими способами можно составить программу, если кон. церт должен начинаться и оканчиваться выступлением певца. ЗЖ. Сколькими способами л!ожно вытащить 13 карт из колоды в 62 карты; а) если карта после вытаскивания возвращается обратно; б) если карта не возвращается. ЗЗ. Сколько чисел между !000 и 9999 (множество четырехзначных чисел, ббльших или равных 1000), в которых; а) 3 встречается один раз; б) 3 не встречается; в) 7 встречается три раза? ЗИ, Сколько диагоналей в правильном 20-угольнике? Сколько сторон у правильного многоугольника с 35 диагоналями? ЗК.
Сколькиыи способами можно разместить 12 человек по трем копна. там, если в первую можно поместить два, во вторую гиесть, в третью четыре человека. ЗЛ. У денди !4 пар перчаток. Сколькими способами можно выбрать одну левую перчатку и одну правую так, чтобы они были не из одной пары. ЗМ. Экзамен состоит из десяти вопросов, три нз иих по математике. Сколькими способами можно поставить десять вопросов так, чтобы никакие два вопроса по математике не следовали один за другим. $ 4.
Пересчет. Перечисление. Классификация. Оптимизация Основная задача комбинаторики — изучение вопросов следующего типа о конечных множествах. Если мы интересуемся тем, сколько элементов, принадлежащих конечному множеству, обладает некоторым свойством или некоторой совокупностью свойств, то это — задача пересчета. Если же при этом интересоваться списком элементов, обладающих этим (этими) свойством А В С В Е Е Рис.
3 Рис. 2. Рис. 1. (свойствами), то приходим к задаче перечисления'). Разумеется, если пересчет приводит к слишком большим числам, что часто случается в комбинаторике, то отказываются от соответствующего перечисления н только классифицируют элементы с помощью какого-либо соотношения; это — задача классификации.
В некоторых задачах на множестве решений можно ввести функцию величины и эта функция приводит к полному упорядочению на этом множестве; тогда можно рассматривать понятия максимума и минимума и мы приходим к задаче оптимизации, которая формулируется следующим образом: каково подмноже- ') Автор различает термины «бепощьгс1пеп1» (пересчет) и «епщпега1юп» (перечисление), хотя в литературе обычно в обоих значениях употребляется «епигпега1юп» (по.английски — епишегапа!и. (7?рихс иерее.) 16 ство решений, для которого функция величины максимальна (соответственно минимальна), и каков соответствующий максимум (минимум).
Чтобы проиллюстрировать эти различные аспекты в конкретном случае, мы рассмотрим один пример, в котором результаты ясны без доказательства, но читатель найдет в дальнейшем строгие рассуждения и доказательства на эту тему. Рассмотрим квадрат, разделенный на 25 клеток (рис. 1). Предположим, что в эти клетки размещаются пять кружков так, ф е) Рис. 4.
что в каждую строку и каждый столбец попадает в точности по одному кружку. Каждой клетке (Хь Х;) сопоставим двойку (Х,, Х;), изображаемую стрелкой. Тем самым размещению кружков по клеткам будет соответствовать диаграмма вида рис. 3. Первый вопрос; сколько различных размещений можно реализовать? Легко доказать, что это число равно числу перестановок из пяти элементов, а именно 5! = 5 4 3 2 ! = !20 (рис. ! — 3). Задача пересчета решена. Выпишем эти 120 решений, используя метод, который будет изложен в дальнейшем.
Получим ((А, А), (В, В), (С, С), (В, Р), (Е, Е)), ((А, В), (В, А), (С, С), (В, В), (Е, Е)), ((А, В), (В, С), (С, В), (В, Е), (Е, А)). Это и есть перечисление. Предположим теперь, что нас интересует число решений (возможно, и их список), обладающих специальной структурой. Рассмотрим, например, рис. 3 и назовем контуром замкнутый путь на этой диаграмме. Она состоит тогда из двух контуров длин 3 и 2 соответственно (длина — число стрелок, образующих контур). Интересной является задача распределения на классы 17 контуров, имеющих одинаковую структуру, например, пять кон туров длины 1 (4, а), три контура длины 1 и один контур длины 2 (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
