Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 59
Текст из файла (страница 59)
Используя те же аргументы при выборе г объектов из и без учета порядка, получаем следующую теорему. РАЗДЕЛ В.З. Перестановки и сочетания 335 ТЕОРЕМА 8.28. Количество способов выбора т объектов из и объектов без учета порядка равно п1 (п — т) Ы /п~ п1 ОПРЕДЕЛЕНИЕ 8.29. Для 0 < т < п положим С(п,т) = ~ ) ~ т~ (п — г)!т! С(п, г) называется числом сочетаний из и обьектое ло г.
ТЕОРЕМА 8.30. Для 0 < г < п имеем С(п,т) = С(п,и — г). ДОКАЗАТЕЛЬСТВО. и! С(п, г) = (и — г) Ы и! (и — т )! (и — (и — г) ) 1 = С(п, и — т). Обратите внимание, что в случае сочетаний, как и в случае перестановок, при выборе г объектов каждый объект может быть выбран не более одного раза. Если выбираются все и объектов без учета порядка, то г = и. Поскольку О! = 1, имеем и.' и! С(п, п) — ' — — 1, (и — п)!(и!) (О!)(и!) поэтому существует только один способ выбрать и элементов; просто взять их все.
ПРИМЕР 8.31. Если множество содержит десять элементов, то сколько оно имеет трехэлементных подмножеств? Поскольку множество не упорядочено, выбираются три элемента из десяти, поэтому всего имеется 10! С(10,3) = — = 120 7(3( различных подмножеств. ПРИМЕР 8.32. Сколько строк длины девять содержат ровно 5 единиц и 4 нуля? Несмотря на то, что строки сами по себе — упорядоченные объекты, эту задачу можно решить, используя сочетания. В строке имеется девять мест для размещения 1 и О.
Можно выбрать любые пять из девяти мест для размещения единицы. Поэтому имеется 9! С(9,5) = —,, = 126 мест для размещения единицы. Как только единицы вставлены, остальные места заполняются нулями. И хотя для строки важен порядок элементов, порядок заполнения пяти мест единицами не существенен; как только эти места выбраны, их порядок уже не имеет значения. П 336 ГЛЯВА 8. Комбинвторияв и вероятность ПРИМЕР 8.33. Сколькими способами можно выбрать комитет, включающий 6 мужчин и 8 женщин, из группы, состоящей из 12 мужчин и 20 женщин? Существует 12! С(12,6) = —,, способов выбора мужчин и С(20,8) = —, 20! способов выбора женщин. Поэтому, согласно комбинаторному принципу умножения, имеется 12! 20! — х †' = 116396280 6!6! 8!12! способов выбрать комитет.
С) ПРИМЕР 8.34. Сколько существует вариантов выбора 5 карт из стандартной колоды, содержащей 52 карты? Поскольку порядок карт не имеет значения, речь идет о выборе 5 объектов из 52, поэтому существует 52! С(52, 5) = — = 2598960 5! 47! возможных комбинаций. П ПРИМЕР 8.35. Сколькими способами можно вытянуть 5 карт трефовой масти из стандартной колоды, содержащей 52 карты? В колоде имеется 13 треф, из которых выбираются 5, поэтому существует 13! С(13,5) = — = 1287 5!8! возможных 5-карточных раскладов пяти треф. С) ПРИМЕР 8.36. Говорят, что 5-карточный расклад содержит каре, если четыре из них являются либо тузами, либо королями, либо дамами и т.д.
Эти четыре карты называются картами одного ранга. Сколько существует раскладов, при которых пятерка карт содержит каре? Существуют 13 способов выбрать каре и 48 способов выбрать пятую карту. Поэтому существует 13 х 48 = 624 различных раскладов, включающих каре. П ПРИМЕР 8.37. "Фулл хаус" содержит три карты одного ранга и две карты другого ранга.
Например, расклад, содержащий три короля и две шестерки представляет собой "фулл хаус". Сколько существует 5-карточных раскладов с "фулл хаус"? Предположим, что "фулл хаус" составили три короля и две шестерки. Три короля выбираются из четырех, поэтому существуют С(4,3) = 4 способа выбрать трех королей. Две шестерки выбираются из четырех, поэтому существуют С(4,2) = 6 способов выбрать две шестерки. Поэтому, согласно комбинаторному принципу умножения существуют 4 х 6 = 24 способа выбрать трех королей и две шестерки или три карты одного ранга и две карты другого ранга.
Существуют 13 способов выбрать три карты одного ранга и 12 способов выбрать две карты одного ранга. Поэтому существуют 13 х 12 = 156 различных способов сочетания рангов. Следовательно, существуют 156 х 24 = 3744 возможных 5-карточных раскладов с "фулл хаус". С) рдздел В.з. перестановки и сочетания 337 Рассмотрим разложение (а + 6) = (а + 6)(а + Ь)(а + Ь)(а + Ь)(а + Ь). Каждое слагаемое в разложении является результатом выбора а или Ь в каждом сомножителе (а + 6) и последовательного их перемножения.
Например, аз получено путем выбора а из каждого сомножителя. Если из первого сомножителя выбрано а и Ь выбрано из остальных сомножителей, то в результате получим аЬ~. Предположим, что требуется найти коэффициент при азЬг. Слагаемое азЬг получается при выборе трех а и двух 6 из пяти сомножителей. Поскольку существует С(5, 3) = /Я способов выбора трех а, то коэффициент при аз6г равен ~ /.
(,3,/' Обобщая результат, получаем следующую теорему. ТЕОРЕМА 8.38. (Биноммальная теорема) Для произвольного положительного целого числа и справедливы равенства (" е = Е (")"" = Е ( )" ' ДОКАЗАТЕЛЬСТВО. Поскольку а"Ь" " получено в результате г-кратного выбора а и и — г-кратного выбора 6 из и сомножителей в выражении (а+Ь)", то коэффициент при а"6" " равен числу способов г-кратного выбора а из и сомножителей (:) Второе равенство следует из того факта, что ПРИМЕР 8.39.
Построим разложение (2х+ Зуг)4. Используя биномиальную тео- рему, находим (2х+Зрг)4 (2х)4+ (2х)з(3уг) + (2х)г(юг)г+ (,о~ Ц ~,2~ + (2х)(Зу ) + (Зу ) = (2х)~ + 4(2х)з(Зуг) + 6(2х)г(Зуг)г + 4(2х)(Зрг)з + (Зрг)4 4 + 96хзуг + 216хгу4 + 216хуе + 81уз РАЗДЕЛ 8.3. Перестановки и сочетания 339 (о) (~) (') (г) (г) (г) (з) (з) (з) (з) (') (~) (') (~) (') (~) (~) (') (') ('.) (~) (и-! ) (пл ) (".) Рис. 8.10 Диаграмма, изображенная на рис, 8.10, известна как треугольник Паскаля.
Каждый из внутренних элементов треугольника равен сумме двух элементов, расположенных над ним, что является прямым следствием доказанной выше теоремы. Имеем В первом случае п = 2 и г = 1, а во втором случае и = 3 и т = 2. Можно заметить, что Гп + 1)-ый ряд состоит из коэффициентов разложения (а + 6)". Например, ( + б)4 о4 + озб + гбг + озбз + 84 Эти коэффициенты приведены в пятом ряду треугольника. На рис. 8.11 изображен треугольник Паскаля с вычисленными элементами. 1 1 1 1 2 1 1 3 3 1 1 4 б 4 1 1 5 10 10 5 1 Рис. 8.П 340 ГПЛВА а, комбинаторика и вероятность ПРИМЕР 8.43.
Найдем разложение (а+ 6)з. Используя шестой ряд треугольника Паскаля, получаем (~+Ь) = а +5а Ь+ 10азЬ +10а Ь +5аЬ +Ь . П Приведенная ниже теорема важна сама по себе и, кроме того, включает один весьма интересный частный случай. ТЕОРЕМА 8.44. (Вандермонд) Пусть т, и и г — положительные целые числа такие, что г < пйп(т, и). Тогда ДОКАЗАТЕЛЬСТВО. Левая часть равенства выражает количество способов выбора г объектов из т+и объектов. Каким бы образом мы не выбирали т объектов из т + и объектов, для некоторого 0 < Й < т всегда )с объектов выбираются из т объектов и г — Ь объектов выбираются из и объектов.
Для этого существуют способов. Обратно, если 1. объектов для любого 0 < й < т выбираются из т объектов и т — к объектов выбираются из и объектов, то при этом г объектов выбираются из т+ и объектов. Следовательно, Следующее утверждение позволяет находить сумму квадратов чисел, образующих строку треугольника Паскаля. СЛЕДСТВИЕ 8.45. Для любого положительного целого числа и ДОКАЗАТЕЛЬСТВО. Полагая в предыдушей теореме и = т = г, получаем (') =,.©(.'- ) или © =(.— ) так что РАЗДЕЛ В.З. Перестановки и сочетания 341 ° УПРАЖНЕНИЯ 1.
Вычислите а) Р(8,5); б) Р(11,8); в) С(12,7); г) С(14,2); д) С(14,12). 2. Вычислите а) Р(8, 3); б) Р(11, 4); в) С(15, 5); г) С(12, 7); д) С(12, 5). 8. Сколько трехзначных чисел можно образовать, используя цифры 2, 3, 4, 5, 6, 8 и 9? А сколько таких трехзначных чисел меньше 450? Сколько среди них четных чисел? Сколько из них делятся на 4? 4. Сколькими способами девять человек могут расположиться в ряд? 5. К несчастью, судья на выставке цветов не разбирается в орхидеях.
Если он выбирает победителей случайным образом среди 18 участниц, то сколько имеется способов вручить первый, второй и третий приз? 6. В скачках участвуют десять лошадей. Сколько существует вариантов призовой тройки лошадей? 7. Пять пар идут в кино. Сколькими способами они могут занять места, если а) они могут сидеть в любом порядке? б) все пять пар сидят подряд? 8.
Шесть мальчиков и шесть девочек идут на концерт вместе. Сколькими способами они могут занять места, если а) мальчики не будут сидеть рядом? б) ни мальчики, ни девочки не будут сидеть все вместе? в) все мальчики сядут вместе? г) два мальчика сядут по краям? д) один мальчик и одна девочка откажутся сесть вместе? 9. Сколько имеется шестизначных чисел, если первая цифра разряд может быть нулем, цифры не должны повторяться и а) последние две цифры должны быть 7 или 8? б) первая цифра должна быть 1, а последние цифры не могут быть 7 или 8? в) цифры 7 и 8 должны стоять рядом? г) число должно делиться на 4? д) число должно делиться на 8? е) в числе должны присутствовать цифры 5 и 6? 1О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
