Paradeterminants and partition polynomials
We study Bell polynomials by using functions of triangular matrices (parapermanents and paradeterminants). Some combinatorial identities and relationships between these functions and the Stirling numbers of the first and second kinds are established.
Gespeichert in:
| Datum: | 2008 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch Englisch |
| Veröffentlicht: |
Institute of Mathematics, NAS of Ukraine
2008
|
| Online Zugang: | https://umj.imath.kiev.ua/index.php/umj/article/view/3261 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860509316916707328 |
|---|---|
| author | Zators’kyi, R. A. Заторський, Р. А. |
| author_facet | Zators’kyi, R. A. Заторський, Р. А. |
| author_sort | Zators’kyi, R. A. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2020-03-18T19:49:31Z |
| description | We study Bell polynomials by using functions of triangular matrices (parapermanents and paradeterminants). Some combinatorial identities and relationships between these functions and the Stirling numbers of the first and second kinds are established. |
| first_indexed | 2026-03-24T02:39:10Z |
| format | Article |
| fulltext |
УДК 512.538
Р. А. Заторський (Прикарпат. нац. ун-т, Iвано-Франкiвськ)
ПАРАДЕТЕРМIНАНТИ I МНОГОЧЛЕНИ РОЗБИТТIВ
We study Bell polynomials by using functions of triangular matrices (parapermanents and paradetermi-
nants). Some combinatorial identities and the relationships between these functions and the Stirling
numbers of the first and second kind are established.
Изучаются многочлены Бэлла с помощью функций треугольных матриц (параперманентов и параде-
терминантов). Установлены некоторые комбинаторные тождества и связи этих функций с числами
Стирлинга первого и второго рода.
1. Вступ. Введене Беллом поняття многочленiв розбиттiв [1] має широкi застосу-
вання в дискретнiй математицi, а саме при диференцiюваннi складених функцiй [2],
в теорiї чисел [3], алгебрi тощо. У цiй статтi матричний метод (див. [4, 5]) застосо-
вано до дослiдження многочленiв Белла. При цьому встановлено тотожностi мiж
деякими важливими многочленами розбиттiв та парадетермiнантами трикутних
матриць [6]. Оскiльки властивостi парадетермiнантiв i параперманентiв трикутних
матриць достатньо вивченi, вони стають зручним iнструментом дослiдження мно-
гочленiв розбиттiв. Метод дозволяє отримати деякi вiдомi та невiдомi тотожностi.
Наведемо короткi вiдомостi про парадетермiнанти (детальнiше див. в [6]).
Нехай K — деяке числове поле.
Означення 1.1. Трикутну таблицю чисел, якi належать числовому полю K,
A =
a11
a21 a22
...
...
. . .
an1 an2 · · · ann
n
(1.1)
назвемо трикутною матрицею, а число n — ї ї порядком.
Зауважимо, що трикутна матриця в нашому розумiннi не є трикутною матри-
цею в звичайному розумiннi цього термiна, оскiльки вона є трикутною, але не
прямокутною таблицею чисел.
Кожному елементу aij матрицi (1.1) поставимо у вiдповiднiсть (i− j + 1) еле-
ментiв aik, k = j, . . . , i, якi назвемо похiдними елементами матрицi, породженими
ключовим елементом aij .
Добуток усiх похiдних елементiв, що породженi елементом aij , позначимо через
{aij} i назвемо факторiальним добутком ключового елемента aij , тобто
{aij} =
i∏
k=j
aik.
Означення 1.2. Набiр ключових елементiв матрицi (1.1) назвемо нормаль-
ним набором цiєї матрицi, якщо вони породжують монотрансверсаль, тобто
множину похiдних елементiв потужностi n, кожнi два з яких не належать одно-
му стовпчику цiєї матрицi.
Нехай P(n) — множина всiх упорядкованих розбиттiв (композицiй) натурально-
го числа n на натуральнi доданки (див. [7, с. 67]). Вiдомо, що
c© Р. А. ЗАТОРСЬКИЙ, 2008
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 11 1457
1458 Р. А. ЗАТОРСЬКИЙ
∣∣P(n)
∣∣ =
n∑
r=1
(
n− 1
r − 1
)
= 2n−1. (1.2)
Легко бачити, що мiж нормальними наборами ключових елементiв матрицi (1.1)
i впорядкованими розбиттями натурального числа n iснує взаємно однозначна вiд-
повiднiсть.
Кожному нормальному наборовi a ключових елементiв поставимо у вiдповiд-
нiсть знак числа (−1)ε(a), де ε(a) — сума всiх iндексiв ключових елементiв цього
набору.
Означення 1.3. Парадетермiнантом трикутної матрицi (1.1) назвемо число
ddet(A) = �
�
�
B
B
B
a11
a21 a22
...
...
. . .
an1 an2 · · · ann
B
B
B
�
�
�
=
∑
(α1,α2,...,αr)∈P(n)
(−1)ε(a)
r∏
s=1
{
ai(s),j(s)
}
,
де ai(s),j(s) — ключовий елемент, що вiдповiдає s-й компонентi розбиття α =
= (α1, α2, . . . , αr), а символ ε(a) — знак нормального набору a ключових елементiв.
За аналогiєю iз поняттям парадетермiнанта матрицi (1.1) введемо поняття па-
раперманента цiєї матрицi.
Означення 1.4. Параперманентом трикутної матрицi (1.1) назвемо число
pper(A) =
a11
a21 a22
...
...
. . .
an1 an2 · · · ann
=
∑
(α1,α2,...,αr)∈P(n)
r∏
s=1
{ai(s),j(s)},
де ai(s),j(s) — ключовий елемент, що вiдповiдає s-й компонентi розбиття α =
= (α1, α2, . . . , αr).
Зауваження 1.1. Внаслiдок (1.2) парадетермiнант i параперманент n-го по-
рядку складаються iз 2n−1 доданкiв.
Теоpема 1.1 (А. Г. Ганюшкiн). Якщо A — трикутна матриця (1.1), то вико-
нуються рiвностi
ddet(A) =
n∑
r=1
∑
α1+...+αr=n
(−1)n−r
r∏
s=1
{
aα1+...+αs,α1+...+αs−1+1
}
, (1.3)
pper(A) =
n∑
r=1
∑
α1+...+αr=n
r∏
s=1
{
aα1+...+αs,α1+...+αs−1+1
}
, (1.4)
де пiдсумовування проводиться за множиною натуральних розв’язкiв рiвняння
α1 + . . . + αr = n.
Означимо скалярний добуток вектора (b1, b2, . . . , bn) на парадетермiнант матри-
цi (1.1), використавши рiвнiсть (1.3), з допомогою рiвностей
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 11
ПАРАДЕТЕРМIНАНТИ I МНОГОЧЛЕНИ РОЗБИТТIВ 1459
(b1, b2, . . . , bn) · ddet(A) df=
df=
n∑
r=1
br ·
∑
α1+...+αr=n
(−1)n−r
r∏
s=1
{
aα1+...+αs,α1+...+αs−1+1
}
. (1.5)
Аналогiчно означимо скалярний добуток вектора (b1, b2, . . . , bn) на параперманент
цiєї матрицi, використавши рiвнiсть (1.4):
(b1, b2, . . . , bn) · pper(A) df=
n∑
r=1
br ·
∑
α1+...+αr=n
r∏
s=1
{
aα1+...+αs,α1+...+αs−1+1
}
.
(1.6)
Кожному елементу aij трикутної матрицi (1.1) поставимо у вiдповiднiсть три-
кутну таблицю елементiв цiєї матрицi з цим елементом в лiвому нижньому кутi,
яку назвемо рогом цiєї матрицi i позначимо через Rij . Очевидно, що рiг Rij є три-
кутною матрицею (i− j +1)-го порядку, причому йому належать лише тi елементи
ars матрицi (1.1), iндекси яких задовольняють спiввiдношення j ≤ s ≤ r ≤ i.
Далi будемо вважати, що
ddet(R01) = pper(R01) = ddet(Rn,n+1) = pper(Rn,n+1) = 1.
Означення 1.5. Прямокутну таблицю елементiв трикутної матрицi (1.1)
назвемо вписаною в цю матрицю, якщо одна її вершина збiгається з елементом
an1, а протилежна до неї — з елементом aii, i = 1, 2, . . . , n. Позначимо цю
таблицю через T (i).
Зауваження 1.2. Якщо в означеннi 1.5 значення iндексу i дорiвнює 1 або n,
то прямокутна таблиця вироджується вiдповiдно у перший стовпчик або останнiй
рядок.
При обчисленнi парадетермiнанта i параперманента зручно користуватися ал-
гебраїчними доповненнями до факторiального добутку ключових елементiв три-
кутної матрицi.
Означення 1.6. Алгебраїчними доповненнями Dij , Pij до факторiального до-
бутку {aij} ключового елемента aij трикутної матрицi (1.1), назвемо вiдповiдно
числа
Dij = (−1)i+jddet(Rj−1,1)ddet(Rn,i+1),
Pij = pper(Rj−1,1)pper(Rn,i+1),
де Rj−1,1 i Rn,i+1 — роги цiєї матрицi.
Корисною є наступна теорема.
Теорема 1.2 (Розклад парадетермiнанта i параперманента за елементами впи-
саної прямокутної таблицi). Нехай A — трикутна матриця (1.1) i T (i) — деяка
вписана прямокутна таблиця елементiв цiєї матрицi. Тодi справджуються рiвно-
стi
ddet(A) =
i∑
s=1
n∑
r=i
{ars}Drs, (1.7)
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 11
1460 Р. А. ЗАТОРСЬКИЙ
pper(A) =
i∑
s=1
n∑
r=i
{ars}Prs, (1.8)
де Drs i Prs — вiдповiдно алгебраїчнi доповнення до факторiального добутку
ключового елемента ars, який належить вписанiй прямокутнiй таблицi T (i).
Наслiдок 1.1. При i = 1 за формулами (1.7), (1.8) i зауваженням 1.2 отри-
маємо розклад парадетермiнанта та параперманента за елементами їх першого
стовпчика
ddet(A) =
n∑
r=1
(−1)r+1{ar1}ddet(Rn,r+1),
pper(A) =
n∑
r=1
{ar1}pper(Rn,r+1).
Якщо i = n, то отримаємо вiдповiднi розклади за елементами останнього рядка
ddet(A) =
n∑
s=1
(−1)n+s{ans}ddet(Rs−1,1),
pper(A) =
n∑
s=1
{ans}pper(Rs−1,1).
Наступна теорема дає зручний алгоритм обчислення парадетермiнантiв i пара-
перманентiв.
Теоpема 1.2 (I. I. Лiщинський). Справджуються рiвностi
�
�
�
B
B
B
a11
a21 a22
...
...
. . .
an1 an2 · · · ann
B
B
B
�
�
� n
= (−1) · �
�
�
B
B
B
(a21 − a11)a22
(a31 − a11)a32 a33
...
...
. . .
(an1 − a11)an2 an3 · · · ann
B
B
B
�
�
� n−1
,
a11
a21 a22
...
...
. . .
an1 an2 · · · ann
n
=
(a21 − a11)a22
(a31 − a11)a32 a33
...
...
. . .
(an1 − a11)an2 an3 . . . ann
n−1
.
Зауваження 1.3. Для знаходження значення парадетермiнанта (параперма-
нента) достатньо виконати
n(n− 1)
2
операцiй множення i стiльки ж операцiй дода-
вання. Оскiльки парадетермiнант мiстить
n(n + 1)
2
елементiв i всi вони впливають
на значення парадетермiнанта, запропонований алгоритм iстотно покращити не
можна.
2. Означення многочленiв розбиття та деякi твердження. Розглянемо три-
кутну матрицю вигляду
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 11
ПАРАДЕТЕРМIНАНТИ I МНОГОЧЛЕНИ РОЗБИТТIВ 1461
A =
k11x1
k21
x2
x1
k22x1
... · · ·
. . .
kn1
xn
xn−1
kn2
xn−1
xn−2
· · · knnx1
n
=
(
kij
xi−j+1
xi−j
)
1≤j≤i≤n
, (2.1)
де x0 = 1, а kij — деяка дробово-рацiональна функцiя аргументiв i, j.
Парадетермiнанти i параперманенти трикутних матриць (2.1) зустрiчаються до-
сить часто (див. [6 – 9]), тому вивчимо їх детальнiше.
Нехай задано деяку мультимножину M iз первинною специфiкацiєю Сачкова
[10] вигляду [
1λ1 , 2λ2 , . . . , nλn
]
.
Якщо показники первинної специфiкацiї мультимножини M задовольняють рiв-
няння λ1+2λ2+. . .+nλn = n, то таку мультимножину називають невпорядкованим
розбиттям натурального числа n i позначають через π(n).
Суму всiх показникiв первинної специфiкацiї розбиття π(n) позначимо через
λ(π), тобто
λ(π) = λ1 + λ2 + . . . + λn.
Зауважимо, що λ(π) має певний комбiнаторний сенс, а саме є числом компонент
розбиття π(n).
Нехай Π(n) є множиною всiх мультимножин π(n), а Πk(n) — множиною всiх
мультимножин π(n), показники первинних специфiкацiй яких задовольняють рiв-
нiсть λ(π) = k. Сiм’я множин Πk(n), k = 1, 2, . . . , n, утворює розбиття множи-
ни Π(n).
Означення 2.1. Многочленами розбиттiв назвемо многочлени вигляду
P (x1, . . . , xn) =
n∑
k=1
y (k)
∑
π(n)∈Πk(n)
c(n;λ1, . . . λn)xλ1
1 . . . xλn
n , (2.2)
де y (k) , k = 1, . . . , n, — компоненти деякого вектора, а c(n;λ1, . . . , λn) — деякi
рацiональнi числа.
Зауваження 2.1. Якщо в рiвностi (2.2) y (k) ≡ 1, k = 1, 2, . . . , n, то вона
набирає вигляду
P (x1, . . . , xn) =
n∑
k=1
∑
π(n)∈Πk(n)
c(n;λ1, . . . , λn)xλ1
1 . . . xλn
n =
=
∑
π(n)∈Π(n)
c(n;λ1, . . . λn)xλ1
1 . . . xλn
n . (2.3)
Многочлени вигляду (2.1) назвемо примiтивними многочленами розбиттiв.
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 11
1462 Р. А. ЗАТОРСЬКИЙ
Теоpема 2.1. Парадетермiнанти i параперманенти матриць вигляду (2.1) є
примiтивними многочленами розбиттiв, тобто виконуються рiвностi
pper(A) =
∑
π(n)∈Π(n)
c(n;λ1, . . . , λn)xλ1
1 . . . xλn
n , (2.4)
ddet(A) =
∑
π(n)∈Π(n)
(−1)n−λ(π)c(n;λ1, . . . , λn)xλ1
1 . . . xλn
n . (2.5)
Доведення. Встановимо рiвнiсть (2.4). Ключовому елементу kij
xi−j+1
xi−j
па-
раперманента матрицi (2.1) вiдповiдає факторiальний добуток
{
kij
xi−j+1
xi−j
}
=
=
∏i
s=j
(
kis
xi−s+1
xi−s
)
=
(∏i
s=j
kis
)
xi−j+1. Тому компонентi αi, i = 1, . . . , n,
впорядкованого розбиття α1 +α2 + . . .+αn = n вiдповiдає факторiальний добуток(∏i
s=j
kis
)
xαi . Отже, згiдно з означенням параперманента кожному впорядкова-
ному розбиттю α1+α2+. . .+αn = n, компоненти якого утворюють мультимножину
π(n) ∈ Π(n) iз первинною специфiкацiєю
[
1λ1 , 2λ2 , . . . , nλn
]
, вiдповiдає доданок
вигляду
c∗xλ1
1 xλ2
2 . . . xλi
i ,
а всiм розбиттям iз первинною специфiкацiєю
[
1λ1 , 2λ2 , . . . , nλn
]
— доданок
c(n;λ1, . . . , λn)xλ1
1 xλ2
2 . . . xλi
i .
Рiвнiсть (2.5) доводиться аналогiчно. Зауважимо лише, що знак кожного з до-
данкiв, якi вiдповiдають розбиттям iз первинною специфiкацiєю
[
1λ1 , 2λ2 , . . . , nλn
]
,
визначається множником (−1)n−λ(π) (див. рiвнiсть (1.3)).
Згiдно iз рiвностями (1.5) i (1.6) многочлени розбиттiв
n∑
k=1
yk ·
∑
π(n)∈Πk(n)
c(n;λ1, . . . , λn)xλ1
1 . . . xλn
n
,
n∑
k=1
yk ·
∑
π(n)∈Πk(n)
(−1)n−kc(n;λ1, . . . , λn)xλ1
1 . . . xλn
n
(2.6)
можна записати вiдповiдно у виглядi
y1
y2
. . .
yn
·
τ11x1
τ21
x2
x1
τ22x1
· · · · · · · · · · · · · · · · · · · · ·
τn1
xn
xn−1
τn2
xn−1
xn−2
· · · τnnx1
n
= (y1, y2, . . . , yn)·
[
τsr
xs−r+1
xs−r
]
1≤r≤s≤n
,
(2.7)
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 11
ПАРАДЕТЕРМIНАНТИ I МНОГОЧЛЕНИ РОЗБИТТIВ 1463
y1
y2
. . .
yn
· �
�
�
��
B
B
B
BB
τ11x1
τ21
x2
x1
τ22x1
· · · · · · · · · · · · · · · · · · · · · · · · · · ·
τn1
xn
xn−1
τn2
xn−1
xn−2
. . . τnnx1
B
B
B
BB
�
�
�
�� n
=
= (y1, y2, . . . , yn) ·
〈
τsr
xs−r+1
xs−r
〉
1≤r≤s≤n
, (2.8)
де (y1, y2, . . . , yn) — деякий вектор.
3. Приклади многочленiв розбиттiв.
Твердження 3.1. Права частина формули Фаа дi Бруно
dn
dxn
f(g(x)) =
n∑
m=1
dm
dgm
f(g(x))×
×
∑
π(n)∈Πm(n)
n!
λ1! . . . λn!(1!)λ1 . . . (n!)λn
(g′(x))λ1 . . . (g(n)(x))λn
є многочленом розбиттiв i згiдно iз позначенням (2.7) може бути подана у виглядi
dn
dxn
f(g(x)) =
=
f ′(g)
f ′′(g)
f ′′′(g)
...
f (n)(g)
g′(x)
1
1
g′′(x)
g′(x)
g′(x)
1
2
g′′′(x)
g′′(x)
2
1
g′′(x)
g′(x)
g′(x)
... · · · · · ·
. . .
1
n− 1
g(n)(x)
g(n−1)(x)
2
n− 2
g(n−1)(x)
g(n−2)(x)
· · · n− 1
1
g′′(x)
g′(x)
g′(x)
n
.
(3.1)
Доведення. Розкладемо параперманент
Bn(x1, . . . , xn) =
x1
1
1
x2
x1
x1
1
2
x3
x2
2
1
x2
x1
x1
... · · · · · ·
. . .
1
n− 1
xn
xn−1
2
n− 2
xn−1
xn−2
· · · n− 1
1
x2
x1
x1
n
=
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 11
1464 Р. А. ЗАТОРСЬКИЙ
=
[
j
i− j + jδij
xi−j+1
xi−j
]
1≤j≤i≤n
(3.2)
за елементами останнього рядка:
Bn(x1, . . . , xn) =
=
(
n− 1
0
)
x1Bn−1(x1, . . . , xn−1) +
(
n− 1
1
)
x2Bn−2(x1, . . . , xn) + . . .
. . . +
(
n− 1
n− 2
)
xn−1B1(x1) +
(
n− 1
n− 1
)
xnB0, (3.3)
де B0 = 1. Оскiльки B1(x1) =
[
x1
]
1
= x1 i параперманент (3.2) та многочлен
Белла задовольняють рекурентну рiвнiсть (3.3) (див. [11, с. 174]), справджуються
тотожнiсть[
j
i− j + jδij
xi−j+1
xi−j
]
1≤j≤i≤n
=
∑
π(n)∈Π(n)
n!
λ1!(1!)λ1 . . . λn!(n!)λn
xλ1
1 . . . xλn
n (3.4)
i, отже, рiвнiсть (3.1).
Розглянемо деякi приклади параперманентiв примiтивних многочленiв.
Важливим прикладом трикутних матриць є матриця (2.1), в якiй kij = 1, 1 ≤
≤ j ≤ i ≤ n, тобто матриця вигляду
Z (x1, x2, . . . , xn) =
x1
x2
x1
x1
... · · ·
. . .
xn
xn−1
xn−1
xn−2
· · · x1
n
=
(
xi−j+1
xi−j
)
1≤j≤i≤n
. (3.5)
Твердження 3.2. Справджуються тотожностi
pper (Z(x1, . . . , xn)) =
∑
π(n)∈Π(n)
(λ1 + . . . + λn)!
λ1! . . . λn!
xλ1
1 . . . xλn
n , (3.6)
ddet (Z(x1, . . . , xn)) =
∑
π(n)∈Π(n)
(−1)n−(λ1+...+λn) (λ1 + . . . + λn)!
λ1! . . . λn!
xλ1
1 . . . xλn
n .
(3.7)
Доведення. Наведемо комбiнаторне доведення тотожностi (3.6). Насамперед
з огляду на означення параперманента зазначимо, що кожному впорядкованому
розбиттю α1 + α2 + . . . + αn = n, компоненти якого утворюють мультимножину
π(n) iз первинною специфiкацiєю
[
1λ1 , 2λ2 , . . . , nλn
]
, вiдповiдає доданок вигляду
xλ1
1 xλ2
2 . . . xλn
n .
Пiдрахуємо число таких доданкiв, якi виникають в результатi обчислення пара-
перманента матрицi (3.5). Вiдомо, що мiж множинами нормальних наборiв клю-
чових елементiв трикутної матрицi i всiма впорядкуваннями мультимножини π(n)
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 11
ПАРАДЕТЕРМIНАНТИ I МНОГОЧЛЕНИ РОЗБИТТIВ 1465
iз первинною специфiкацiєю
xλ1
1 xλ2
2 . . . xλn
n
iснує бiєкцiя. Але за полiномiальною формулою число таких впорядкувань дорiв-
нює
(λ1 + λ2 + . . . + λn)!
λ1!λ2! . . . λn!
.
Таким чином, тотожнiсть (3.6) встановлено.
Справедливiсть тотожностi (3.7) випливає iз рiвностi (2.5).
Зазначимо, що якщо для деякого многочлена розбиттiв знайдено вiдповiдний
йому параперманент або парадетермiнант, то з допомогою замiни змiнних можна
отримати низку нових тотожностей.
Пpиклад 3.1. Виконавши в тотожностях (3.6), (3.7) замiну змiнних xi =
yi
i
,
xi =
yi
i!
, i = 1, . . . , n, отримаємо вiдповiдно тотожностi
pper
(
Z
(y1
1
,
y2
2
, . . . ,
yn
n
))
=
[
i− j + δij
i− j + 1
yi−j+1
yi−j
]
1≤j≤i≤n
=
=
∑
Π(n)
(λ1 + . . . + λn)!
1λ1λ1! . . . nλnλn!
yλ1
1 . . . yλn
n ,
pper
(
Z
(y1
1!
,
y2
2!
, . . . ,
yn
n!
))
=
[
1
i− j + 1
yi−j+1
yi−j
]
1≤j≤i≤n
=
=
∑
Π(n)
(λ1 + . . . + λn)!
(1!)λ1λ1! . . . (n!)λnλn!
yλ1
1 . . . yλn
n ,
ddet
(
Z
(y1
1
,
y2
2
, . . . ,
yn
n
))
=
〈
i− j + δij
i− j + 1
yi−j+1
yi−j
〉
1≤j≤i≤n
=
=
∑
Π(n)
(−1)n−(λ1+...+λn) (λ1 + . . . + λn)!
1λ1λ1! . . . nλnλn!
yλ1
1 . . . yλn
n ,
ddet
(
Z
(y1
1!
,
y2
2!
, . . . ,
yn
n!
))
=
〈
1
i− j + 1
yi−j+1
yi−j
〉
1≤j≤i≤n
=
=
∑
Π(n)
(−1)n−(λ1+...+λn) (λ1 + . . . + λn)!
(1!)λ1λ1! . . . (n!)λnλn!
yλ1
1 . . . yλn
n .
Розглянемо ще один приклад примiтивного многочлена розбиттiв.
Твердження 3.3. Нехай
S(x1, . . . , xn) =
(
j
i− j + 1
xi−j+1
xi−j
)
1≤j≤i≤n
,
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 11
1466 Р. А. ЗАТОРСЬКИЙ
тодi справджуються тотожностi
pper(S(x1, . . . , xn)) =
∑
π(n)∈Π(n)
n! (λ(π))!
λ1! . . . λn!(1!)λ1 . . . (n!)λn
xλ1
1 . . . xλn
n , (3.8)
ddet(S(x1, . . . , xn)) =
∑
π(n)∈Π(n)
(−1)n−λ(π) n! (λ(π))!
λ1! . . . λn!(1!)λ1 . . . (n!)λn
xλ1
1 . . . xλn
n .
(3.9)
Для доведення твердження 3.3 достатньо встановити тотожнiсть (3.8), тодi
справедливiсть тотожностi (3.9) випливатиме з рiвностi (2.5). Те, що доданки
параперманента матрицi S(x1, . . . , xn) мають вигляд xλ1
1 . . . xλn
n , вже доведено у
попередньому твердженнi. Знайдемо коефiцiєнт доданка xλ1
1 . . . xλn
n . Розглянемо
деяке впорядковане розбиття
{
α1, α2, . . . , αn
}
натурального числа n, первинна
специфiкацiя якого має вигляд
[
1λ1 , 2λ2 , . . . , nλn
]
. Очевидно, що цьому розбиттю
вiдповiдає доданок
n!
1!λ1 . . . n!λn
xλ1
1 . . . xλn
n
параперманента pper(C(x1, . . . , xn)). Оскiльки таких доданкiв у параперманентi
pper(S(x1, . . . , xn)) налiчується рiвно
(λ1 + λ2 + . . . + λn)
λ1!λ2! . . . λn!
,
тотожнiсть (3.8) встановлено.
4. Многочлени розбиттiв та деякi комбiнаторнi числа. Встановимо зв’язки
мiж деякими спецiальними комбiнаторними числами i параперманентами деяких
трикутних матриць. При x1 = . . . = xn = 1 тотожнiсть (3.4) набирає вигляду[
j
i− j + jδij
]
1≤j≤i≤n
=
∑
π(n)∈Π(n)
n!
λ1! . . . λn!(1!)λ1 . . . (n!)λn
=
=
n∑
k=1
∑
π(n)∈Πk(n)
n!
λ1! . . . λn!(1!)λ1 . . . (n!)λn
,
а оскiльки виконується рiвнiсть [11, с. 191]
S(n, k) =
∑
π(n)∈Πk(n)
n!
λ1! . . . λn!(1!)λ1 . . . (n!)λn
,
де S(n, k) — числа Стiрлiнга другого роду, справджується також рiвнiсть[
j
i− j + jδij
]
1≤j≤i≤n
=
n∑
k=1
S(n, k).
Зауваження 4.1. Число з правої частини рiвностi (3.4) називають числом
Белла, а число пiд знаком суми у правiй частинi рiвностi (3.4), як вiдомо [11],
дорiвнює числу всiх можливих розбиттiв множини потужностi n = λ1 + 2λ2 + . . .
. . . + nλn на λ1 пiдмножин потужностi 1, λ2 пiдмножин потужностi 2, . . . , λn
пiдмножин потужностi n.
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 11
ПАРАДЕТЕРМIНАНТИ I МНОГОЧЛЕНИ РОЗБИТТIВ 1467
Аналогiчно можна отримати рiвностi
〈
j
i− j + jδij
〉
1≤j≤i≤n
=
∑
π(n)∈Π(n)
(−1)n−λ(π) n!
λ1! . . . λn!(1!)λ1 . . . (n!)λn
=
=
n∑
k=1
∑
π(n)∈Πk(n)
(−1)n−k n!
λ1! . . . λn!(1!)λ1 . . . (n!)λn
=
n∑
k=1
(−1)n−kS(n, k).
Позначимо параперманент вигляду
[
(j − (j − 1)δij)
xi−j+1
xi−j
]
1≤j≤i≤n
=
x1
x2
x1
x1
x3
x2
2
x2
x1
x1
x4
x3
2
x3
x2
3
x2
x1
x1
· · · · · · · · · · · · · · · · · · · · · · · · · · ·
xn
xn−1
2
xn−1
xn−2
· · · (n− 1)
x2
x1
x1
n
через Cn(x1, . . . , xn) i розкладемо його за елементами останнього рядка:
Cn(x1, . . . , xn) =
= (n− 1)0x1Cn−1(x1, . . . , xn−1) + (n− 1)1x2Cn−2(x1, . . . , xn−2) + . . .
. . . + (n− 1)n−2xn−1C1(x1) + (n− 1)n−1xnC0. (4.1)
Можна довести, що цикловий iндикатор
Cn(x1, . . . , xn) =
∑
Π(n)
n!
λ1! . . . λn! 1λ1 . . . nλn
xλ1
1 . . . xλn
n
симетричної групи також задовольняє рекурентну рiвнiсть (4.1). Отже, справджу-
ється тотожнiсть[
(j − (j − 1)δij)
xi−j+1
xi−j
]
1≤j≤i≤n
=
∑
Π(n)
n!
λ1! . . . λn! 1λ1 . . . nλn
xλ1
1 . . . xλn
n . (4.2)
Якщо покласти x1 = . . . = xn = x, то тотожнiсть (4.2) набере вигляду
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 11
1468 Р. А. ЗАТОРСЬКИЙ
x
1 x
1 2 x
1 2 3 x
· · · · · · · · · · · ·
1 2 · · · (n− 1) x
1≤j≤i≤n
=
∑
Π(n)
n!
λ1! . . . λn! 1λ1 . . . nλn
xλ1+...+λn , (4.3)
але (див. [5]) параперманент в лiвiй частинi рiвностi (4.3) дорiвнює
x(x + 1)(x + 2) . . . (x + n− 1),
тому отримуємо вiдому тотожнiсть [11, с. 181]
Cn(x, . . . , x︸ ︷︷ ︸
n
) = x(x + 1)(x + 2) . . . (x + n− 1),
яка при x = 1 набирає вигляду
1
1 1
1 2 1
1 2 3 1
· · · · · · · · · · · ·
1 2 · · · (n− 1) 1
n
= Cn(1, . . . , 1︸ ︷︷ ︸
n
) = n!. (4.4)
Таким чином, спiвставляючи рiвностi (4.3) i (4.4), одержуємо рiвнiсть [9, с. 49]∑
Π(n)
1
λ1! . . . λn! 1λ1 . . . nλn
= 1.
Зауваження 4.2. Число пiд знаком суми в рiвностi (4.2) є числом пiдстановок
n символiв, якi складаються iз λ1 циклiв довжини 1, λ2 циклiв довжини 2, . . . , λn
циклiв довжини n.
Парадетермiнант матрицi(
(j − (j − 1)δij)
xi−j+1
xi−j
)
1≤j≤i≤n
обчислюється, як i парадетермiнант матрицi(
j
i− j + jδij
)
1≤j≤i≤n
.
При цьому справджується тотожнiсть
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 11
ПАРАДЕТЕРМIНАНТИ I МНОГОЧЛЕНИ РОЗБИТТIВ 1469〈
(j − (j − 1)δij)
xi−j+1
xi−j
〉
1≤j≤i≤n
=
=
∑
Π(n)
(−1)n−(λ1+...+λn) n!
λ1! . . . λn! 1λ1 . . . nλn
xλ1
1 . . . xλn
n . (4.5)
Враховуючи, що виконується рiвнiсть [11, с. 191]
s(n, k) =
∑
Πk(n)
(−1)n−k n!
λ1! . . . λn! 1λ1 . . . nλn
,
де s(n, k) — числа Стiрлiнга першого роду, тотожнiсть (4.5) при x1 = . . . = xn = 1
можна записати у виглядi
〈(j − (j − 1)δij)〉1≤j≤i≤n =
n∑
k=1
s(n, k) =
1, n = 1,
0, n > 1.
Очевидно, що вiрною є також рiвнiсть
[(j − (j − 1)δij)]1≤j≤i≤n =
n∑
k=1
(−1)n−ks(n, k) = n!.
1. Bell E. T. Partition polynomials // Ann. Math. – 1927. – 29. – P. 38 – 46.
2. Riordan J. An Introduction to combinatorial analysis. – New York: Wiley, 1958. – 236 p.
3. Fine N. J. Sums over partitions // Rept Inst. Theory Numbers, Boulder. – 1959. – P. 86 – 94.
4. Протасов I. В., Хромуляк О. М. Методи лiнiйної алгебри в комбiнаторицi. – Київ: Укр. держ.
пед. ун-т, 1997. – 40 с.
5. Тараканов В. Е. Комбинаторные задачи и (0, 1)-матрицы. – М.: Наука, 1985. – 192 с.
6. Заторський Р. А. Паравизначники та параперманенти трикутних матриць // Мат. студ. – 2002.
– 17, вип. 1. – С. 45 – 54.
7. Стенли Р. Перечислительная комбинаторика: Пер. с англ. – М.: Мир, 1990. – 440 с.
8. Эндрюс Г. Теория разбиений: Пер. с англ. – М.: Наука, 1982. – 256 с.
9. Заторський Р. А. Параперманенти та лiнiйнi рекурентнi спiввiдношення // Мат. мiжн. мат.
конф., присв. 100-рiччю вiд початку роботи Д. О. Граве (1863 – 1939) в Київ. ун-тi (Київ,
17 – 22 червня 2002 р.). – 138 с.
10. Сачков В. Н. Введение в комбинаторые методы дискретной математики. – М.: Наука, 1982. –
382 с.
11. Риордан Дж. Комбинаторные тождества: Пер. с англ. – М.: Наука, 1982. – 255 с.
Одержано 17.04.07
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 11
|
| id | umjimathkievua-article-3261 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | Ukrainian English |
| last_indexed | 2026-03-24T02:39:10Z |
| publishDate | 2008 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/83/aa82791ab61f20c0c75c0c607f8bd783.pdf |
| spelling | umjimathkievua-article-32612020-03-18T19:49:31Z Paradeterminants and partition polynomials Парадетермінанти i многочлени розбиттів Zators’kyi, R. A. Заторський, Р. А. We study Bell polynomials by using functions of triangular matrices (parapermanents and paradeterminants). Some combinatorial identities and relationships between these functions and the Stirling numbers of the first and second kinds are established. Изучаются многочлены Бэлла с помощью функций треугольных матриц (параперманентов и парадетерминантов). Установлены некоторые комбинаторные тождества и связи этих функций с числами Стирлинга первого и второго рода. Institute of Mathematics, NAS of Ukraine 2008-11-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/3261 Ukrains’kyi Matematychnyi Zhurnal; Vol. 60 No. 11 (2008); 1457–1469 Український математичний журнал; Том 60 № 11 (2008); 1457–1469 1027-3190 uk en https://umj.imath.kiev.ua/index.php/umj/article/view/3261/3268 https://umj.imath.kiev.ua/index.php/umj/article/view/3261/3269 Copyright (c) 2008 Zators’kyi R. A. |
| spellingShingle | Zators’kyi, R. A. Заторський, Р. А. Paradeterminants and partition polynomials |
| title | Paradeterminants and partition polynomials |
| title_alt | Парадетермінанти i многочлени розбиттів |
| title_full | Paradeterminants and partition polynomials |
| title_fullStr | Paradeterminants and partition polynomials |
| title_full_unstemmed | Paradeterminants and partition polynomials |
| title_short | Paradeterminants and partition polynomials |
| title_sort | paradeterminants and partition polynomials |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/3261 |
| work_keys_str_mv | AT zatorskyira paradeterminantsandpartitionpolynomials AT zatorsʹkijra paradeterminantsandpartitionpolynomials AT zatorskyira paradetermínantiimnogočlenirozbittív AT zatorsʹkijra paradetermínantiimnogočlenirozbittív |