Комбинаторные числа для подсчёта разбиений конечных мультимножеств | ПДМ. 2013. № 4(22).

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

Рассматриваются комбинаторные числа для подсчёта всех разбиений произвольного конечного мультимножества как в упорядоченную, так и в неупорядоченную сумму его подмультимножеств. Найдены производящие функции для введённых комбинаторных чисел и исследованы некоторые свойства этих чисел.

Combinatorial numbers of the finite multiset partitions.pdf Введение В классическом смысле под разбиением [1,2] произвольного множества понимают его представление в виде объединения произвольного числа попарно непересекающихся подмножеств. Всякое представление натурального числа суммой натуральных чисел также называется разбиением этого числа. Разбиения конечных множеств изучаются в комбинаторике и теории чисел. К основным комбинаторным задачам относятся задачи подсчёта и перечисления разбиений данного типа [1, 2]. Разбиения конечных множеств, а также подсчёт числа различных разбиений, удовлетворяющих тем или иным условиям, представляет особый интерес в комбинаторике. В частности, некоторые комбинаторные числа естественно возникают как количества разбиений того или иного вида. Например, число Стирлинга второго рода S (m, n) [1,2] представляет собой число неупорядоченных разбиений m-элементного множества на n частей. При этом мультиномиальный коэффивыражает число упорядоченных разбиений m-элементного множества на n частей фиксированных размеров ki, k2,... , kn. Отметим, что многие комбинаторные задачи приводят к вычислению числа способов разбиения m-элемент-ного множества на n подмножеств, среди которых допускаются и пустые подмножества. Однако в этом случае задача сводится к определению числа всех (неупорядоченных) разбиений заданного m-элементного множества на не более чем n непустых его подмножеств. Число всех неупорядоченных разбиений (без пустых подмножеств) m-элементного множества называется числом Белла Bm [1, 2]. Одно из возможных обобщений приведённых выше комбинаторных конструкций связано с допущением дублирования во множествах некоторых элементов, т. е. переход к мультимножествам. 1. Формализация комбинаторных чисел для подсчёта неупорядоченных разбиений конечных мультимножеств Обозначим через X = {m1a1, m2a2,..., mNaN} исходное мультимножество, которое необходимо представить в виде неупорядоченной суммы n подмультимножеств Хд, k = 1,..., n. Отметим также, что вектор первичной спецификации [4] каждого из под-мультимножеств Xfc имеет вид [ki, k2,..., kN]T , где 0 ^ k ^ m^ i = 1,..., N. n Для произвольного представления X = У Xk обозначим через Xkbk2,...,kN число k=1 подмультимножеств Xk с вектором первичной спецификации равным [k1, k2,... , k^]T. Набор целых неотрицательных чисел Xkbk2,...,kN, как несложно проверить, является решением системы линейных диофантовых уравнений: ✓ k1 m1 m1 m2 mN У! . . . Yj xki,k2,...,kN k2 = m2 ki=0 k2=0 kN =0 kw _ mw _ m1 m2 mN Yj S . . . S xki,k2,...,kN n. „ ki=0 k2=0 kN =0 Данная система содержит (1 + m1) (1 + m2)... (1 + mw) неизвестных Xk1,k2,...,kN и N +1 уравнений. Таким образом, задача сводится к определению числа всех целых неотрицательных решений системы уравнений (1). Обозначим данное число через S (m1, m2,... , mw; n). Получим производящую функцию для введённых комбинаторных чисел S (m1,m2, ... ; n). Рассмотрим для этого следующую промежуточную задачу. Обозначим через A = (aij)nxm произвольную матрицу с целыми неотрицательными элементами, через b = (bi)n — произвольный вектор-столбец с целыми неотрицательными элементами. Определим число всех целых неотрицательных решений системы линейных диофан-товых уравнений + ai2^2 + ... + aimxm = bi, i = 1,..., n. (2) Данное число равно коэффициенту при ^ t22 ... ^П" в разложении в степенной ряд производящей функции m п (1 - с ta2j ...с)-1. (з) j=1 Для применения формулы (3) к определению числа целочисленных неотрицательных решений системы диофантовых уравнений (1) перенумеруем неизвестные Xk1,k2,...,kN, ki = 0,1,...,mi, i = 1,...,N, с помощью одного индекса. Одно из возможных таких взаимно однозначных соответствий, как несложно проверить, задаётся следующей последовательностью рекурсивно определяемых функций: V (0 ^ i1 ^ m1, 0 ^ i2 ^ m2,..., 0 ^ iN ^ mw) /2 (i1, i2) = i1 (m2 + 1) + i2 + 1, /3 (i1, i2, ie) = /2 (i1,i2) + is/2 (m1,m2), /n (i1,i2,... ,iw) = /w-1 (i1,i2,... ,iw-1) + iw/w-1 (m1,m2,... ,mw-1). Следовательно, задача (1) допускает представление в виде (2), если положить A = )(n+1)x/n(mi,m2.....) ' Ь = (bi)w+1 , (4) где Vp G {0,..., m1>(a1fc = p), k = fw (p, «2, «з, •. •, iw-1, iw), 0 ^ is ^ mS)s G {1,..., N} \ {1}; Vp G {0,... ,m,2}(a2fc = p), k = fw («1,Р,«з,..., iw-1,iw), 0 ^ is ^ ms,s G {1,..., N} \ {2}; Vp G {0,... ,mw}(aw,fc = p), k = fw (i1,i2,..., iw-1,p) , 0 ^ is ^ ms,s G {1,..., N - 1}; aw+1,k = 1, k = 1,... ,fw (mbm2,.. .,mw); bfc = mfc, k = 1,..., N; bw+1 = n. Таким образом, полагая /v (mi,m2.....mN) _ 1 ^mi,m2,...,mN (t1, ^2, . . . , ^w+1) = П (1 — ^^ ^^ •••tNvkL1j) , j=1 где элементы матрицы A определяются формулами (4), получаем, что число S (m1, m2,... , mw; n) равно коэффициенту при t^1 .. - tmV tjv+1 в разложении функции ^mi,m2,...,mv (t1, t2,... , tw+1) в степенной ряд, т. е. имеет место равенство s (m1,m2i..., mw; n) = ^mi;m2;...;mvv где ltr i \ _ v1 ,(,mi;m2.....mvj-п ,r2 j-rvj-rV+1 ¥mi,m2.....mv (t1, l2, - - - , ^w+1) = Гп,г2.....rv,rv+1П l2 - . - lw +1 . ri,...,rv+1^0 Для введённых комбинаторных чисел справедлива формула w S (m1, m2,..., mw; m) = S (m1, m2,..., mw; n) для всех m ^ n = £ m^ (5) i=1 w Действительно, если n = £ mi, то в этом случае лишь одно разбиение, состоящее из i=1 w одноэлементных множеств, не содержит пустых множеств. Поэтому при n > £ mi все i=1 разбиения мультимножества X = {m1a1,m2a2,... , mwaw} получаются путём добавлеw w ния n - mi пустых множеств в каждое разбиение при n = mi, что устанавливает i=1 i=1 взаимно однозначное соответствие между рассматриваемыми разбиениями и, таким образом, доказывает формулу (5). Далее рассматриваются некоторые частные случаи и примеры вычисления рассмотренных комбинаторных чисел. Пример 1. Полагая mi = 1 для всех i = 1,...,N, получаем, что комбинаторное число S (m1,m2,...,mw; n) определяет число всех неупорядоченных n-эле-ментных разбиений N-элементного множества. Поэтому при n = N получаем, что S (1,1,..., 1; n) = , где — число Белла. Как частный случай формулы (5), получаем S (1,1,..., 1; m) = S (1,1,..., 1; n) для всех m ^ n, n G N. В данном случае элементы матрицы (4) лежат в булеане {0,1} и легко вычисляются, так как рекурсивная функция /n (i1, i2, i3,... , iw) допускает представление в явной форме N /n (i1, i2, is,..., iN) = 1 + 2i1 + i2 + E 2 ik, is G {0,1} , s = 1,..., N. k=3 Например, для случая N = 3 матрица (4) имеет вид A 1 S (1, 1, 1; n) = 0 0 1 1 0 0 1 1 01010101 0 0 0 0 1 1 1 1 11111111 Следовательно, коэффициент при 11t2t3tn в разложении в степенной ряд производящей функции (1 - tstQ 1 (1 - t2*3*4) (1 - *1*3*4) (1 - *1*2*3*4) (1 - t4) (1 - *2*4) (1 - *1*4) (1 - W4) определяет комбинаторное число 1 , если n = 1 , 2, если n = 2, 5, если n > 3. Пример 2. Предположим, что имеется m1 предметов вида a1 и m2 предметов вида a2. Рассмотрим задачу определения числа способов разложения этих предметов по n одинаковым коробкам без каких-либо ограничений. Таким образом, необходимо найти число способов разложения мультимножества n X = {m1a1,m2a2} в неупорядоченную сумму n его подмультимножеств X = (J {Xk}. k=1 В этом случае формулы (4) (при N = 2) приводят к следующему результату: j 3x(mi+1)(m2+1) A = (aj) Ь = (bi); где Vp G {0,..., m1}(a1k = p) при p (m2 + 1) + 1 ^ k ^ (p +1) (m2 + 1); Vp G {0,..., m2}(a2k = p) при k = i (m2 + 1) + p + 1, i = 0,..., m1; a3k = 1, k = 1,..., (m1 + 1)(m2 + 1); b1 = m1 ,b2 = m2, b3 = n. Например, если m1 = 1 и m2 = 3, то матрица A имеет вид A 0 0 0 0 1 1 1 1 01230123 11111111 и, следовательно, комбинаторное число S (1, 3; n) определяется как коэффициент при t1t2tn в разложении в степенной ряд производящей функции (1 - М3)-1 (1 - М213)-1 (1 - t1t2t3)-1 (1 - t1 ^2^3)-1 (1 - t3)(1 - *2*3) (1 - t|t3> (1 - *2*3) . 1, если n = 1, 4, если n = 2, 6, если n = 3, 7, если n ^ 4. 2. Формализация комбинаторных чисел для подсчёта упорядоченных разбиений конечных мультимножеств Обозначим S (mi,m2,... ,mN; n) число всех упорядоченных n-элементных разбиений мультимножества X = {miai, m2a2,..., mNaN}, предполагая, что допускаются повторения подмультимножеств, а также пустые подмультимножества. Зафиксируем произвольное упорядоченное разбиение {X^ : i = 1,... ,n} мультимножества X. Обозначим через [kii, k2j,..., kNj ], 0 ^ ^ ms, s = 1,..., N, вектор первичной спецификации подмультимножества Xj. Тогда каждое упорядоченное разбиение мультимножества X однозначно задаётся следующей матрицей: kii ki2 ... kin k2i k22 . . . k2n Nn kN i kN 2 ... k При этом из равенства U Xj = X следует, что элементы данной матрицы должны j=i быть решениями в целых неотрицательных числах системы линейных уравнений n J2 kij = mj, i = 1,..., N. (6) ]=i S(1, 3; n) Элементарные подсчёты показывают, что Переименуем неизвестные к] одним индексом с помощью отображения (i,j) ^ ^ (i — 1) n + j [5] и запишем систему (6) в стандартной форме N, Nn £ aj]X] = mj, i = 1, ]=i где 1, если (i — 1) n +1 ^ j ^ in, . 7) И] 1, . . . , N, j = 1, . . . , Nn. 0 в остальных случаях, Таким образом, из соотношений (2)-(3), (7) следует, что комбинаторное число S (mi, m2,... , mN; n) равно коэффициенту при t^1t™2 ... t™N в разложении в степенной ряд производящей функции i ((1 — ti)n (1 — t2)n ... (1 — tN )П) Наконец, используя разложение Е(—1)М ,r )tfc 1 (1 — t)r fc=Q получим mi+m2+-+m^ n i i n mi m2 -n mN S (mi, m2, ...,mN; n) = (—1) Замечание. Отметим, что формула для подсчёта упорядоченных разбиений конечных мультимножеств может быть получена без применения формул (2)-(3). Действительно, окончательно задача сводится к определению числа всех целых неотрицательных решений системы линейных диофантовых уравнений (6). Несложно проверить, что данное число равно коэффициенту при t^74 tm2 .. . tmN в стандартном разложении по возрастающим степеням t^4 t^2 ... tN производящей функции 1 1 - tw 1 t1 1 - t2 Отсюда, воспользовавшись тождеством g / n + k - 1 n 1 k t k 1t k=0 получаем n + m1 - 1 m1 n + m2 - 1 m2 n + mw - 1 mw S (m1, m2,..., mN; n) Заключение В данной работе задача о подсчёте числа различных разбиений конечного мультимножества сведена к определению числа всех целых неотрицательных решений соответствующей системы линейных диофантовых уравнений с многоиндексной нумерацией неизвестных. Полученные соотношения (4) позволяют представить данную систему в стандартной форме (2), для которой известен явный вид производящей функции (3). Это позволило получить производящие функции для рассматриваемых комбинаторных чисел и исследовать некоторые их свойства. При этом для числа всех разбиений произвольного конечного мультимножества в упорядоченную сумму его подмульти-множеств получены явные формулы. Отметим, что для практики, безусловно, важны не только формулы (или алгоритмы) вычисления тех или иных комбинаторных чисел, но и оценки и асимптотики этих чисел [6]. Однако вопросы, связанные с эффективностью реализации вычислений с помощью полученных соотношений, требуют дальнейшего исследования.

Ключевые слова

разбиения мультимножества, диофантовы уравнения, производящие функции, multiset partitions, Diophantine equations, generating functions

Авторы

ФИООрганизацияДополнительноE-mail
Гоцуленко Владимир ВладимировичИнститут технической теплофизики Национальной академии наук Украины (г. Киев)старший науный сотрудник, кандидат технических наук, старший научный сотрудник отдела теплофизических основ энергосберегающих теплотехнологийgosul@ukr.net
Всего: 1

Ссылки

Стенли Р. Перечислительная комбинаторика. М.: Мир, 1990. 400 с.
Новиков Ф. А. Дискретная математика для программистов. СПб.: Питер, 2009. 384 с.
Виленкин Н. Я. Комбинаторика. М.: Наука, 1969. 323 с.
Заторский Р. А. Подсчет m-подмультимножеств через их вторичные спецификации / под ред. К. А. Рыбникова // Комбинаторный анализ. М.: МГУ, 1986. Вып. 7. С. 136-145.
Гоцуленко В. В. Формула для числа сочетаний с повторениями при ограничениях и её применение // Прикладная дискретная математика. 2013. №2(20). С. 71-77.
Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986. 384 с.
 Комбинаторные числа для подсчёта разбиений конечных мультимножеств | ПДМ. 2013. № 4(22).

Комбинаторные числа для подсчёта разбиений конечных мультимножеств | ПДМ. 2013. № 4(22).

Полнотекстовая версия