Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 91
Текст из файла (страница 91)
Следовательно, имеются Сь 1 путей из точки (0,0) в точку (й,й), которые до достижения точки (й,й) не приводят к реке. 500 ГЛАВА 12. Снова о комбинеторных подсчетах Теперь рассмотрим пути, которые по суше ведут из точки (й,к) в точку места работы. Но эта задача эквивалентна задаче о перемещении посуху на 10 — й кварталов на север и 10 — й кварталов на восток, а значит, число путей равно Сго ь. Поскольку существуют Сь г способов попасть в точку (гг,к) и Сго ь способов попасть из точки ()с,й) к месту работы, то существуют Сь г Сго к способов попасть на работу, достигнув реки первый раз в точке ()чк). Более того, для каждого пути существует только одно значение к, поскольку место, где он первый раз достигает реки, только одно. Рассмотрим случай, когда наш герой попадает к месту работы, не достигая реки.
Иными словами, рассмотрим случай к = 10. Используем вышеприведенные аргументы, чтобы показать, что количество путей на работу в этом случае равно Сь ы т.е. Сд, но в этом случае, в отличие от предыдущих, нет второй части путешествия. Для удобства записи, исходя из того, что Со = 1, запишем, что число способов дойти до работы, не достигая реки, равно Со Со. Если просуммировать количество путей для всех возможных значений к, 1 < й < 10, то получим количество всех возможных путей от дома к месту работы. Следовательно, го С =~ С, С Как легко видеть, рассуждения не связаны с использованием числа 10. Если взять и вместо 10, то получим Пусть задан и+ 2-сторонний выпуклый многоугольник; требуется разделить многоугольник на треугольники, проводя прямые из вершины в вершину, причем прямые не должны пересекаться.
Сколько существуют способов такого разбненияй Обозначим это число через Т„. Например, для и = 4 возможная триангуляция (разбиение на треугольники) показана на рис. !2.4. Для удобства обозначим вершины через ио, и„иы из, из,..., и„. Предположим, что проведена линия из вершины ио в вершину и,. Сколько треугольников можно начертить? (См.
рис. 12.5.) ег к х, 0 а Рис. 12.4 Теперь для триангуляции остался многоугольник пои,иаиз...и„. Поскольку у него и+ 1 сторон, то имеется Т„г способов триангуляции этого многоугольника. Предположим, что мы начали триангулировать исходный п+ 2-сторонний многоугольник, нарисовав прямую из вершины ио в вершину иь, где 1 < й < п, РАЗДЕЛ 12.2. Числа Каталана 501 и запретили рисовать прямые из вершины ио в любую другую вершину и„где 1 ( Й, так что Й вЂ” наименьшее целое число, для которого существует отрезок из вершины ио в вершину с таким нижним индексом.
Но тогда должен существовать отрезок из вершины иь в вершину и„образующий треугольник иьи,ио. В результате для триангуляции остается многоугольник и,и~изиз... ию Поскольку в этом многоугольнике й+1 сторон, то существуют Ть ~ способов разбиения его на треугольники. (См. рнс. 12.6.) Ус а Рис. !2. б Для триангуляции остается также многоугольник иоиьиь+,иь.ьзиь.ьз... и„.
В нем п — К+2 сторон, поэтому его можно разбить на треугольники Тс» способами. Следовательно, многоугольник справа от линии, соединяющей вершины ио н ию можно триангулировать Ть ~ способами, а многоугольник слева от этой линии можно триангулировать Тс ь способами. Поэтому весь многоугольник вместе с линией от вершины ио к вершине иь можно триангулнровать Ть ~ . Тл ь способами. Рассмотрим случай, когда первой линией будет линия из вершины ио в вершину и„, что можно интерпретировать как отсутствие прямых, выходящих из ио к любым другим вершинам. Но в таком случае должна быть прямая, выходящая из вершины и„в вершину и, н многоугольник и,и,азиз...и„триангулирован.
(См. рис, 12.7.) Но этот многоугольник имеет и+ 1 сторон и поэтому может быть триангулирован Ть ~ способами. Принимая во внимание, что суммирование по к от 1 до п учитывет все возможные разбиения на треугольники исходного и+ 2-стороннего многоугольника и, полагая То = 1, получаем и Т„ = 'У Т, , Т„ ,, а=1 что совпадает с определением чисел Каталана, поэтому Т„ = С„ ° УПРАЖНЕНИЯ 1.
Вычислите Сз, Са и Ст. 2. Во время перерыва 20 человек выстроились у автомата по продаже напитков. Любой напиток стоит 50 центов. В автомате нет монет для сдачи, но как только автомат получает монету, он может возвращать ее как сдачу, Если 10 человек могут заплатить без сдачи, а 10 человек имеют только купюры в один доллар, то сколькими способами они могут выстроиться в очередь, чтобы каждый, кто нуждается в сдаче, мог ее получить.
502 ГЛАВА 12 Снова о комбннвторных подсчетах 3. Сколькими способами можно расставить в очереди 15 мужчин и 15 женщин, если в любом месте очереди женщин впереди должно быть не меньше, чем мужчин? 4. Пусть имеется последовательность из 12 чисел. Сколькими способами можно перемножить эти числа, не меняя их порядка записи. 12.3. ОБЩЕЕ ВКЛЮЧЕНИЕ-ИСКЛЮЧЕНИЕ И РАЗУПОРЯДОЧЕНИЯ Ранее мы уже обсуждали принцип включения-исключения для трех или менее множеств. В этом разделе мы рассмотрим принцип включения-исключения для конечного числа конечных множеств. Для начала докажем следующую теорему.
ТЕОРЕМА 12.7. Пусть Аы Аг, Аз,..., А„— совокупность конечных множеств. Количество элементов во множестве А~ иАгоАзо...оА„определяется формулой !А, щ Аг и Аз и... и А„! = ~ ~А,! — ~~ ~А, О А,~ + 1 а<у + ~ (А, ОА пА„.~ — ... +( — 1)"+')Аг ОАгпАз гт...пА„!. а<г<к ДОКАЗАТЕЛЬСТВО. Необходимо показать, что в правой части приведенного выше равенства каждый элемент множества Аг и Аг и Аз о...
о А„подсчитан и учтен ровно один раз. Предположим, что элемент а принадлежит в точности р множествам совокупности АыАг, Аз,...,А„. В сумме 2, (А,~ элемент а учтен р раз. В сумме 2, (А, П А,.! элемент а учтен всякий раз, когда выбраны два множества, содержащие элемент а. Существуют (~~) способов выбрать такие два множества. Следовательно, в сумме ,'>„,~, ~А, П А ~ элемент а учтен (') раз.
В сумме 2,< „~А, П Аг П Аь~ элемент а учтен всякий раз, когда выбраны три множества, содержащие элемент а. Существуют (Рз) способов выбрать такие три множества. Следовательно, в сумме ,'>"„,< „~А,ПАгПАк~ элемент а учтен (рз) раз. В сумме элементов всех возможных пересечений г множеств, где г < р, элемент а учтен ("„) раз. Следовательно, в сумме ~т (А,( — ~ )А, йА,( + + ~ )А,ПА,ПАк~ — .+( — 1)"+')А,ПАгЛАзП...ЛА„) г<у<ь элемент а учтен р — (") + © — + ( — 1)'+'(р) + + ( — 1)" ь' раз. Но 0 — (1 — 1)" — 1 — р + + + ( 1)", так что 2 3 и получаем, что элемент а учтен в точности один раз.
РЯЗДЕЛ 12.3. Общее включение-исключение и резупорядочения 603 На основании этой теоремы докажем утверждение, известное как теорема о включении-исключении. ТЕОРЕМА 12.8. (о включении-исключении) Пусть Аы Аз, Аз,..., А„— набор конечных множеств. Количество элементов множества А', Г1 А' й А' й ... Л А'„ определяется формулой )А', г~ А', г1... г~ А'„( = )٠— ? (А,(+ ~ )А, г1 А,)— 1 в<у — ~А; г~ А, г~ Ак) + " + ( — 1)" )А, г~ А, г1... г1 А„!. ~<у<к ДОКАЗАТЕЛЬСТВО. Из теории множеств известно, что А', и А', и А', п... г~ А'„= (А, и А, и А, ш ., . ш А„)' = = тт — (Аг и Аг О Аз Г1...
и А ), так что имеем соотношение (А',пА'лА'и...г~А'„~=~٠— ~А~ОАзиАзш...иА„), подстановка которого в (А~ ОАзОАзО...ОА„) = ~~~ (А;) — ~ (А, г~А.)+ Ф а<1 + ~ ~~А, ПАу ПАь( —. + ( — 1)""'(А, ПАзГ~ Аз Г1... ПА„( х<з</с дает требуемый результат. ПРИМЕР 12.9. Сколько положительных чисел, меньших 2003, делятся на 2, 3, 5 или 7? Сколько положительных чисел, меньших 2001, не делятся на 2, 3, 5 или 7? Имеются ) ""з"') = 1001 целых чисел, делящихся на 2; ) зозо') = 666 целых чисел, делящихся на 3, ~ о ~ = 400 целых чисел, делящихся на 5, и 1'"т"') = 286 целых чисел, делящихся на 7.
Выбирая по два, получаем, что ~~~~~~ = ЗЗЗ целых числа делятся на 2 и 3, ~~~д~~ = 200 целых чисел делятся на 2 и 5, 1 — ',з') = 133 целых числа делятся на 3 и 5, ~~~~~) = 143 целых числа делятся на 2 и 7, ~~~~~~ = 95 целых чисел делятся на 3 и 7, и ~~~~) = 57 целых чисел делятся на 5 и 7. Выбирая по три, получаем, что ~~~~~~ = 66 целых числа делятся на 2, 3 и 5, ~~4~~) = 47 целых чисел делятся на 2, 3 и 7, 1'оп,") = 28 целых чисел делятся на 2, 5 и 7, и Щ~ = 19 целых чисел делятся на 3, 5 и 7. Наконец, имеются ~~~~~~ = 9 целых чисел, которые делятся на 2, 3, 5 и 7. Итак, существуют 504 ГЛАВА 12. Снова о хомбинаторных подсчетах 1001+ 666+ 400+ 286 — (333+ 200+ 133+ 143+ 95+ 57) + +66+ 47+ 28+ 19 — 9 или 2353 — 961+ 160 — 9 = 1543 целых числа, которые делятся на 2, 3, 5 или 7. Соответственно, существуют 2001 — 1543 = 458 целых чисел, которые не делятся на 2, 3, 5 или 7. Воспользуемся теперь теоремой о включении-исключении для подсчета количества разупорядочений.
ОПРЕДЕЛЕНИЕ 12.10. Разупорядочением называется перестановка п различных упорядоченных символов, при которой ни один из символов не остается на своем месте. Количество разупорядочений на и различных упорядоченных символах обозначается через Р„. Для удобства обозначим рассматриваемые и символов как 1,2,3,...,и. Для и = 1 величина Р, = О, поскольку перестановка одного элемента оставляет его на месте. Для и = 2 единственным разупорядочением будет (г поэтому Рз = 1. Для п = 3 разупорядочениями будут перестановки 2 3 1 3 1 2 так что Рз — — 2. Существует 9 разупорядочений, если и = 4. Предлагаем читателю найти эти перестановки самостоятельно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
