Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 54
Текст из файла (страница 54)
3. Вычислите подходящие дроби рь/дь определяя рь и дь при О < !г < 5 для х = [!о,!1,тз,ез,!е,!з,хе] и для следующих значений х (см. упражнения раздела 7.1): а) х=х/5; б) х=~/2; в) х = я; г) х = (1 + ъ/5)/2 4. Докажите утверждения (д) и (е) теоремы 7.12.
5. Докажите теорему 7.13. Указание; используйте теорему 7.1!. 6. Пусть для цепной дроби [!о,е„!з,...,1„] величины рь и дь определены теоремой 7.!1. Докажите, что =( — 1)"е' приО<гг<п, дь дь-1 где левая часть равенства записана с помощью определителя. 7. В теореме 7.!1 показано, что если р г = 1 и д 1 = О, утверждение (в) справедливо при !г = 1. Какие значения должны иметь р з и д з, чтобы утверждение (в) было справедливо для !г = О? Ряэдсл э.я Основные комбинвпюрные принципы 317 из обведенных чисел изображает единственный исход. Если на монете выпал Н, то существуют шесть возможных исходов для кубика; и те же шесть возможных исходов, если выпала "решка" Т.
Таким образом, можно найти общее количество исходов, умножая 2 х 6, т.е. умножая число возможных исходов для подбрасывания монеты на число возможных исходов для подбрасывания игральной кости. Следует обратить внимание, что исход подбрасывания монеты не влияет на возможный исход подбрасывания кости. Можно представить, что игрок подбрасывает две кости. Существуют шесть исходов выпадений первого кубика и шесть — второго. Поэтому существует 6 х 6 = 36 возможных исходов выпадения при подбрасывании двух кубиков.
По желанию можно снова нарисовать дерево подсчета. Аналогичным образом предположить, что выбирается сначала одна буква из 26-символьного алфавита, а затем — вторая, причем вторая буква может совпадать с первой. Для нахождения общего числа буквенных пар важно заметить, что имеются 26 вариантов выбора первой буквы, и для каждой выбранной первой буквы существуют 26 вариантов выбора второй. Следовательно, существуют 26 х 26 = 676 возможных способов выбора из алфавита буквенных пар. Если вторая буква не должна совпадать с первой, то после выбора первой буквы имеется только 25 вариантов выбора второй. Поэтому всего имеются 26 х 25 = 650 возможных вариантов выбора.
Другой способ решения этой же задачи; вычесть из 676, общего числа возможных вариантов выбора буквенных пар из алфавита, число всех вариантов, в которых обе буквы совпадают. Их, понятно, 26, поэтому, вычитая 26 из 676, снова получаем 650. Предположим, что номерной знак автомобиля содержит три буквы алфавита, за которыми следуют три десятичные цифры. Если повторения разрешены, то существуют 26 вариантов выбора каждой буквы и 10 вариантов выбора каждой цифры.
Таким образом, общее число номерных знаков составит 26 х 26 х 26 х 10 х 10 х 10 = 17,576,000. Допустим, что по какой-то причине буквы и цифры не могут повторяться. Тогда, после выбора первой буквы имеются 25 вариантов выбора второй и 24 варианта выбора третьей буквы. Аналогично имеем 10 вариантов выбора первой цифры, 9 вариантов выбора второй и 8 вариантов выбора третьей цифры номера. Таким образом, общее число номерных знаков составит 26 х 25 х 24 х 10 х 9 х 8 = 11,232,000.
Выразим данный метод в приведенной ниже теореме, которую примем в качестве аксиомы. ТЕОРЕМА 8.1. (Комбинаторный принцип умножения) Пусть задана последовательность событий Е,,Ез, Ез,,Е таких, что событие Е, осуществляется п, способами, и если события Еы Ез, Ез, ..., Еь , осуществились, то событие Еь может осуществиться пь способами. Тогда существует и, х пз х пз х .. х п способов осуществления всей последовательности событий. 318 ГЛЯВЯ 8. Комбинатормке и вероятность ПРИМЕР 8.2. Сколько существует функций, задающих взаимно однозначное соответствие между множеством 5, содержащим и элементов, и множеством Т, содержащим гп элементов? Если и > т, то такие функции не существуют, поэтому предположим, что и < т. Не уменьшая общности, допустим, что элементы множества Б обозначены а,, аз, аз,..., а . Существует гп вариантов отображения элемента аы Если образ а1 определен, то имеется т — 1 вариантов отображения элемента аз, поскольку он не может быть отображен в образ элемента аы Аналогично, существует гп — 2 вариантов отображения аз и гп — 3 вариантов отображения а4, и т.д.
Руководствуясь этой схемой, получаем, что существует т — г + 1 вариантов отображения ан Поэтому, в соответствии с комбинаторным принципом умножения, имеется (гп)(гп — 1)(гп — 2)(т — 3) .(Гп — п + 1) способов отображения множества 5 на множество Т, при котором никакие два элемента множества Б не будут отображены в один и тот же элемент множества Т. Таким образом, существует (гп)(гп — 1)(т — 2)(гп — 3) (т — п + 1) взаимно однозначных функций из Б в Т. ПРИМЕР 8.3. Сколько существует функций из множества 5, содержащего п элементов, в множество Т, содержащее гп элементов? На этот раз любой из п элементов множества 5 может быть отображен в любой из гп элементов множества Т.
Следовательно, существует (т)(т)(т)(гп)... (гп) = гп" функций из о в Т. П ПРИМЕР 8.4. Битовая строка — это строка, состоящая из элементов, каждый из которых имеет значение 1 или О. Сколько существует битовых строк, имеющих длину 5? Сколько существует битовых строк длины й? Поскольку каждый символ строки может иметь значение 1 или О, то существует два варианта выбора для каждой позиции. Следовательно, существует 2 х 2 х 2 х 2 х 2 = 2з битовых строк длины 5. По аналогичным соображениям, имеется 2" битовых строк длины 1з Е ПРИМЕР 8.5.
Сколько существует подмножеств множества о, содержащего пять элементов? Сколько подмножеств имеет множество, содержащее й элементов? Имеется несколько способов подсчета подмножеств. Укажем два из них, Рассмотрим первый способ. Пусть аы аз, аз, а4, аз — элементы множества 5. Определим взаимно однозначное соответствие между множеством Я и множеством битовых строк длины 5, при котором каждому подмножеству з множества Б соответствует строка, в которой г-ый бит равен 1, если а, е о, и равен О, если а, ф 5. Таким образом, подмножество (а,, аз, а4) соответствует строке 11010, подмножество (аз,аз) соответствует строке 01001, о соответствует строке 00000, а множество о соответствует строке 11111.
Итак, установлено взаимно однозначное соответствие между подмножествами множества о и битовыми строками длины 5. Из предыдущего примера известно, что существует 2з битовых строк длины 5. Поэтому существует 2з подмножеств множества из пяти элементов. Используя аналогичные рассуждения, можно показать, что существует 2ь подмножеств й-элементного множества. РЯЗДЕЛ 8.1. Основные комбинвторныв принципы 319 Второй метод подсчета состоит в том, чтобы для каждого подмножества з б 5 определить функцию У, из 5 в множество (О, Ц.
Функция 7; определена соотношениями 7,(а;) = 1, если он Е з, и 7,(а;) = О, если ои ф з. Обратно, пусть задана функция Х из множества 5 в множество (О, Ц. Если положить з = (а,: 7(ои) = Ц, то функция 7' является функцией 7",. Поэтому имеется взаимно однозначное соответствие между подмножествами множества 5 и функциями из 5 в (О, Ц. Но, согласно примеру 8.3, существует 2з функций из 5 в (О, Ц, Подобным образом, если множество 5 содержит й элементов, то имеется 2" функций из 5 в (О, Ц, и поэтому существует 2 подмножеств множества 5. С) Предположим, что на собрании присутствуют 10 мужчин и 15 женщин, и кого-то одного нужно выбрать председателем. Существует 10 + 15 = 25 способов выбора председателя. Предположим, что человек направляется в ресторан, в котором предлагаются 15 блюд из говядины, 8 блюд из свинины и 12 блюд из морских продуктов.
Посетителю ресторана предложен выбор из 15+ 8+ 12 = 35 различных блюд. Предположим теперь, что студент выбирает книгу на полке, где находятся 25 различных учебников по математике, 30 учебников по информатике и 15 — по химии. Существует 25+30+15 = 70 различных вариантов выбора книги студентом. Заметим, что в каждом случае множества, из элементов которых делается выбор, не пересекаются. Эти примеры приводят к следующей теореме, которая формулируется без доказательства.
ТЕОРЕМА 8.8. (Комбинаторный принцип сложения) Пусть 5ы 5г,5з,...,5 попарно непересекающиеся множества (т.е. 5, П 5 = Я для всех г ф з), и пусть для каждого г, множество 5, содержит гн элементов. Количество вариантов выбора из 51 или 5г или 5з или ... или 5 равно п1+пг+па+ +и . На языке теории множеств утверждение теоремы имеет вид ~5, О 5г О 5з О... и 5 ) = 1511+ 15г! + 15з! +. + ~5 1, где (5) обозначает количество элементов множества 5.
ПРИМЕР 8.7. Сколько существует целых чисел между 0 и 1000, содержащих ровно одну цифру 67 Пусть 5 будет множеством целых чисел между 0 и 1000, содержащих ровно одну цифру 6. Пусть 5з — подмножество множества 5, которое содержит число, состоящее из одной цифры, и эта цифра равна 6. Пусть 5г — подмножество множества 5, содержащее двузначные числа ровно с одной цифрой, равной 6. Пусть 5з — подмножество множества 5, содержащее трехзначные числа ровно с одной цифрой, равной 6. Множество 51 содержит только один элемент — число 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
