Введение в прикладную комбинаторику, Кофман А. (984071), страница 18
Текст из файла (страница 18)
Пересчитать следующие случаи: а) карантину должны быть подвергнуты в точности 2 семьи, б) в точности трн, в) не менее трех, г) нсе семьи. й 19. Урновые схемы В теории вероятностей рассматриваются комбинаториые схемы, связанные с выбором г шаров из урны с п шарами. При этом шары могут различаться или нет, выбор шаров производится с возвращением или без (вынутый шар кладется обратно в урну или нет) и он может рассматриваться как упрядоченный илн неупорядоченный.
Рассмотрим наиболее важные случаи. Неупорядоченный выбор с возвращением г шаров из урны е п различимыми шарами. Число способов выбора равно числу неупорядоченных г-выборок с повторением: Ж (г, и) = С„,, !. (19.1) Упорядоченный выбор с возвращением г шаров из урны си различимыми шарами. Число способов выбора равно числу упорядоченных г-выборок с повторением: Ж(г, п) =л . (19.2) Неупорядоченный выбор без возвращения г шаров из урны с а различимыми шарами.
Очевидно, что должно быть г (и. Число способов выбора ранно числу неупорядоченных г-выборок без повторения: гт'(г, и) = С'„. (!9.3) Упорядоченный выбор без возвращения г шаров из урны с а различимыми шарами. В этом случае также г(п. Число способов выбора равно числу упорядоченных г-выборок без повторения; Ж (г, и) = А„'. (19.4) 126 Эти случаи соответствуют следующим размещениям г различимых элементов в п ячеек: Таблица !9! Число размещений г элементов в п различимых и неупорядоченных ячеек Элементы разли- чимые и неупо- рядоченные Элементы неразличимые пг г с„+, Без ограничений С возвращением В ячейку попадает не более одного элемента лл Без возвращения Неупорядоченный выбор Упорядоченный выбор Число способов выбора г шаров из урны с и различимыми шарами УПРАЖНЕНИЯ !26 19А.
Скольними способами можно осуществить неупорядоченный выбор 7 шаров из урны с 11 различимыми шарами: а] без возвращения, б] с возвращением? 19Б. Сколькими способами можно осуществить неупорядоченный выбор 6 шаров из урны с !О различимыми шарами: а) без возвращения, б) с возвращением? 19В. Сколько существует возможностей трижды вытащить туза червей из колоды в 52 карты при пятикратном выборе с возвращением? 19Г. Сколькими способами можно получить, бросая 8 раз игральную кость, дважды 3, дважды 4, трижды 5, один раз 6 (безразлично в каком пс. рядке)? 19Д. Колода в 52 карты раздается 4 игрокам, каждол1у по 13 карт.
Сколько существует возможностей того, что у одного из игроков окажется: а) 13 карт одной масти, б) 4 туза и 4 короля, в) 3 туза и 3 короля? 19Е. По некоторому признаку из совокупности я лиц выбираются г человек. Сколько существует возможностей того, что ! человек окажутся среди г выбранных? 19Ж. Клетка содержит А! хромосом. Обмен частями в парах хромосом осуществляется, когда в плетке происходит г изменений (это может реализоваться (М/2)' различными способами). Подсчитать число случаев, когда а таком обмене участвуют в точности т хромосом. 193. Сколькими способами могут появиться буквы слова АРБУЗ при пятикратнол~ выборе из алфавита в ЗЗ буквы: а) выбор без возвращения, б) выбор с возвращением? Тот же вопрос для слова АГАВА (выбор с возвращением). !9И. Телефонный коммутатор имеет 200 контактов: !00 щтекеров с номерами от 1 до !00 и 100 гнезд с теми же номерами.
Выбираются два контакта. Скольио существует способов выбора. а) одного щтекера и одного гнезда без учета ик номеров, б) пары контактов с одним и тем же номером? 9 20. Задача о супружеских парах, или задача Люка ') Чтобы ввести подстановки с ограничениями, налагаемыми этой задачей, напомним представление подстановки с помощью булевой матрицы. Рассмотрим, например, рнс. 16 — 18. Им соответствуют булевы матрицы на рнс.
34 — 36, в которых предполагается, что на незанятых местах стоят нули. Такие матрицы иногда называют «матрицами назначений». Поставим следующий вопрос как пересчитать подстановки (или перестановки, см. стр. 87), для которых единицы не могут находиться на некоторых фиксированных местах? В главе Гтг, 9 46 мы решим задачу перечисления таких подстановок.
В 5 14 уже рассматривалась подобная задача: задача о беспорядках. В булевой матрице беспорядка на главной диагонали не могут стоять единицы (рис. 37). Сейчас рассмотрим другую такую задачу. За круглым столом рассаживаются и супружеских пар, мужчины и женщины через одного, причем муж не должен сидеть рядом со своей женой. Эту задачу Люка назвал задачей о супружеских парах. Разместим сначала жен, что можно сделать 2 и! способами.
Тогда каждый муж может занять любое место, кроме мест справа и слева от своей жены, и число размещений мужей не зависит от размещения жен. Итак, задача сводится к задаче о соответствующем размещении мужей. Перенумеруем мужей от 1 до п. Теперь задача состоит в том, чтобы пересчитать перестановки такие, что элемент г не может стоять на местах г, г + 1, 1= 1, 2, ..., и — 1, а элемент 1= и — на местах и,!. На рис. 38 изображены эти запрещенные места при п = 7.
На рис. 38 приведено одно из решений, которое в виде подстановки изображено на рис. 40, и рис. 39 показывает соответствующее расположение семи супружеских пар за круглым столом (номер жены тот же, что и у ее мужа, только со штрихом). Пусть!~ Е)~ — булева матрица порядка и с элементами О, )=л+й, А=О, 1, г, 1=1, 2, .... и — 1; „Ег = О, г'=и, (=п, 1; 1 (20.1) 1 в остальных случаях.
') Люка (Е. 1.н с аз), Тйеопе г!ез пощбгез, 1891. 197 Полагаем (7„= рег !1 оЕ !!. (20.2) Обозначая через М„число перестановок п супружеских пар таких, что муж — не сосед своей жены, получаем М„=2 и!У„. (20.3) Можно вычислить с7„и М, исходя из ~~ „Е ~1, но этот способ неэффективен, и приведенный ниже пример показывает, что нельзя 7~о о!~ б 7 1 г г б' б 4' 4 б' б б б 7 7 а обс бго 7с 7 б' б б' б 4' 4 Рис. 39. Рис 40 непосредственно получить простую формулу вида (!5.37) или (15.47).
Для вычисления У„иногда можно воспользоваться формулой Тушара. Предварительно рассмотрим пример (используем (15.28) ). Пусть ОО11~ 2 о о 1 1 0 0~ 2 0 1 1 0!! 2 !! Е1= са = 16! (20 4) !О 0 О 1 1 0 0 !!Е~~с=10 О ,о о 0 0 1 0 1 0 0 О 1 1 0 0 0 1 1 0 11,Е, 11,= 1! ьЕ 1!я= х~~~~с,=4+4+4+4=16; 129 0 1 1~! 2 0 0 1 ! 1 О 0 1 1 1 О, 2 4 0 0 1 1 0 0 1 2 ! 0 0 2 1 0 О, 1 4 2 2 ! 1 1 (20.5) 1 2 1 2 оо! ооо )оооо оо!о 2 1 о 1 о ос ооо О(ОО о)оо 1 1 (20.6) 11 „Е, !)а = )1,Ев)1г = о о ! о оооо о)оо о ! ! о 1 о 1 2 о !о о о о о о о о !!,Ев Ь = о во) ооо(16 о 16 П4Ев)1,= ', (о 1 1 11 „Ев 1)в= оооо ооо о о О)ОО о 1 2 1 11 4Ев )и ') Т уш ар (Т оп сЬ а г6), Зпг пп ргоЫеше ае регши1абопв, С.
к. Асаа. зс!. Рапв 198 (1934), 631 — 636. ') Капа а вский (1. Кар!апв1гу), Зо!пиоп о1 (пе «РгоЫеше аев шепаиев», Вп!1, Ашег, Ма!)г. Ьос, 49 (1934), 784 — 785. 130 о ~се=О+ 1+О+О+1+О=2. Очевидно, что 1),Ев))г, 1=1, 2, 3, 4, образованы из нулей, поэтому ~ с, = О. Итак рег (),Е)1 = с, — ~ с, + ~ са — ~~з, с, = 16 — 16 + 2 = 2. (20.7) Мы видим, что не все ))аЕв))ь г = 1,2, ..., 6, равны между собой; по этой причине трудно получить непосредственно простые формулы вида (16.3?) или (16.47). Тушар ') вывел следующую формулу, использовав две леммы Капланского в); с)л=п! — 2 ! Сва ~(п — 1)1+ 2 Сап-в(л — 2)!в 2п 1 2п 2 ...
+( — 1)" — С"„° 01 а=2, 3, 4, ... (20.8) Применим эту формулу к случаю и=4: 0,=4! — — Сг ° 3!+ — Св 2! — — Св ° 11+ — Са О! = 8 ! 8 в 8 в 8 4 7 ' 6 5 4 = 24 — 48+ 40 — 16+ 2 = 2. (20.9) Леммы Капланского. Первая лемма. Пусть из и раз. личимых объектов, расположенных на прямой, выбираются й объектов. Тогда число )" (п, й) таких наборов, что никакие два из выбранных объектов не являются последовательными, равно (20.10) Прежде чем доказать лемму, рассмотрим пример. Пусть на прямой расположены семь различимых объектов АВСРЕГО и й = 3.
Тогда в силу (20.! О) ) (7, 3) = Сз = 1О. Соответствующими наборами будут АСЕ, АСЕ, АСО, АРг, АРО, АЕО, ВРЕ, ВРО, ВЕО, СЕО. Очевидно, ( (и, 1) = С„' = и, 1(п, и) = О. (20.11) (20.12) Пусть 1 ( й ( и. Разобьем множество таких наборов на два подмножества: наборы, содержащие первый объект, и наборы, не содержащие его. Так как набор, содержащий первый объект, не содержит второго, то число наборов в соответствующем подмножестве равно (20.13) Но число наборов, не содержащих первого объекта, равно 1(п — 1, й), (20. 14) поэтому ~(п, й) =((п — 1, й)+((и — 2, й — 1). (20,15) Теперь применяем индукцию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
