Введение в прикладную комбинаторику, Кофман А. (984071), страница 7
Текст из файла (страница 7)
(8.28) ~=0 Г л-! Полагая и = г + и и учитывая, что С,+, ! = С,э, !, находим » г(„= ~ч~ С„":,'г" = ~ С"„ (8.29) и л и=л Таким образом, число неупорядоченных г-выборок с повторением, в которых каждый объект встречается не менее одного раза, равно Подсчитаем теперь вообше число сочетаний из п объектов по г элементов с повторением, в которых каждый объект встречается не менее й раз. С этой целью рассмотрим такой денумератор: в1„(г) ~ (г + г + ...) = г" (1 — г) = г с~ Са+. 1г . (8.30) =в Если положим и = г+ йп, то с(,(г) = ~ С"„:~~" и „,г". и~вв Таким образом, искомое число равно С',:а" п„п 0(й(г; г=йп, йп+ 1, ...; г, й, пан Х. П р и мер. Даны три объекта А, В, С. Каково число восьми- элементных сочетаний с повторением из этих объектов по 8, в которых каждый объект встречается не менее двух раз? Имеем Р— «п в-в в 4! Сг-а-ив-1= Св-в-1 = С4= — =6.
г!з! Выпишем эти сочетания: '!ААААВВСС), '!ААВВВВСС), '!ААВВСССС1 (АААВВССС), *!ААВВВССС) (АААВВВСС1 Подсчитаем число сочетаний из и объектов по г элементов с повторением, в которых каждый объект встречается четное число раз. Для этого рассмотрим денумератор г!и(г) =(1+г +г + ...) =(1 — г) = ~Св.~., 1г'.
(8.32) Таким образом, У(п, 2г)=С',+, ~ и Л'(и, 2г+1)=0. Вообще при условии, что каждый объект встречается число раз, кратное Й, следует использовать такой денумератор: СО в(„(г) =(1+г +г + ...) =(1 — г ) = Д С'„+, ~г '. (8.33) в=в Итак, У(п, йг)=С,',+, 1 и Ф(п, з)=0, если Рассмотрим теперь условия более общего вида, чем встречались до сих пор в этом параграфе. Предположим, что объект А1 встречается не менее А, — не менее йв раз, ..., А„ — не менее й„ раз.
Тогда стае энумератора можно взять е е* (г) = Ц (а,'г ~ + а,в+'г~1+' -1- ...), в=1 те, что й, раз, в каче- (8.34) 41 а в качестве денумератора 1" ()=П("+""+ ".). Предположим, что объект А! встречается не более й! раз, Аз — не более ез раз, ..., А„— не более е раз. Тогда в качестве энумератора можно взять е*(г) = Ц (1+ аз»+ азг'+ ... + а!!»~!), (8.36) (8.35) а в качестве денумератора л з1 (г) = П (1 + г + г + ° + г !) (8.37) Пусть теперь количество появлений объекта А! — одно из чисел аз„~п ..., Ло где аз<рз< ... <Л,; количество появлений объекта Аз — одно из чисел а„р„..., Лз, где аз<8!« ... Л,; количество появлений объекта А — одно из чисел а„, ~„,..., Л„, где а,<8„< ...
<Лл. Тогда в качестве энумератора можно взять е'(г) =П (а!!»!+ а!!»~!+ ... +а,'г '), (838) ! ! а в качестве денумератора з(*(г)=П(г"з+г"з+ " +» ') ! ! (8.39) Любой разумной комбинации условий, относящихся к наличию или отсутствию объектов в неупорядоченных г-выборках с повторением, соответствует некоторый энумератор и некоторый денумератор. П р и м е р. Перечислить сочетания с повторением из 3 объектов Аь А,, А, по г элементов при условии, что А! встречается не более одного раза, Аз — не более двух, а Аз — один или два раза. Тогда энумератором служит е*(г) (1+ а,г)(1+ аз»+ а,'г')(а,г+ а'г') = = аз» + (а!аз + азаз+а.аз) г'+(а!азаз+азазаз+а!а!аз+ аза:.аз) гз+ + (а,а,азаз+ азазазаз+ а,а,а,а,) г'+ (а,а,а,аза,) г'.
(8АО) 42 Для возможных значений «имеем «=1: [Аз1. «2: [А! Аз] [Аз Аз] [Аз Аз]. «=3: [А, Аз Аз]~ [Аз Аз Аз] [А, Аз Аз1 [Аз Аз Аз1 (8.41) «= 4: [А! Аз Аз Аз1 [Аз Аз Аз Аз] [А~ Аз Аз Аз] «=5: [А1 Аз Аз Аз Аз]. Денумератор равен Г (г) = (1 + г) (1+ г+ г') (г+ г') = — (1+ Зг + 4гз+ Згз+гз) (8 42) Если Я(п, «) обозначает число сочетаний с указанными ограничениями, то И (3, 1) = 1, Ф (3, 2) = 3, У (3, 3) = 4, (8.43) У (3, 4) = 3, У (3, 5) = 1. Общий метод. Для нахождения энумератора и соответствующего денумератора достаточно рассматривать ограничения, относящиеся к подмножествам, на элементы которых накладываются условия. Для этого используется изоморфизм между алгеброй Буля и формальной логикой. Например, пусть А, ен А таково, что выполняются следующие условия: У,: А, встречается четное число раз, тогда множеством коэффициентов будет (1, а'„азн ...).
Уз: А, встречается три или большее число раз, тогда множеством коэффициентов будет (ап а'„а'„...); Уз. А, встречается не более семи раз, тогда множеством коэффициентов будет (1, а„а'„ац ..., а',). Тогда У, Л Уз Л Уз будет соответствовать пересечение (1, аз„ а4 ) П (аз а) аз, ...) П (1, а„ аззо ..., а[) = = (а4 аз) (8.44) Член энумератора, соответствующий А~ и удовлетворяющий условиям, будет а(г'+ азгз. Еше один пример. Предположим, что на А~ и Аз наложено следующее условие: У,: присутствие А~ исключает присутствие Аз (А, и Аз никогда не встречаются вместе). Пусть также дано условие: Уз.
присутствуют как Аь так и Аз, тогда соответствующим множеством коэффициентов будет з з з з з з а,аз а,а„а,а„а,а„а,а;, а,аз, ). Уг = не Уэ, для нахождения У1 нужно взять дополнение указанного множества по отношению к множеству, дающему все неупорядоченные г-выборки с повторением, образованные с Аг и Аж т. е. по отношению к множеству следовательно, множеством коэффициентов, соответствующим Уь будет [1, а„аа а';, а'„а'„а,', ...[.
(8.46) Тогда энумератор есть 1 + (а, + а,,) г + (а', + а';) г'+ (а', + а,') г'+ ... (8.47) Рассмотрим вкратце еще один пример. Даны четыре объекта А, В, С, Р, на которые наложены следующие условия: У,: если А встречается четное число раз, то В встречается нечетное число раз и наоборот; Ух. число появлений С меньше 3; Уз.. число появлеяий Р больше 2. Имеем е" (г) = [Ьг + (азЬ+ Ь ) г'+ (атЬ'+ а'Ь) аз+ (агЬз [ 4Ьз 1 эЬ)гт [ )(1 [ 1 .. )((з з [ „(чгч 1 ) (8.48) УПРАЖНЕНИЯ 8А. Указать денумератор неупорядоченных г-выборок с повторением, в которых каждый объект встречается; а) не менее двух раз; б) не больше четырех раз; в) не менее одного и не больше пяти раз; г) в количестве раз, кратном трем.
8Б. Указать денумератор сочетаний из и объектов по г элементов с повторением, в которых объект Аг встречается не меньше 1 раз Привести также энумератор. Рассмотреть случай пяти объектов А, В, С, О, Е. 8В. Показать, что деиумератор сочетаний из и объектов по г элементов с повторением, в которых каждый объект встречается четное число раз, име. ет вид 1 (1 — з')" ' 8Г. Даны пять объектов А, В, С, О, Е. Указать энумераторы и денумераторы, учитывая следующие условия, наложенные на сочетания с повторением (здесь х обозначает число вхождений обьекта Х в сочетание): а) А, В, С встречаются четное число раз, а О, Š— нечетное; б) о, Ь, с — нечетные числа и с) + е ~ <3; в) о ( Ь ( с; г] всегда о > йг); д) присутствие А исключает В, но разрешает присутствие С, если О присутствует; О исключает Е.
5 9. Денумераторы размещений Для получения энумератора размещений следовало бы построить некоммутативную алгебру пооизводящих функций. Это возможно, но очень сложно и в конечном счете не дает преиму- 44 ществ по сравнению с методом 4 3. Напротив, для получения денумераторов размещений пользоваться производящими функциями удобно. Учитывая (8.5) и (3.25), можно записать д„(г) =(1+ г)"=1+ С,'г+ С'„г'+ С'„г'+ ... + С"„г" = Таким образом, число упорядоченных г-выборок без повторения (размещений без повторения из и элементов по г) равно коэффициенту при г'/г! в (9.1). Для получения числа упорядоченных г-выборок с повторением (размещений с повторением из и элементов по г) используем денумератор д*,(г)=(1+г+ — „+ ...) =(е)"=е =1+пг+ 2, + =~~' —, (92) =о Приходим к результату, полученному ранее (см.
(3.9)): число упорядоченных г-выборок с повторением равно и'. Употребление денумераторов размещений, если накладывать условия на повторение элементов, — вещь более сложная и тонкая. Попробуем, например, получить число таких упорядоченных г-выборок, что каждый элемент встречается не менее одного раза. С этой целью возьмем денумератор з ~л 2 =е"' — нем-и'+ еы — и'+ ... +( — 1)". (9.3) Пример, Приведем числовой пример для п=З. Из (г) = (е'- — 1)' = е" — Зе'* + Зе' — 1 = 2! 3( 4( =1+Зг+ + — + — + ...— (Зг)~ (зг)э (зг)' 3 (1 ! 2г ! (2г) 1 (2г)' + (2г)' + ) 2! 3( 4( =(3' — 3 2з+3) ~, +(3' — 3 2'+3) — + + (Зз — 3 2' + 3) †, + ...
+ (3' — 3 2' + 3) — + ... (9.4) Итак, число упорядоченных г-выборок с повторением, в которых каждый элемент встречается не менее одного раза, равно 3" — 3 2" + 3, г = 3, 4, 5, ... Найдем теперь число таких упорядоченных г-выборок с повторением, в которых каждый элемент встречается не более двух раз. Возьмем с)„(в) = (1 + а + х ) (9,5) Например, при л=3 с(з(а) =(1+я+ — ) = 1+ Зз+ аз+ 4зз + а4+ из+ 9 9 З 2 4 4 8 1+3 а+ ~ ° 2 ° 9 +4 3! з! + 4 ° 4! 4! + 8 з' 1 х' + — 5! — + — 6! —. 4 б! 8 '6! (9.6) Итак, имеем — ° 4)=9 3 2 54 4 зал(в) "(1+2+ х! + ''' + !)(1+3+ + ° + ) ° ° "» ) 1+ + !+ + — )/ (97) Коэффициент при г"1+" + "'+ » г равен в+и+ ..+е е ! ае п! а коэффициент при — равен . Это число — не что и! и!)юэ! '' и»! иное, как число разбиений (см.
(3.34)). УПРАЖНЕНИЯ 9А. Найти денумератор упорядоченных г-выборок с повторением, обраЗуемых я элементами, в которых каждый элемент встречается: а) не менее двух раз, б) точно два раза, в) не более двух раз, г) четное число раз, д) на. четное число раз. упорядоченных 4-выборок с повторением, образуемых тремя элементами, каждый из которых встречается не более двух раз. Приведем етце один пример. Дано множество из и элементов, подсчитаем число упорядоченных г-выборок, в которых элемент Е, встречается и! раз, Ез встречается пз раз, ..., Е» встречается п„раз, причем п1+ пз+...
+ и» = п, а Е„Е,, Ż— некоторые элементы этого множества. 1(л + 2) 1(л + !) + 1(л) с 1(о = 1 и 1(!) = 2. ычислить 1*(з) и выписать последовательность 1(л) (числа Фибоначчи, см. упражнение 7Г). 9Д. Найти денумератор упорядоченных г-выборок с повторением, в которых встречается точно р элементов одного вида и точно по одному элементу каждого из л — р других видов.
Показать, что число таких г-выборок равно 1(л, г, р) Сг а+Сг ! + +Сг Доказать рекуррентную формулу 1(л, г, р) — 1(л, г — ), ) С'„— с'„ й 1О. Основные последовательности и формулы для пересчета Числа Стирлинга. Рассмотрим производящую функцию <р,', (г) = г (г — 1) ... (г — и + 1), и = 1, 2, 3... ° ' гро (г) = 1. (10.1) будучи упорядоченной по возрастающим степеням г, зта производящая функция для начальных значений и имеет следующий вид: !р',(г) = 1, Ф',(г)=г, фз'(г) *г(г — 1) =г' — г, Ф' (г) = г (г — 1) (г — 2) = гз — Згз + 2г, Фз (г) = г (г — 1) (г — 2) (г — 3) = гч — бгз + 11гз — бг. (10.2) Обозначим через з(л, г) коэффициент при г' в разложении (10.1) и тогда запишем <р'„(г) = ~ з(п, г) г', з(0, О) 1, г о (10.3) 9Б.
Указать денумератор упорядоченных г.выборок с повторением, образуемых четырьмя элементами, с условием, что каждый элемент встречается не более одного раза. Выписать эти выборки. 9В. Рассмотрим р объектов А и д объектов В, расположенных на прямой так, что никакие два объекта В не стоят подряд. Показать, что число таких упорядоченных (р+ д)-выборок равно Сор+и 9Г. Рассмотрим л объектов двух видов А и В, расположенных на прямой так, что никакие два объекта вида В не стоят подряд. Обозначим через 1(л) число таких л-выборок. Показать, что Целые числа з(п,г) называются числами Стирлинга первого рода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
