Определение числа разложений конечного множества

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


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

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

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

96
НАУЧНЫЕ ВЕДОМОСТИ
Серия: Математика. Физика. 2015. № 5(202). Вып. 38
MSC 05А18
ОПРЕДЕЛЕНИЕ ЧИСЛА РАЗЛОЖЕНИЙ КОНЕЧНОГО МНОЖЕСТВА
Ю. П. Вирченко, Л.П. Остапенко
Белгородский государственный университет, ул. Студенческая, 14, 308 007, г. Белгород, e-mail: GlushakQbsu. edu. ru
Аннотация. Рассматривается комбинаторная задача о числе разложений Mn произвольного конечного множества из n элементов. Вычисляется производящая функция числа Mn, n € N.
Ключевые слова: разложения конечного множества, производящая функция, симметричные функции, бесконечномерная алгебра.
1. Разложения конечного множества. Пусть In = (1,2,…, n} - стандартное n-элементное множество. Разложением множества In называется неупорядоченный набор непустых множеств Wj, j = 1У в, которые называются компонентами этого разложения и которые составляют диъюнктивное разложение множества In:
S
|^J Wi — I, n, Wj П = 0, j = k, j, k — 1 — в.
i=i
Число в компонент разложения называется его мощностью.
Обозначим посредством Mn значения функции от n € N, равные числу всех возможных разложений множества In для фиксированного значения n € N. Следующий пример поясняет смысл введенных понятий.
Пример:
1. n =1 Ii = {1}. Имеется только одно разложение с в = 1 w = I = (1} Mi = 1.
2. n = 2, I2 = (1, 2}. Имеется два разложения с в = 1 w1 = I2 и с в = 2, w1 = (1}, w2 = (2} M2 = 2.
3. n = 3 I3 = (1,2, 3}. Имеется пять разложений с в =1 w1 = I3 и с в = 2: w1 = (1},
W2 = (2, 3} W1 = (1, 2} W2 = (3} W1 = (1, 3} W2 = (2} С в = 3 W1 = (1}, W2 = (2},
W3 = (3} Мз = 5.
В связи с понятием разложения, естественным образом, возникает комбинаторная задача о вычислении числа разложений Mn для каждого значения n € N. Эта задача тесно связана с некоторыми вопросами статистической механики (см. [1]). Настоящее сообщение посвящено решению этой задачи, которое понимается как вычисление производящей функции (см., например, [2])
G (z) = ?
n=0
-Г М"
n!
Mn
dnG (z)
dzn) z=o'
(1)
соответствующей комбинаторной функции Mn, где, по определению, M0 = 1.
НАУЧНЫЕ ВЕДОМОСТИ |^Ц Серия: Математика. Физика. 2015. № 5(202). Выл. 38 97
2. Алгебра последовательностей симметричных функций. Вычисление функции G (z) будет выполнено на основе специальной алгебраической техники, используемой в статистической механике (см., например, [1]), возникновение которой было связано с преобразованиями статистических сумм [3].
Рассмотрим линейное пространство бесконечных последовательностей Ф = (& lt-^m- m G N+), в которых каждая ком понентаm при люб ом m G N+ является симметричной измеримой функцией на [0,1]m со значениями в Rm (Xm) =m (xi, x2, xm), Xm = (x1,x2,…, xm), При этом для значения m =0 такие функции, полагаются константами. Это линейное пространство превращается в коммутативную алгебру A при определении на нем следующей бинарной операции *. Для каждой пары Ф = (& lt-^m- m G N+) и I = (^m- m G N+) последовательностей из A построим последовательность Ф * Ф, компоненты которой определяются формулой (см. [1])
(Ф * I) n (X (/")) =? & lt-?m (XMWv"w|(X (In ш)), (1)
W0l~n
в которой использованы следующие обозначения: X (ш) = (xi1, xi2 ,…, xis) для каждого ш = {i1,i2, …, is} С In и |ш| = s — число элементов в ш.
Очевидно, что функции (Ф * I) n (x1,x2,…, xn) симметричны при любом n G N и, таким образом, результатом применения операции * к двум последовательноетям Ф и Ф снова является последовательность симметричных функций. Очевидным образом операция * является коммутативным умножением, так как удовлетворяет всем свойствам, предъявляемым к умножению в общеалгебраическом смысле. Таким образом, линейное пространство A, снабженное операцией * является бесконечномерной коммутативной алгеброй. Единицей алгебры A является последовател ьность 1 = (1, 0, 0,…),
В алгебре A имеется идеал А0, который состоит го поеледовательноетей Ф функций с = 0. Для элементов Ф этого идеала рассмотрим степень Ф^ ^юбым m G N. Тогда компоненты ^m)n этой последовательности равны нулю при n & gt- m. Если же n & lt- m, то эти компоненты даются формулой
(ФГ),(Х (In)) = m!? V|", |(X (Ш1))Р|"2|(Х (Ш2))… ^|w"|(X (ш",)),
W1:
WiU^2U… Uwm=/n,
Wj = 0, Wj
то есть суммирование в правой части формулы производится по разложениям множества In, содержащим р овно m компонент. Тогда для эл ементов Ф та идеал a A0 имеет место формула
(ехр, ф) п (МУ) = (lWX («) + (*)JX (W) + i („)JX (/.“ + i (^)"(X (/.)) + … =
= 0wi|(X (ш1))^|Ш2|(Х (ш2)) •••^|ws |(Х (шs)), (2)
wi,…, ws:
WiUW2U… UWs=1n ,
Wj=0, Wj nwk=0
98
НАУЧНЫЕ ВЕДОМОСТИ
Серия: Математика. Физика. 2015. № 5(202). Вып. 38
где суммирование производится по веем разложениям множества In с любым допустимым числом s = 1,…, n компонент.
Так как
Mn = Y, 1,
и1:
и 1 U U2 U… U Us=In ,
Uj =0, Uj П Ufc=0
то из (2) следует, что
Mn = (exp* (In)), х = (0,1,1,…) = 1 — So, n, n G N+
для любой точки Xn G [0,1]n, Эта формула является основой для вычисления производящей функции G (z).
Введем линейную форму L (z- •) на алгебре A, зависящую от параметра z G C. Для каждого элемента Ф алгебры A значение L (z- Ф) этой формы определяется формулой
L{z- Ф) = 5]^ Vn (Xn)dXn, (3)
n=0 [0,1]n
где dXn = dx1dx2… dxn — мера Лебега на [0,1]n, Эти значения заведомо конечны в том случае, когда последовательность функций Ф равномерно ограничена.
Теорема 1. Форма L мультипликативна, то есть для каждой пары элементов (Ф, Ф) с равномерно ограниченными элементами имеет место равенство
L (z- Ф * Ф) = L (z^)L (z^). (4)
? Доказательство проводится приводимым ниже прямым вычислением, в котором все ряды равномерно сходятся, ввиду предполагаемой равномерной ограниченности. Согласно определению (1),
ОО n л
L{z- Ф*Ф) = ]& gt-]^ У (ф * 4) n{X{In))dXn =
n=0 [0,1]n
= Е
n=0
[0,1]
Yl 0U|(X (^))Д|/пи|(Х (In ^))dXn = U0ln
© n p
= I 0ш{Х{ш))ф1пш{Х{1пш^Хп.
n = 0 UC/n[0 1]n
После замены переменных интегрирования X (ш), |ш| = m на X (Im) и X (In ш) на X (In Im) в каждом из слагаемых и используя правило перестройки суммирований
НАУЧНЫЕ ВЕДОМОСТИ Е1Д Серия: Математика. Физика. 2015. № 5(202). Выл. 38 99
?¦¦¦ =? ? ¦¦¦•? i
ш? I» m=0 ш€. 1п: ш=т ш€. 1п: ш=т
П
m
получаем
^ Zn ^ /
Z/(zj Ф * Ф) — ^ ^ ^ ^ I '-•Рт (Хт'-) Im^dXn —
n[0,1]n
Ю -V™ П
Т-Т
z-'- n! ^ m
n=0 m=0
n
lflm (Xm)^n-m (X (In Im))dXn
[0,1]n
zm r r
УУ ml / lP'-rn (Xm)dX (Im) j
m=0
[0,1]m
[0,1]n
(n — m)!
Фn-m (X (InIm))dX (In-m)
(?"[ / 4& gt-m{Xm)dX{Im))(f f]^ra (X (/ra))dX (/ra)) =?(г-Ф)?(г-Ф).
m=0
[0,1]m
[0,1]n
n=0
Следствие. Если Ф G A0, го
L (z- exp, Ф) = exp (L (z- Ф)).
(5)
n-m
z
n=m
3. Вычисление производящей функции G (z). Положим Ф = х G A0. Тогда
ОО n
b (z- X) = J] Z~x = ег — 1
n= 1
и, на основании формулы (5),
L (z- exp, x) = exP (ez — 1) ¦ (6)
С другой стороны, как было сказано выше (exp, Ф) = Mn, n G N, и поэтому, согласно (6),
Ю Zn
G (z) = УУ -гМг = L (z'-i ехР* х) = ехР (ez — 1) •
'- n!
n=0
Таким образом, производящая функция G (z) числа разложений определяется формулой
G (z) = exp (ez — 1). (7)
Пример. Произведем расчет первых пяти значений Mn на основе формулы (7).
Mn = G (n)(0).
100 НАУЧНЫЕ ВЕДОМОСТИ
Серия: Математика. Физика. 2015. № 5(202). Вып. 38
Заметим, что G (n) = G (z)Qn (ez), где Qn (x) — полином п-й степени, где Qi (x) = x.
При этом полиномы Qn вычисляются рекуррентно по формуле
Qn+1(x) x (Qn (x) + Qn (x)) ¦
Это положение проверяется непосредственным дифференцированием
G (n+1) = G (z)Qn (ez) + G (z)Qn (ez)ez = G (z)(Qn (ez) + Qn (ez))ez ¦
Так как G (0) = 1 И M, n = G (n)(0) = G (0)Qn (1), Qn+l (1) = Qn (1) + Q'-n (1)^ T0
Q1(x) = x M1 = 1-
Q2(x) = x + x2 M2 = 2-
Q3(x) = x + 3×2 + x3 M3 = 5 —
Q4(x) = x + 7×2 + 6×3 + x4, M4 = 15 —
Q5(x) = x + 15×2 + 25×3 + 10×4 + x5, M5 = 52 —
то есть эти значения совпадают со значениями M1- M2, M3, вычисленными выше напрямую.
Литература
1. Рюэль Д. Статистическая механика. Строгие результаты / М.: Мир, 1971. — 368 с.
2. Холл М. Комбинаторный анализ / М.: Иностр. лит., 1963. — 98 с.
3. Майер Дж., Гепперт-Майер М. Статистическая механика / М.: Мир, 1980. -546 с.
CALCULATION OF PARTITION NUMBER OF FINITE SET Yu.P. Virchenko, L.P. Ostapenko Belgorod State University,
Studencheskaja St., 14, Belgorod, 308 007, Russia, e-mail: soldatov48@gmail. com
Abstract. Combinatorial problem about the partition number Mn of arbitrary finite set of n elements is studied. The generation function of the number Mn, n € N is calculated.
Key words: partition of finite set, generation function, symmetric functions, infinite dimensional algebra.

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