Комбинаторные числа для подсчёта разбиений конечных мультимножеств

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

2013
Вычислительные методы в дискретной математике
№ 4(22)
УДК 519. 1
КОМБИНАТОРНЫЕ ЧИСЛА ДЛЯ ПОДСЧЁТА РАЗБИЕНИЙ КОНЕЧНЫХ МУЛЬТИМНОЖЕСТВ
В. В. Гоцуленко
Институт технической теплофизики НАН Украины, г. Киев, Украина
E-mail: gosul@ukr. net
Рассматриваются комбинаторные числа для подсчёта всех разбиений произвольного конечного мультимножества как в упорядоченную, так и в неупорядоченную сумму его подмультимножеств. Найдены производящие функции для введённых комбинаторных чисел и исследованы некоторые свойства этих чисел.
Ключевые слова: разбиения мультимножества, диофантовы уравнения, производящие функции.
В классическом смысле под разбиением [1,2] произвольного множества понимают его представление в виде объединения произвольного числа попарно непересекающих-ся подмножеств. Всякое представление натурального числа суммой натуральных чисел также называется разбиением этого числа. Разбиения конечных множеств изучаются в комбинаторике и теории чисел.
К основным комбинаторным задачам относятся задачи подсчёта и перечисления разбиений данного типа [1, 2]. Разбиения конечных множеств, а также подсчёт числа различных разбиений, удовлетворяющих тем или иным условиям, представляет особый интерес в комбинаторике. В частности, некоторые комбинаторные числа естественно возникают как количества разбиений того или иного вида. Например, число Стирлинга второго рода S (т, и) [1,2] представляет собой число неупорядоченных разбиений т-элементного множества на и частей. При этом мультиномиальный коэффи-
множества на и частей фиксированных размеров к, к2,…, кп. Отметим, что многие комбинаторные задачи приводят к вычислению числа способов разбиения т-элемент-ного множества на и подмножеств, среди которых допускаются и пустые подмножества. Однако в этом случае задача сводится к определению числа всех (неупорядоченных) разбиений заданного т-элементного множества на не более чем и непустых его подмножеств. Число всех неупорядоченных разбиений (без пустых подмножеств) т-элементного множества называется числом Белла Вт [1, 2].
Одно из возможных обобщений приведённых выше комбинаторных конструкций связано с допущением дублирования во множествах некоторых элементов, т. е. переход к мультимножествам.
1. Формализация комбинаторных чисел для подсчёта неупорядоченных
разбиений конечных мультимножеств
Обозначим через X = {та, т2а2,…, т"} исходное мультимножество, которое необходимо представить в виде неупорядоченной суммы и подмультимножеств Хк,
Введение
выражает число упорядоченных разбиений m-элементного
к = 1,…, п. Отметим также, что вектор первичной спецификации [4] каждого из под-мультимножеств Хк имеет вид
[к1, к2,…, kN]т, где 0 ^ кг ^ ш, г = 1,… ,
П
Для произвольного представления X = У Хк обозначим через Хкьк2,…, км число
к=1
подмультимножеств Хк с вектором первичной спецификации равным [к1, к2,…, к^]Т.
Набор целых неотрицательных чисел Хк1, к2,…, км, как несложно проверить, является решением системы линейных диофантовых уравнений:
? k1 m1
mi m2 mN xki, k2,…, kN k2 = m2
ki=0 k2=0 kN =0 kN
mN
ш m2
xki, k2,…, kN n-
^ ki=0 k2=0 kN =0
Данная система содержит (1 + mi) (1 + m2) … (1 + mN) неизвестных xki, k2,…, kN и N +1 уравнений.
Таким образом, задача сводится к определению числа всех целых неотрицательных решений системы уравнений (1). Обозначим данное число через S (m1,m2,…, mN- n).
Получим производящую функцию для введённых комбинаторных чисел S (m1,m2, …, mN- n). Рассмотрим для этого следующую промежуточную задачу. Обозначим через A = (aij)nxm произвольную матрицу с целыми неотрицательными элементами, через b = (bi)n — произвольный вектор-столбец с целыми неотрицательными элементами. Определим число всех целых неотрицательных решений системы линейных диофан-товых уравнений
ai1x1 + ai2x2 + … + aimxm bi, i 1.. , n. (2)
Данное число равно коэффициенту при t22 … в разложении в степенной ряд производящей функции
m
п (1 — taij ta2j --Х& quot-'-)-1. (з)
j=i
Для применения формулы (3) к определению числа целочисленных неотрицательных решений системы диофантовых уравнений (1) перенумеруем неизвестные xk1, k2,…, kN, ki = 0,1,•••, mi, i = 1,…, N, с помощью одного индекса. Одно из возможных таких взаимно однозначных соответствий, как несложно проверить, задаётся следующей последовательностью рекурсивно определяемых функций:
V (0 ^ i1 ^ m1, 0 ^ i2 ^ m2, • • •, 0 ^ iN ^ mN)
/2 (i1, i2) = i1 (m2 + 1) + i2 + 1,
/3 (i1, i2, ie) = /2 (i1,i2) + *3/2 (m1, m2) ,
/n (i1, i2, • • •, iw) = /n-1 (i1, i2, • • •, iN-1) + *n/n-1 (m1,m2, • • •, mN-1) •
Следовательно, задача (1) допускает представление в виде (2), если положить
А = («Ч)(М+1)х/м (Ш1,Ш2… ш№), Ь = (Ь»)м+1, (4)
где
Ур е {0,…, Ш1& gt-(а1й = р), к = (р, *2, *3,…, -1,), 0 ^ ^ ^ т8, 5 е {1,…, N} {1}-
Ур е {0,…, т2}(а2к = р), к = /^ (*1,р, *з,… ,*м-1,*м), 0 ^ г8 ^ т8, 5 е {1,…, N} {2}-
Ур е {0,…, ш^}(а^, к = р), к = /^ (*1, *2,… ,*м-1,р), 0 ^ ^ т8, 5 е {1,…, N — 1}-
«N+1,*: = 1, к = 1,… / (то1,Ш2,…, ш^) —
Ь* = т*, к = 1,…, N- 6м+1 = п.
Таким образом, полагая
/^ (т1,т2.
Фш1, ш2,., ГО» (^1,^2,… ,^М+1)= П (1 — С'- ^ … *^++11'-0 ,
.7 = 1
где элементы матрицы, А определяются формулами (4), получаем, что число S (т1, т2,… , — п) равно коэффициенту приЩ74 … %+1 в разложении функции
Фш1, ш2,… ,^ (^1, ^2,…, ^N+0 в степенной ряд, т. е. имеет место равенство
^ (т1, т2,…, -п) = С?^-:. :-^ ^
где
Т/ (+ + + _ ,/|т1,т2. -п у-г1у-г2 4-rN^rN+1
*т1,Ш2… (11, 12,.. , ^N+1) гп, г2… гN, гм+111 12.. +1.
rl,…, rN+10
Для введённых комбинаторных чисел справедлива формула
N
5 (т1, т2,…, тМ- т) = 5 (т1, т2,…, тМ- п) для всех т ^ п = ^ т^. (5)
г=1
N
Действительно, если п = X] т", то в этом случае лишь одно разбиение, состоящее из
г=1
N
одноэлементных множеств, не содержит пустых множеств. Поэтому при п & gt- X] т" все
г=1
разбиения мультимножества X = {т1а1,т2а2,…, mN} получаются путём добавле-
N N
ния п — У2 т" пустых множеств в каждое разбиение при п = ^ т", что устанавливает
г=1 г=1
взаимно однозначное соответствие между рассматриваемыми разбиениями и, таким образом, доказывает формулу (5).
Далее рассматриваются некоторые частные случаи и примеры вычисления рассмотренных комбинаторных чисел.
Пример 1. Полагая т" = 1 для всех * = 1,…, N, получаем, что комбинаторное число 5 (т1,т2,…, тя- п) определяет число всех неупорядоченных п-эле-ментных разбиений N-элементного множества. Поэтому при п = N получаем, что 5 (1,1,…, 1- п) =, где — число Белла.
Как частный случай формулы (5), получаем
5 (1,1,…, 1- т) = 5 (1,1,…, 1- п) для всех т ^ п, п е N.
В данном случае элементы матрицы (4) лежат в булеане {0,1} и легко вычисляются, так как рекурсивная функция ^ (*1, *2, *3,…, ^) допускает представление в явной форме
N
/м (*1, *2, *3, • • • ,) — 1 + 2І1 + *2 + 2 Є {0,1}, в — 1,…, N.
к=3
Например, для случая N — 3 матрица (4) имеет вид
А
0 0 1 1 0 0 1 1 1 010 101 0 0 0 0 1 1 1 1 11 111 111
Следовательно, коэффициент при *1*2*з*4 в разложении в степенной ряд производящей функции
(1 — *3*4) (1 — *2*3*4) (1 — *1*3*4) (1 — *1*2*3*4)
(1 — *4) (1 — *2*4) (1 — *1*4) (1 — *1*2*4)
1
определяет комбинаторное число
S (1,1, 1- п) —
1, если п — 1,
2, если п — 2, 5, если п & gt- 3.
Пример 2. Предположим, что имеется т1 предметов вида а1 и т2 предметов вида а2. Рассмотрим задачу определения числа способов разложения этих предметов по п одинаковым коробкам без каких-либо ограничений.
Таким образом, необходимо найти число способов разложения мультимножества
П
X — {т1а1,т2а2} в неупорядоченную сумму п его подмультимножеств X — и {Х& amp-}.
к=1
В этом случае формулы (4) (при N — 2) приводят к следующему результату:
А — (аЧ)
& quot-Ч '- 3х (ті+1)(т2+1)
Ь — (Ьг)г
где
Ур е {0,…, т1}(а1* = р) при р (т2 + 1) + 1 ^ к ^ (р +1) (т2 + 1) — Ур е {0,…, т2}(а2к = р) при к = * (т2 + 1) + р + 1, * = 0,…, т1- аз* = 1, к = 1,…, (т1 + 1)(т2 + 1) — 61 = т1,62 = т2, 63 = п.
Например, если т1 = 1 и т2 = 3, то матрица, А имеет вид
А
0 0 0 0 1 1 1 1 1 230 123 11 111 111
и, следовательно, комбинаторное число 5 (1, 3- п) определяется как коэффициент при *1*2*? в разложении в степенной ряд производящей функции
(1 — *1*з)-1 (1 — *1*2 *з)-1 (1 — *1*2*3)-1 (1 — *1 *2*з)-1 (1 — *3) (1 — *2*3) (1 — *2*3) (1 — *2*3)
Элементарные подсчёты показывают, что
Б (1, 3- п)
1, если п = 1, 4, если п = 2,
6, если п = 3,
7, если п ^ 4.
2. Формализация комбинаторных чисел для подсчёта упорядоченных разбиений конечных мультимножеств
Обозначим Б (т1,т2,…, т^- п) число всех упорядоченных п-элементных разбиений мультимножества X = {т1а1, т2а2,…, }, предполагая, что допускаются
повторения подмультимножеств, а также пустые подмультимножества. Зафиксируем произвольное упорядоченное разбиение {Х^: г = 1,…, п} мультимножества X. Обозначим через [к1г, к2г,…, & amp-№], 0 ^ ^ т, 5 = 1,…, N, вектор первичной специфи-
кации подмультимножества Хг.
Тогда каждое упорядоченное разбиение мультимножества X однозначно задаётся следующей матрицей:
к11 к12.. к1п
к21 к22.. к2п
При этом из равенства и Хг = X следует, что элементы данной матрицы должны
г=1
быть решениями в целых неотрицательных числах системы линейных уравнений
П
Е ку = тг, г = 1,…, N. (6)
.7 = 1
Переименуем неизвестные ку одним индексом с помощью отображения (г,_7) ^ ^ (г — 1) п + [5] и запишем систему (6) в стандартной форме
где
Е «і?Ху = т*, і = 1, у=1
1, если (і - 1) п +1 ^ І ^ іп,.
X,
1, • • •, X, і = 1, • • •, Хп.
7)
0 в остальных случаях,
Таким образом, из соотношений (2)-(3), (7) следует, что комбинаторное число Б (т1, т2, …, т^- п) равно коэффициенту прит-1 в разложении в степенной
ряд производящей функции
((1 — У» (1 — «2)» ¦¦¦ (1 —)")
1
Наконец, используя разложение
1
(1 —
*=0
Е (-1)М, Г Ь*
получим
Б (т1, т2, • • •, — п) = (-1)
ті+т2+.-. +тм І п I п т1 т2
-п
тм
Замечание. Отметим, что формула для подсчёта упорядоченных разбиений конечных мультимножеств может быть получена без применения формул (2)-(3). Действительно, окончательно задача сводится к определению числа всех целых неотрицательных решений системы линейных диофантовых уравнений (6). Несложно проверить, что данное число равно коэффициенту при г1 *™2. . *™^ в стандартном разложении по возрастающим степеням г1 *22 … производящей функции
1 п / 1 у / 1 п 1 — V и — V & quot-л 1 —.
Отсюда, воспользовавшись тождеством
п + к — 1 ^ получаем
а, (п + т1 — 1 / п + т2 — 1 / п + - 1
Б (т1,Ш2,…, т^- п) = ….
V т1 / V т2) V т" /
Заключение
В данной работе задача о подсчёте числа различных разбиений конечного мультимножества сведена к определению числа всех целых неотрицательных решений соответствующей системы линейных диофантовых уравнений с многоиндексной нумерацией неизвестных. Полученные соотношения (4) позволяют представить данную систему в стандартной форме (2), для которой известен явный вид производящей функции (3). Это позволило получить производящие функции для рассматриваемых комбинаторных чисел и исследовать некоторые их свойства. При этом для числа всех разбиений произвольного конечного мультимножества в упорядоченную сумму его подмульти-множеств получены явные формулы.
Отметим, что для практики, безусловно, важны не только формулы (или алгоритмы) вычисления тех или иных комбинаторных чисел, но и оценки и асимптотики этих чисел [6]. Однако вопросы, связанные с эффективностью реализации вычислений с помощью полученных соотношений, требуют дальнейшего исследования.
ЛИТЕРАТУРА
1. Стенли Р. Перечислительная комбинаторика. М.: Мир, 1990. 400 с.
2. Новиков Ф. А. Дискретная математика для программистов. СПб.: Питер, 2009. 384 с.
3. Виленкин Н. Я. Комбинаторика. М.: Наука, 1969. 323 с.
4. Заторский Р. А. Подсчет т-подмультимножеств через их вторичные спецификации / под ред. К. А. Рыбникова // Комбинаторный анализ. М.: МГУ, 1986. Вып. 7. С. 136−145.
5. Гоцуленко В. В. Формула для числа сочетаний с повторениями при ограничениях и её применение // Прикладная дискретная математика. 2013. № 2(20). С. 71−77.
6. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986. 384 с.
1 — г
Ж / Е
к=0 V
п
1

ПоказатьСвернуть
Заполнить форму текущей работой