РОЗДІЛ 2
КОМБІНАТОРИКА МУЛЬТИМНОЖИН ТА ДЕЯКИХ Ч.В.М.
2.1. Шляхи на діаграмі з рухом
Твердження 2.1. Якщо – деяка мультимножина, а – відповідний їй мультибулеан,
то справедлива рівність
.
Доведення. Доводимо за допомогою індукції. Твердження очевидне при , бо у
випадку маємо всього підмультимножин: .
Припустимо, що твердження справедливе при , і доведемо його справедливість
при . Кожна із підмультимножин мультимножини є також підмультимножиною
мультимножини . Тому кожній мультимножині можна поставити у відповідність
підмультимножин мультимножини . Таким чином, мультимножина має всього
підмультимножин, що і доводить твердження 2.1.
Твердження 2.2. Для довільних мультимножини і її підмультимножини потужність
ч.в.м. дорівнює
Доведення. Для доведення достатньо встановити взаємно однозначну відповідність
між елементами ч.в.м. і , а це можна зробити за правилом:
.
Теорема 2.1. Якщо мультимножина є підмультимножиною мультимножини , то число
шляхів на діаграмі з рухом дорівнює
.
Доведення теореми 2.1. безпосередньо випливає із тверджень 1.6 та 2.2.
Наслідок. Число шляхів на діаграмі Ферре з рухом , де – мультимножина (1.1),
дорівнює
.
2.2. Сполучення на мультимножинах та елементи одного рангу діаграми Хассе
мультибулеана
Означення 2.1. Множину
(2.1)
всіх -підмультимножин мультимножини назвемо множиною -сполучень мультимножини
.
Для позначення потужності множини (2.1) будемо користуватися введеним в [3]
позначенням
. (2.2)
Для деяких специфікацій мультимножини (1.1) потужність множини підраховувалась
раніше (див., наприклад, [38], стор. 16-25; [39], стор. 16-18, 40-43). Зокрема,
для мультимножини із специфікацією (1.27), тобто для множин, маємо:
. (2.3)
Для мультимножин із специфікаціями із повтореннями без обмежень (1.25)
виконується рівність (див.[38]):
, (2.4)
а для мультимножин із сталою специфікацією (1.24) – рівність (див.[39]):
. (2.5)
В [39] наведено приклади ще двох типів мультимножин, для яких знайдено число
всіх -сполучень:
,
.
Наступна теорема дозволяє обчислювати потужність множини (2.1) в загальному
випадку.
Теорема 2.2. Число всіх -підмультимножин мультимножини дорівнює
, (2.6)
де – множина тих розв’язків рівняння
, (2.7)
які задовольняють нерівності
, (2.8)
, , – -тий елемент специфікації (1.8), спряженої до первинної специфікації
мультимножини .
Доведення. Розглянемо множину
(2.9)
вторинних специфікацій елементів множини (2.1). Із означення множини випливає,
що вона задовольняє умови:
1)
2) .
Доведемо, що множина складається з усіх цілих невід’ємних розв’язків рівняння
(2.7), які задовольняють нерівності (2.8).
Дійсно, нехай – деяка мультимножина, яка належить множині (2.1) і . Позаяк ,
то очевидно, що елементи цієї специфікації задовольняють рівняння (2.7).
Істинність нерівностей (2.8) для розв’язків цього рівняння випливає із
нерівності .
Нехай – деякий розв’язок рівняння (2.7), який задовольняє умови (2.8).
Побудуємо мультимножину таку, що . Почнемо з того, що виділимо із мультимножини
різних груп по однакових елементів. Це можна зробити завжди, бо , внаслідок
(1.8). Припустимо, що ми вже виділили різних груп елементів, кожна з яких
складається не менше ніж із однакових елементів. Позаяк – максимальне число
різних груп по однакових елементів, які можна виділити із мультимножини , то
після виділення із цієї мультимножини вказаних вище груп елементів, в ній, крім
інших груп, залишиться ще
груп по однакових елементів в кожній. Таким чином, виділення із мультимножини
наступних груп однакових елементів забезпечують виконання нерівностей (2.8).
Якщо тепер кожній вторинній специфікації із множини (2.9) поставити у
відповідність не порожню множину
(2.10)
мультимножин із множини (2.1) , то множина класів (2.10) при утворить розбиття
множини (2.1). При цьому буде виконуватися рівність
. (2.11)
Встановимо потужність множини (2.10). Вище вже було встановлено, що після
виділення із мультимножини (1.1) всіх груп однакових елементів, які складаються
не менше ніж із однакових елементів, в ній залишиться
груп по однакових елементів. Тому існує рівно
різних варіантів вибору цих груп із мультимножини . Число всіх елементів, які
належать множині (2.10), за правилом добутку дорівнює
(2.12)
Тут і далі . Зауважимо, що коли виконуються нерівності (1.4), то елементи
специфікації , крім співвідношення (1.8), можуть бути обчислені за однією з
наступних формул:
, (2.13)
де
(2.14)
– мінімальний прообраз тих елементів первинної специфікації , які не менші за ;
або
, (2.15)
де . Формула (2.15) випливає із співвідношення (1.19).
Із (2.11) і (2.12) випливає справедливість формули (2.6).
Приклад 2.1. Обчислимо число -підмультимножин мультимножини
.
Тут . Знаходимо елементи специфікації із співвідношень (1.8). Отримуємо: . Для
знаходження елементів множини випишемо всі розв’язки рівняння
. (2.16)
Їх десять:
Легко перевіряється, що всі вони задовольняють нерівності
Для кожного розв’язку рівняння обчислимо (2.16) добуток (2.12) і знайдемо суму
цих добутків :
Обчислимо число всіх - підмультимножин мультимножини, первинною специфікацією
якої є додатна цілочисельна функція натурального аргументу (1.21).
Теорема 2.3. Якщо мультимножина має первинну
специфікацію виду , причому , то при справедлива рівність
, (2.17)
де
.
Доведення. Перш за все відмітимо, що внаслідок нерівностей , , справедлива
рівність , і тому рівняння (2.7) і нерівності (2.8) матимуть відповідно вигляд
; (2.18)
. (2.19)
Доведемо, що кожен розв’язок рівняння (2.18) задовольняє н