Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
кодами кратностей вхождения объектов .. Ш1 ais в исходное сочетание с повторениями. При этом
кратность вхождения 1 кодируется О,
» » 2 » 1,
» » к i » kt— 1,
182
Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ
Если, например, взято сочетание с повторениями й2а1 (л = 6, к = 5), то, согласно описанному алгоритму, этому сочетанию будет соответствовать сочетание Й;0- 4616264*
Покажем, что каждому сочетанию из множества {аи ап, Ьи .Ък-1} по к объектов соответствует в вышеуказанном смысле единственное сочетание с повторениями (из которого оно получается).
В этом сочетании встречается 5 объектов множества {й1, ..а„) и 5^1: 2 .., аи. Тогда остальные к ~ в
объектов принадлежат множеству {Ьи 6*-,}. Следовательно, (А:— 1) — (к — 5) = у — 1 объектов из множества {Ьи ..Ьл_,1 не входят в рассматриваемое сочетание. Пусть это будут объекты с номерами
к'1, кл Л-кг, ..&1 + кг + ... + А'в_! (К к2, ..к,-1 > 1}.
Этими объектами множество {Ъи ..Е^-м) разбивается па 5 кусков, некоторые из них могут быть пустыми (в случае, если соответствующее &* = 1). Длины полученных кусков равны соответственно
А'1 — 1, - 1, ..к* ~ 1,
где к, = & — (&! + ... + &*_!). Производя декодирование, получим сочетание с повторениями
а ? » •
Из данного соответствия немедленно получаем, что => = Теорема доказана.
6. я-мерный куб размера к{к^ 2). Случал к~ 2 нами уже разобран. При к 5* 2, очевидно, | Е" | = кп. Рассмотрим набор (<%!, а2, • • е Е^. Этот набор можно характеризовать значениями ки кг, ..., кг, которые в нем встречаются, и кратпостями пи пг, ..., пг (щ>0, ? = = 1, ..., г) вхождений этих значений в (аь а2, ..., а„). Очевидно, П-1 + п2 -Ь ... + пт ~ п.
Специфику набора (а1р а2, ..., а*) можно задавать в
тп1 гп‘> »“г
виде следующей записи: кг , к2~, ...,аг ? Совокупность
наборов с данной спецификой йй1, АА ..., к/ будем называть слоем. Подсчитаем число точек в данном слое.
Ч. П. КОМБИНАТОРНЫЙ АНАЛИЗ 183
Выбор позиций для значения к{ осуществляется }
способами.
Далее, выбор позиций для значения кг осуществляет-
С Г)
с я 1) способами.
Выбор позиций для значения кг осуществляется /в —пг — ... — V. Д
I п \ способами (т. е. однозначно).
Таким образом, интересующее нас число равно
_ пі_____________(и"~ "О1
” Яі!(в - пД! п2\ (п - ~ п2)!
. (п~~ П1~~ -""»г-Д1 ИІ
* ’ * ’ Пг! 01 пі!/У ? • ? пГ1 *
Это число обозначается также через
( " 1 У1!’ П2’ Пг)
Число слоев с заданными г значениями кУ) ..кт равно числу решений уравнения
«і + п2 + ... + пт — п, пи пг> 0. • (14)
И, наконец, число выборов из к каких-либо г значений
равно ^ Окончательно мы получаем
»"=1 ' 1 2 711**"” 2^ *?• + %—'П
Эта формула при А: = 2 переходит в (9).
7. Разбиения мпожества Е. Обозначим через Ф (п, к) число разбиений множества Е = {я1? ..ап) на к (п> 0, 0<&<н) непустых частей, а через Ф(п) — число всех разбиений множества Е (н >0) на непустые части. Ино-
1Я4 Ч. II. КОМЕIIНЛТОРНЫЙ АНАЛИЗ
г да доопределяют эти числа для случая к > п, к = 0 и п — 0:
Ф(п,Л)=0, к>п,
Ф(п,0)=0, п>0,
Ф(0) = Ф(0, 0) = 1.
Комбинаторные числа Ф(п,/с) называются числами Стирлинга 2-го рода, а Ф(п)— числами Белла. Очевидно,
Ф(П)- І Ф (»!*). ( Ю)
ь=о
Найдем сначала явную формулу для чисел Ф(п, к). Каждое разбиение Е =<?х 11 и ... и «Э3* на непустые подмножества можно характеризовать набором чисел (1и К Ї«), где
її — число подмножеств разбиения мощности 1,
1% — число подмножеств разбиения мощности 2,
1п — число подмножеств разбиения мощности п. Очевидно, что эти числа удовлетворяют тождеству
1 ? Ї* + 2їа + ,,, + п1п = п. (17)"
Теорема 3.
ф (п, к) - У ----------------------------
(І,.!“.!,.) 1,11,1 ... і„! (II) 1 (21) * ... (пі) 11
• .Дп>0 1>11 + 202+...-Ьтгг71=п 11 + 12+,,- + Іп=к
Доказательство. Процесе построения всех разбиений множества Е на к непустых частей, характеризуемых набором чисел (1и 1г, ,.1п), ^ + 1г + ... + 1п = к, можно представить следующим образом. Возьмем п упорядоченных ячеек и разобъем их на к подмножеств, характеризуемых данным набором чисел (11г 1г, ..їт,). Эти подмножества занумеруем числами 0, 1, ..к — 1. Разместим в этих ячейках элементы а1г ..., ап. Очевидно, что разбиение ячеек на подмножества структуры (її, ї2, ..їп) порождает разбиение элементов аи ап на подмножества такой же структуры. Последнее задается набором (аи а2, ..ап), где аі — номер подмножества разбиения ячеек, которому принадлежит элемент аі. Производя различные размещения элементов щ, ап
Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ 185
по ячейкам, мы получим все разбиения множества Е на к непустых частей данной структуры (1и К ... у. При атом два размещения определяют одно и то же разбиение множества Е тогда и только тогда, когда для соответствующих им наборов («1, ., ссп) и (аи Щч • * • , а„)
выполнено условие: для любых ? и / равенство Щ = а} эквивалентно равенству сх, — а. Это означает, что два таких размещения переводятся друг в друга преобразованием, состоящим из перестановок элементов внутри одной компоненты разбиения и перестановок компонент разбиения, имеющих одинаковую мощпость. Таким образом, среди п\ возможных размещений элементов
