Основы дискретной математики В.А. Осипова (552659), страница 16
Текст из файла (страница 16)
1=1 1=1 Другим часто используемым в комбинаторике правилом является правило произведен я; если произвольный объект из Х может быть выбран т способами, а произвольный объект из У вЂ” и способами, то вь1бор упорядоченной пары объектов— первого из Х, а второго из 1', может быть осуществлен т п способами. Иными словами )Х х У) = (Х) ~У~. Правило произведения можно обобщить следующим образом: если х1 может быть выбран т1 способами, после чего объект хз может быть выбран тз способами, и для любого 1, 2 < 1' < к — 1, после выбора объектов х1, хз, ..., х, объект х,+1 может быть выбран тьь1 способами, то выбор упорядоченной последовательности из й объектов < х1, хз, ..., хь > может быть осуществлен т1 тэ .
тъ способами. Пример 3.1. а) У вас три любимых сорта конфет и два вида любимых тортов. Тогда любимое лакомство вы можете выбрать 3+ 2 = 5 способами. б) Сколькими способами можно выбрать гласную и согласную из слова «комбинаторикаъ7 В этом слове 6 гласных и 7 согласных. Следовательно, по правилу произведения число способов равно 6 7 = 42. 3.1.2. Размещения и сочетания В этом разделе мы будем использовать принятую в комбинаторике терминологию.
Набор элементов х;„х1„..., х,„из и-элементного множества Х = (х1, хе, ..., х ) называется выборкой объема т из и элементов нли, иначе, (и, т) выборкой. Упорядоченный набор < х;„х,„..., х;„> называется упорядоченной-выборкой. (Есл1« порядок следования элементов в выборке не существенен, то такая выборка называется неупорядоченной.) Можно допускать или не допускать повторения элементов в выборках. Упорядоченная (и, т) выборка, в которой элементы могут повторяться называется розмещепием из и элементов по т с повторением элементов. Если элементы упорядоченной (щ т) выборки не повторяются, то она называется размещением из и элементов по т без повтпорений или проста размещением из п элементов по т. 88 Глава 3.
ОСНОВНЫЕ ПОНЯТИЯ КОМБИНАТОРИКИ При п = т размещение называется перестановкой п элеменгиов множества Х. Определим число таких выборок из и элементного множества Х. Число размещений из п-элементов по т обозначим А'„, число размещений из и элементов по т с повторением элементов обозначим А„',число перестановок и элементов Р„. и! Утверждение 3.1. А„''= и", А„' = ', р„= п! (и — т)! Каждую компоненту упорядоченной (и, г) выборки с повторением элементов можно выбрать п способами. Длина этой упорядоченной последовательности равна т. Тогда по правилу произведения А;,=и и . п=п'. При подсчете числа упорядоченных (п, т) выборок без повторений элементов первый элемент может быть выбран и способами, второй (и — 1) способами из оставшихся элементов, ..., т-й элемент (и — т+ 1) способом из оставшихся элементов.
По правилу произведения п! Аг =п (п — 1) . (и — г+1) = (и — т)! Поскольку Р„= А„", Р„= и!. (Напомним, что О! = 1.) Пример 3.2. Пусть Х = 1А, В, С, Р). Можно образовать 43 = 64 размещений с повторениями из 4 элементов по 3. Примеры таких (4, 3)-упорядоченных выборок с повторениями: ( А, А, А >, < А, А, В >, ( В, А, С >. Число размещений из 4 элементов по 3 равно 4 3 2 = 24, Это, например, (4, 3)-выборки < А, В, С ), < А, В,Р ), < .Р, С, А >. Неупорядоченная (и, т) выборка, в которой элементы могут повторяться, называется сочетанием с повтпоренисм из п элементов по т. Если элементы неупорядоченной (п, т) выборки различны, то она называется сочегпапием без повторений из п элсменитов по т. Отметим, что сочетание из п элементов по т есть фактически т-элементное подмножество и-элементного множества Х. Число сочетаний из п элементов по т обозначается С„', а число сочетаний с повторением элементов С„".
3.1. Комбинаторные схемы п1 Утверждение 3.2. С„' = т !1п — т1.' Действительно, каждую неупорядоченную (и, г) выборку можно упорядочить г! способами, так как число упорядочений лг совпадает с числом перестановок Р„. Отсюда С,", . Р, = А„, т. е. (3.1) Рг г! т 1(п — т)! Отметим некоторые свойства числа сочетаний С": 1) С3 Сп — т. 2) СО + С1 ! ... + Са — 2п 3) Сь = С„" 1+ С~~ Доказать эти свойства можно непосредственно используя формулу (3.1) для числа сочетаний, однако можно предложить более «изящные» доказательства,.
Например, свойство 1) можно трактовать следующим образом: число способов выбрать г-элементное подмножество п-элементного множества совпадает с числом способов «оставить» и — г-элементное подмножество. Левая часть равенства 2) есть сумма числа всех подмножеств — пустого, одноэлементных, двухэлементных и т. д, множества из п элементов, а число подмножеств п-элементного множества равно 2". Для доказательства свойства 3) все Й-элементные подмножества и-элементного множества разобьем иа два непересекающихся класса: к первому принадлежит некоторый фиксированный элемент множества Х, а ко второму он не принадлежит. Тогда число подмножеств, относящихся к первому классу, равно С„1, а второму — Сь .
Применяя правило суммы, получим требуемое соотношение. Пример З.З. В лотерее нужно указать 5 номеров из 36 возможных. а) Сколькими способами можно выбрать 5 номеров из 36? Это число неупорядоченных (36, 5) выборок без повторений, т. е. 36! Сззе = = 376992 зе у3р б) Во скольких случаях будут правильно угаданы ровно 3 номера? Три «правильных» номера будут угаданы С способами, з 90 Глава 3. ОСНОВНЫЕ ПОНЯТИЯ КОМБИНАТОРИКИ а два оставшихся «неправильных» — Сзз1. По правилу произве- дения число случаев равно з з 5! 31! Сз Сз1 —— — — ' = 4650. 3!2! 2!29! Утверждение З.З.
С„' = С" Каждой неупорядоченной (и, т) выборке с повторением элементов из множества (х1, хз, ..., х„) поставим в соответствие последовательность из нулей и единиц по следующему правилу: пишем в последовательности столько единиц, сколько раз каждый элемент х1, хз, ..., х„входил в т-выборку, разделяя последовательности из единиц нулями (при этом, если какой-либо элемент х; не входил в выборку, то пишем подряд два нуля). Следовательно, каждой (и, т) выборке ставится во взаимно однозначное соответствие последовательность, в которую входит т единиц, а число нулей на единицу меньше числа элементов исходного множества, т.
е. п — 1. Длина такой последовательности равна и+ т — 1. Но число последовательностей длины и+ т — 1 из нулей и единиц и содержащее т единиц совпадает с числом тэлементных подмножеств п+ т — 1-элементного множества, т. е. равно С„"-»т 1. Отсюда С„' = Са+ -1 Пример 3.4. В магазине продается 4 сорта пирожных: безе, эклеры, наполеоны, песочные. Сколькими способами можно выбрать 7 пирожных? Каждая покупка — это сочетание с повторением из 4 элементов по 7.
Как следует из доказательства утверждения 3.3, покупке, например, двух безе, одного эклера и четырех песочных пирожных ставится в соответствие последовательность 1101001111. Всего покупок 7 7 7 10! С4 = С7+4-1 = Сзо = — = 120. 7!3! Пример 3.5. Число решений в целых неотрицательных числах уравнения Х1+ хЗ+ ° ° + ха = т равно С;,. Действительно, каждое решене ( а1, аз, ..., а„) этого уравнения можно считать неупорядоченной т-выборкой, в 3.1.
Комбинаторные схемы х1+ хз + хз = 13 равно С 1з = С13 = 105. ' 3.1.3. Разбиения. Полиномиальная Формула Понятие разбиения множества обсуждалось в п. 1.2.2. Подсчитаем число разбиений конечного и-элементного множества Х на 1с подмножеств Х1, Хз, ..., Хй таких, что каждое Х; содержит и; элементов, т. е.
й ЦХ1=Х, ХеОХ =9 Прн»фу, !Х«!=ПИ г'=1, ..., й. й При этом, очевидно, ~~) и; = п. (Отметим, что некоторые 4=1 подмножества могут быть пустыми.) Число таких разбиений обозначим через !У(П1, пз, ..., пй). 'Утверждение 3.4. п! 1У(П1, пз, ..., Пй) = П1.ПЗ. Ий. (3.2) Действительно, каждое из подмножеств Х; есть сочетание без повторег)ий элементов. При образовании сочетания, соответствующего множеству Х1, элементы берутся из всего множества Х, т. е.
число таких выборок равно С,",'. Для образования сочетания, соответствующего множеству Хз, элементы берутся из оставшихся и — п1 элементов, т. е. число таких выборок равно С„"'„, и т. д. По правилу произведения ~-~а1 т~пв Са» й) а 'а а1 и — п1 пв — — а» и! (и — П1) ! х п1!(п — п1)! из 1(п — п1 — пз)! (и — п1 — пз — — пй 1)! п! х пй !0! П1!ПЗ ° ' ' ' Пй.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
