С.В. Яблонский - Введение в дискретную математику (1060464), страница 28
Текст из файла (страница 28)
[ц. Легко усмотреть следующую сьяэгс если сущесгвуег /(е), онределенная на [О, н) к /(») аь тогда кз строгой уннмодальносгк /(е) следует уннлодальность (аь). 119 Ч. 11 КОЫБПНЛТОРВЫВ АНАЛИЗ б„ь „то существует взаимяо однозначное соответствие между а... и С„ь,ЦС„, „,. В силу етого (а) (л — !) (я — 1) Данное рекурревтное соотношение позволяет !и прв том гь! с линейной сложпосгью) построить для чисел (ь) таблицу, называемую треугольником Паскаля.
Таблваа 2 Сочетания элементов из Е-!а„..., а„) по й являются специальными подмвоя!ествами из Е, содержащими ровно й элементов. Соответствующие им наборы !сг„..„сг.) содержат ровно й единиц и образу!от й-й слой к-мерного куба Е„.". Отсюда следует, что й-й слой содержит (ь) 1ЗО ч. зь комвыплтогнын Апллнз точек. Следовательно, Еь' разбивается в прямую сумму слоев с номераььи й О, 1, ..., и и (,")+(,")+ ... +(„") -2". (9) $.
Сочетания с повторениями элементов из Ж по ьт. ь Обозначим через Н» число сочетаний с повторениями злементов из множества Е (аи .;., а.) по й. Теорема 2. Н Д о к а з а т е л ь с т в о. Рассмотрим некоторое сочетание с повторениями из етого множества, содер>кагцее й (н 1 С числами ( ь ) связано функциональное тождество, называемое Формулой длл бинома Ньютони (1+ )"-(",)+(",) + ...+(„") +„.
+(") ".(1о) В самом деле, коэфФициент при х" получается всевозможными выборамн из )ь скобок (1+ х) переменного х и из остальных скобок 1, что дает как раз ( ь ) слагаемых. Полагая в (10) х 1, мы получаем тождество (9), Если в (10) взять х -1, то получим (",) (",)+ ... +( — 1)" (")-О. (1Ц Покажем, далее, что т ( ь'-'(")(')-( ' с2) Опираясь на тождества (8) н (11), имеем Х (-1)'- (",Х,')-Х(-1)'- (",И",—,")- -(",) Х~- ~'-'("::) -(ь:",'..": Аналогично доказывается, что при пь > л Х~ — )''(„„)(„:;) (,„,„,' из ч. и, комвинлтогныи лнлл»»з 181 объектов.
Пусть в сочетании встречаются г элементов а»,, °, а», (1 ~ », <... < 1, - л) соответственно с кратностями Ь„..., Ь„где Ь»+... + Ь. Ь. Мы будем зто сочетание записывать в следующем виде: А»»»», а» а ... а» . 1 3 Установим взаимно однозначное соответствие между соче- таниями с повторениями объектов множества (а„..., а„) по»г и обычными сочетаниями из множества (а„..., а„, Ь„..., Ь»») по Ь, где символы а„..., а„, Ь„..., Ь,, ко- парно различны.
Для етого сочетанию с повторениями »» »» ' з ° а, а, ... а;, » поставим в соответствие сочетание а, а» ... а,,Ь,Ь,... Ь», .,Ьд +,Ь»,+, Ьн»+»»Ьг»+»»+» ... Ьг»+...+», ч» ... Ь» + . +в» ° Как видно, объекты из множества (Ь„Ь„..., Ь,,) входят в данное сочетание массивами: ЬА "° Ь„; ' »»+»Ь»,+г" Ь»,,+Н-»1 Ь, ...; Ь„,,„,+„,,„... „„,„,„,, ... Ъ Число массивов равно г, и каждый из них содержит соот- ветственно по Ь,— 1, Ь» — 1, ..., Ь,— 1 объектов.
Коррект- ность такого построения вытекает из тождества (Ь» — 1)+(Ь» — 1)+...+(Ь.— 1)+(г — 1)=Ь-1. Отсюда вытекает также, что число объектов в сочетании равно г+(Ь» — 1)+(Ь» — 1)+... +(Ь, — 1) Й. Таким образом, построенпое сочетание содержит по одно- му представителю каждого сорта объектов, встречающих- ся в сочетании с повторениями, т. е. а»,, ...,а»,, а длины массивов объектов из мпол»ества (Ь„..., Ь,,) являются кодами краткостей вхождения объектов а;,, ..., а», в ис- ходное сочетание с повторениями. При атом кратность вхождения 1 кодируется О, »»> 2» 1, »» !', » Ь,— 1.
183 Ч. 11. КОМБИНАТОРНЫЯ АНАЛИЗ Если, например, взято сочетание с повторениями з а азаз (и 6, й 5), то, согласно описанному алгоритму, этому сочетанию будет соответствовать сочетанне а,а,Ь,Ь,Ь,. Покажем, что каждому сочетанию из множества (а„..., а., Ь„..., Ь,,) по й объектов соответствует в вышеуказанном смысле единственное сочетание с повторениями (из которого оно получается).
В этом сочетании встречается з объектов мнон<ества (ао ..., а„) и з~1: а11а11... а„. Тогда остальные й — г объектов принадлежат множеству (Ь„..., Ь„,). Следовательно, (й-1) — (й — з) з — 1 объектов нз множества (Ь„..., Ь,,) не входят в рассматриваемое сочетание. Пусть это будут объекты с номерами й„й,+й„..., й,+й,+...+й., (йо й„..., й,,>1). Этими объектами множество (Ьо ..., Ьь,) разбивается на ' з кусков, некоторые из них могут быть пустыми (в случае, если соответствующее й, 1) .
Длины полученных кусков равны соответственно й,-1, йз-1, ..., й.-1, где й, й — (й,+...+й,,). Производя декодирование, получим сочетание с повторениями А, А, а1а1 ...а;,, 1 1''' Из данного соответствия немедленно получаем, что Н„= 1л+З вЂ” 11 /. Теорема доказана. 6. и-мерный куб размера й(й)~ 2). Случай й 2 на- ми уже разобран. При й>2, очевидно, )ЕА~ й". Рас- смотрим' набор (а„а„. ° .,а„)~ЕА Этот набор можно характеризовать значениями й„й„..., й,, которые в вем встречаются, и кратностями п„л„..., и, (и,) О, 1, .
„г) вхождений этих значений в (ссо- аэ ..., И.). Очевидно, п, + и,+...+п,=я. Специфику набора (иэ аь ..., а„) можно задавать в М1 Аз Иг виде следующей записи: й,', й.,',..., й, . Совокупность наборов с данной спецификой й,, й,', ..., й будем на- аывать слоем. Подсчитаем число точек в данном слое.
ч. и. комвинАТОРный АнАлиз !' и '! Выбор позиций для значения й, осуществляется л1 способами. Далее, выбор позиций для значения й, осуществляет- !л — л 1 са ~ ') способами. лл Выбор позиций для значения й, осуществляется < л — л —...— л г-> 1 ~ способами (т. е. однозначно). ии Таким образом, интересующее нас число равно л! (л — лз)! и !(л — л )! л ! (л — л — л )! (л — л — ... — л„)! и! л„! о! и !и! ...л„! ' Это число обозначается также через (л, и, ..., л,). Число слоев с заданными г значениями йл ..., й, равно числу решений уравнения и,+из+...+п„=и, и„..., п,)0.
(14) И, наконец, число выборов из й каких-либо г значений !' «'! равно ~ г! Окончательно мы получаем йл =,,)', („),)', л!л !... л ! ° (15) 1 2 (и,,и,,...,и„~л) Эта формула при й = 2 переходит в (9). 7. Разбиения множества Е. Обозначим через Ф(я, й) число раабиений множества К (а„..., а„) на й (я)0, 0(й~ и) непустых частей, а через Ф(п) — число всех разбиений множества Е (п>0) на непустые части.
Ино- 184 ч. и, комвпплтогпый Апллпз гда доопрсдслиот зти числа для случая й>п, й= О и и 0: Ф(п,й)=0, Й>п, Ф(п, 0) О, п>О, Ф(0)-Ф(0,0) 1. Комбинаторные числа Ф(п, й) называются числами Стир- линга 2-го рода, а Ф(п) — числами Белла. Очевидно, и Ф(п) Д Ф(п, й). (16) г=з Найдем сначала явную формулу для чисел Ф(п, а). Каждое разбиение Е = Е, 0 д', 0 ...0 Ю, на непустые подмножества можно характеризовать набором чисел (1„ (ь ..., 1„), где 1, — число подмножеств разбиения мощности 1, Ц вЂ” число подмножеств разбиения мощности 2, 1„— число подмножеств разбиения мощности и.
Очевидно, что зти числа удовлетворяют тождеству 1 ' 11 + 2(а + . ° . + п)и ~ и (17)' Теорема 3. Ф(п,й) р л,.„л ) 1 0 ! . „1э! (10 1 Щ г ... Щ и т 1,+г ~,+...+и„=в 11+~г+" +!л=А Доказательство. Процесс построения всех разбиений множества Е на Й непустых частей, характеризуемых набором чисел ((о (ь ..., („), 1,+1,+...+1„= и, можно представить следующим образом. Возьмем п упорядоченных ячеек и разобъем их на й подмножеств, характеризуемых данным набором чисел (1и („..., 1 ). Эти подмножества запумеруем числами О, 1, ..., й — 1.
Разместим в этих ячейках элементы а„..., а„. Очевидно, что разбиение ячеек на подмножества структуры ((о Ц, ..., 1„) порождает разбиение элементов а„..., а на подмножества такой же структуры. Последнее задается набором (ао а„..., а ), где сг~ — номер подмножества разбиения ячеек, которому принадлежит элемента,. Производя различные размещения элементов ао ..., а„ ч. н.
комвинАТОРныи АнАлиз 1аб по ячейкам, мы получим все разбиення множества Е на ' Й непустых частей данной структуры (!и 1,, ..., !.). Прн этом два размещения определяют одно и то же разбиение множества Е тогда и только тогда, когда для соот- ВЕтСтВуЮщИХ ИМ НабОрОВ (а„иг ., а„) И (а„а1 ° ., Сси) выполнено условие: для любых 1 и 1 равенство м1 а; зквивалентно равенству сг1 = а,. Это означает, что два таких размещения переводятся друг в друга преобразованием, состоящим из перестановок злементов внутри одной компоненты разбиения и перестановок компонент разбиения, имеющих одинаковую мощность. Таким обрааом, среди и! возможных размещений элементов каждое разбиение повторится ровно 1,(!з! ... 7 ! (1!) ' Х 1р 1и Х(2!) ' ..
(я!) раз. Теорема доказана. Мы уже видели, что разбиения множества Е связаны с наборами (иь ..., а ). Выберем г значений из множества (О, 1, ..., й — 1). Пусть это будут й, йа ° ° ° йи / А'! Очевидно, таких выборов будет ! 1. Возьмем произвольное разбиение Е на г частей.
Число разбиений равно Ф(я, г). Если нумеровать компоненты разбиений числами й„й„..и й, (г! способов), то мы получим всевозможные наборы длины п, содержащие ровно г значений Й„й„..и й,. Очевидно, что каждый набор при атом будет построен ровно один раз. Поэтому "= Х ~ь~) !Ф(, ). (18) Если теперь сравнить соответствующие слагаемые в (15) и (18), то из рассуждения можно увидеть, что они выражают одно и то же число. Отсюда получаем еще одно явное выражение для Ф(и, г) (я, г) 0)1 и +и +...+и„=и 1 З Полученные формулы для Ф(я, й) практически не пригодны для вычисления Ф(л, й), так как они предполагают знание всех рептеиий уравнения (14) или (17).
Эффективные способы вычислений чисел Стирлинга 2-го рода и изучение их свойств связано с установлением ряда рекуррентных соотношений дзя Ф(я, й), ч. и. комвинатогпыя анализ «-с УсФ(и,Ус) ~', (")Ф(с',Й вЂ” 1) или «-т ЙФ( Й)- Х(",)Ф(У,Й вЂ” 1). (20) Несколько видоизменим предыдущее рассуждение. В произвольном разбиении Е на Й непустых подмноакестз, выбросим ту компоненту, которая содержит фиксированный элемент а (а, ез Е). Тогда этому разбиению однозначным образом соответствует разбиение на Й вЂ” 1 непустых подмножеств некоторого множества из 1 элементов (Й вЂ” 1<1< и — 1).
Справедливо и обратное утверждение: любое разбиение на Й вЂ” 1 непустых частей произвольного подмножества из Е, не содержащего а„, однозначным образом продолжается до разбиения множества Е на Й непустых частей. Поэтому Ф(и,Й) ~~~~ ( )Ф(У,Й вЂ” 1) Ф(и, Й) ~ (" „) Ф(У, Ус — 1). (21) Почленно суммируя по Й полученное тождество и учитывая (16), инеем Ф()- Х(", ')Ф(У).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
