Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
каждое разбиение повторится ровно У У * * - У (П) 1 X
Х{2!) 2. *. (я!) п раз. Теорема доказана.
Мы уже видели, что разбиения множества Е связапы с наборами (аи ..ап). Выберем г значений из множества (0, 1, ..., к —1>. Пусть это будут к1г кг, кг.
Очевидно, таких выборов будет Возьмем произвольное разбиепие Е на г частей. Число разбиений равно Ф(я, г). Если нумеровать компоненты разбиений числами ки к2, кг (г! способов), то мы получим всевоз-
можные наборы длины п, содержащие ровно г значений к и к2, ..., К. Очевидно, что каждый набор при этом будет построен ровно один раз. Поэтому
к"-2(*)/-1Ф (я, г). (18)
Если теперь сравнить соответствующие слагаемые в (15) и (18), то из рассуждения можно увидеть, что они выражают одно и то же число. Отсюда получаем еще одно ЯЕное выражение для Ф(я, г) (я, г > 0):
Ф К г) = 7[ ^ Ты ... л | ?
и1+/?г+...+яг=1г ха п1,па,..1,иг>о
Полненные формулы для Ф(щ к) практически не пригодны для вычисления Ф{и, к), так как они предполагают знание всех решений уравнения (14) или (17). Эффективные способы вычислении чисел Стирлинга 2-го рода и изучение их свойств связано с установлением ряда рекуррентных соотношений для Ф(», к).
186
Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ
Возьмем произвольное разбиение Е па к непустых подмножеств и выбросим одну из компонент (что возможно к способами). Оставшаяся часть множества Е имеет мощность ? (&— 1«??^гс — 1) и разбита на к— 1 частей. Таким образом, разбиению Е на к непустых подмножеств соответствует к разбиений множеств мощности, меньшей или равной п — 1, на к — 1 часть. С другой стороны, если взять произвольное собственное подмножество в Е и выбрать в нем любое разбиение на к — 1 непустую часть, то оно может быть однозначно продолжено до разбиения множества Е на к непустых частей.
Отсюда *)
5] (")фм —1)
1N. 1 /
ИЛИ
И>(пД)=2 (")ф((,Ь-1). (20)
1=0 ^ 1 >
Несколько видоизменим предыдущее рассуждение* В произвольном разбиении Е на к непустых подмножеств, выбросим ту компоненту, которая содержит фиксированный элемент а„ (ап&Е). Тогда этому разбиению однозначным образом соответствует разбиение на к — 1 непустых подмножеств некоторого множества из ? элементов (к — 1 ^ ? < п — 1). Справедливо и обратное утверждение: любое разбиение на к — 1 непустых частей произвольного подмножества из Е, не содержащего яп, однозначным образом продолжается до разбиения множества Е на к непустых частей.
Поэтому
Ф (щ к) = 2 (" 7 О ф А — 1)
1=А-1 V 1 *
ИЛИ
ф (« ,*) =?(" 7 *)ф <и-1). (21)
Почленно суммируя по к полученное тождество и учитывая (16), имеем
Ф(»)= 2'(п7,)ф{;). (22)
г =0 ' * *
*) Эта формула верпа и при А- = 1, что вытекает из краевых условий (см. с. 184).
Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ
187
Заметим, что произвольное разбиепие Е на к непу-» стых частей получается:
а) либо из разбиения множества Е\ап на к — 1 непустую часть добавлением подмножества {а„};
б) либо из разбиения множества Е\ап на к непустых частей путем добавления к одной из них элемента ап {к способов).
Отсюда получаем тождество
Ф(га, ?)=Ф(л— 1, к — 1)+ АФ(п — 1, к). (23)
Оно позволяет построить таблицу для чисел Ф(и, к) (с линейной сложностью) и чисел Белла.
Таблица 3
п к
0 1 2 3 4 5 6 7 8- 9 . . . Ф(л)
0 1 1
1 0 1 1
2 0 1 1 0 2
3 0 1 3 1 5
4 0 1 7 6 1 15
5 0 1 15 25 10 1 52
6 0 1 31 90 65 15 1 203
7 0 1 63 301 350 140 21 1 877
8 0 1 127 966 1701 1050 266 28 1 4140
9 0 1 255 3025 7770 6951 2646 462 36 1 21147
Опираясь на рекуррентные соотношения для чисел к), докажем следующий факт.
Теорема 4. Последовательность {Ф(/г, &)} при фиксированном п и к = 0, 1, ..п унимодальна', существует
160
-±. 11. шжьдидид'шш лил л п а
такое кщ что
Ф(п, 0)< Ф(и, 1)<Ф(п, 2)<...<Ф(га, К)>
> Ф(пл кп + 1)> ... > Ф(щ п),
и кп — кп-1 или кп = + 1.
Доказательство. Ведем ипдукцией по п. При п — 2 утверждение очевидно (см. табл. 3).
Индуктивный переход от п — 1 к п.
а) Пусть 2^к^ Используя (23), имеем
Ф (н, А) — Ф(и, А — 1) =*
-(Ф(л-1, к — 1) — Ф(н — 1, А-2)) +
+ &(Ф(н—1, А-) — ф(гг — 1, к— 1))+Ф(п— 1, к — 1)>0.
б) Пусть + 2 ^ к ^ п. Используя (21) и учитывая, что ^ кп-1 при Кп — 1, имеем
х(Ф(;д-1)-Ф(гД-2))<о.
Сравним теперь величины Ф(», и Ф(н, Ап-11).
Если Ф(п, А„_,)>Ф(/г, Ап_1+1), :то полагаем Ап=» = к«-и
Если Ф(и, А11_1)<Ф(«, А„-1 + 1), то полагаем кп =* = +? 1.
Утверждение доказано.
Уже первое знакомство с комбинаторными объектами показывает, что мы сталкиваемся с общими задачами: такими, как задача о построении комбинаторных объектов и чисел (задача о перечислении), как задача о построении комбинаторных тождеств, как задача об изучении свойств комбинаторных чисел (например, наличие унимодальности) и т. п.
§ 3. Методы изучения комбинаторных объектов и чисел
В комбинаторном анализе существует целый ряд подходов для изучения комбинаторных объектов и чисел.
Теоретико-множественный подход. Он связан с вычислениями мощностей коночных подмножеств.
Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ 189
Пусть Ах, ..., Ап — система подмножеств конечного множества А. Обозначим через Я, (? = 0, п) совокупность всех элементов из А, которые содержатся ровно в ? множествах системы, и через Сх (? = 0, 1, п) — совокупность всех элементов из А, которые принадлежат ве менее чем I множествам системы. Очевидно, что
