A new simple proof of cayles’s formula and its relationship with the Kirkwood – Salzburg equations
UDC 519.1 A new very simple proof of the formula for the number of labeled root forest-graphs with a given number of vertices is proposed. As a partial case of this formula, we obtain Cayley's formula.
Gespeichert in:
| Datum: | 2022 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Institute of Mathematics, NAS of Ukraine
2022
|
| Online Zugang: | https://umj.imath.kiev.ua/index.php/umj/article/view/7156 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860512626005508096 |
|---|---|
| author | Rebenko, O. L. Rebenko, Alexei Ребенко, О. Л. |
| author_facet | Rebenko, O. L. Rebenko, Alexei Ребенко, О. Л. |
| author_sort | Rebenko, O. L. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2022-12-17T13:41:47Z |
| description |
UDC 519.1
A new very simple proof of the formula for the number of labeled root forest-graphs with a given number of vertices is proposed. As a partial case of this formula, we obtain Cayley's formula. |
| doi_str_mv | 10.37863/umzh.v74i10.7156 |
| first_indexed | 2026-03-24T03:31:46Z |
| format | Article |
| fulltext |
К О Р О Т К I П О В I Д О М Л Е Н Н Я
DOI: 10.37863/umzh.v74i10.7156
УДК 519.1
О. Л. Ребенко1 (Iн-т математики НАН України, Київ)
НОВЕ НАЙПРОСТIШЕ ДОВЕДЕННЯ ФОРМУЛИ КЕЛI
ТА ЗВ’ЯЗОК IЗ РIВНЯННЯМИ КIРКВУДА – ЗАЛЬЦБУРГА
A new very simple proof of the formula for the number of labeled root forest-graphs with a given number of vertices is
proposed. As a partial case of this formula, we obtain Cayley’s formula.
Наведено нове найпростiше доведення формули для кiлькостi помiчених корiнних графiв-лiсiв iз заданою кiлькiстю
вершин. Частковим випадком цiєї формули є формула Келi.
1. Вступ. Iснує багато способiв довести формулу Келi (див., наприклад, [1, 4]; щодо останнiх
публiкацiй див. [2]). Дуже близьке за стилем доведення м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й механiцi. Хоча формулу для лiсiв було отримано в статтi [5] таким
же способом, тут ми виведемо її лише в контекстi теорiї графiв. Це свiдчить про те, що iдеї
статистичної механiки можуть надати новi iнструменти для iнших роздiлiв математики.
2. Конфiгурацiйний простiр i графи-лiси. Нехай \BbbR d — d-вимiрний евклiдiв простiр. Роз-
глянемо набiр координат \gamma = \{ xi\} i\in \BbbN точок, який є локально скiнченною пiдмножиною в \BbbR d,
а множина всiх таких пiдмножин утворює конфiгурацiйний простiр \Gamma . Ми будемо розгляда-
ти лише скiнченнi графи, тому через \Gamma 0 позначимо множину всiх скiнченних конфiгурацiй.
Простiр скiнченних конфiгурацiй в \BbbR d можна записати як диз’юнктивне об’єднання множин з
фiксованою кiлькiстю точок:
\Gamma 0 :=
\infty \coprod
n=0
\Gamma (n), \Gamma (n) :=
\bigl\{
\gamma \in \Gamma
\bigm| \bigm| | \gamma | = n, n \in \BbbN
\bigr\}
, \Gamma (0) := \varnothing .
На кожнiй конфiгурацiї можна побудувати граф, з’єднавши певнi точки (вершини) конфiгу-
рацiї лiнiями (ребрами). Окрему точку конфiгурацiї будемо також вважати графом, що склада-
ється з однiєї вершини. Якщо є граф f на конфiгурацiї \gamma \in \Gamma (n), то його порядок визначається
потужнiстю конфiгурацiї | f | = | \gamma | = n. Через E(f) позначимо множину ребер графа f.
Розглянемо m-зв’язний граф (m \geq 1), кожна зв’язна складова якого є помiченим корiнним
графом-деревом. Коренi вiдповiдних зв’язних компонент цього графа утворюють конфiгурацiю
\eta = \{ x1, . . . , xm\} \in \Gamma (m). Усi iншi вершини утворюють деяку конфiгурацiю \gamma = \{ y1, . . . , yn\} ,
n = 0, 1, . . . . Будь-яка пiдмножина точок з \gamma , якi належать одному дереву з коренем xk, не
може належати iншому дереву з коренем xl, l \not = k. Випадок n = 0 означає, що m-зв’язний
1 e-mail: rebenkoo@ukr.net.
c\bigcirc О. Л. РЕБЕНКО, 2022
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 10 1441
1442 О. Л. РЕБЕНКО
граф f складається з m точок-вершин. У випадку m = 1 граф f є помiченим графом-деревом з
(n + 1)-ю вершиною i з n ребрами. Такi графи називаються помiченими кореневими лiсовими
графами (rooted labeled graph-forest). Множину всiх таких лiсiв iз заданою конфiгурацiєю
коренiв \eta i вершин \gamma позначимо \frakF \eta ;\gamma . Топологiчно, графи, якi вiдрiзняються довжинами своїх
ребер i можуть бути зведенi один до одного евклiдовими перетвореннями координат їхнiх
вершин, вважаються однаковими.
Важливим елементом цього розгляду будуть аналiтичнi внески графiв, якi ми введемо таким
чином. Кожнiй вершинi припишемо деяку сталу h, а кожному ребру, яке з’єднує точки x i y, —
деяку функцiю \nu (x - y). Якщо такi графи зустрiчаються в конкретнiй задачi, то на цi функцiї
необхiдно накласти вiдповiднi умови.
Аналiтичним внеском довiльного графа з множини f \in \frakF \eta ,\gamma буде вираз
G(f) = h| \eta | +| \gamma |
\prod
(x,y)\in E(f)
\nu (x - y). (2.1)
Основний результат базується на такiй тотожностi.
Пропозицiя 2.1. Для довiльного x \in \eta позначимо \eta \^x := \eta \setminus \{ x\} . Тодi\sum
f\in \frakF \eta ;\gamma
\prod
(x\prime ,y\prime )\in E(f)
\nu (x\prime - y\prime ) =
\sum
\xi \subseteq \gamma
\prod
(y\in \xi )
\nu (x - y)
\sum
f\in \frakF
\eta \^x\cup \xi ;\gamma \setminus \xi
\prod
(x\prime ,y\prime )\in E(f)
\nu (x\prime - y\prime ). (2.2)
Доведення. Лiва частина рiвняння (2.2) є сумою внескiв усiх граф-лiсiв множини \frakF \eta ;\gamma .
Права частина — це та сама сума, в якiй записано її члени в такому порядку. Спочатку запишемо
суму внескiв усiх графiв, у яких вершина x не пов’язана з жодною iншою вершиною. З правого
боку це сума всiх внескiв графiв з \frakF \eta \^x;\gamma , тобто \xi = \varnothing . Наступна група членiв включає графи,
у яких вершина x з’єднана однiєю лiнiєю з вершинами y \in \gamma . Отже, всi \xi є одноточковими
множинами з \gamma . Решта груп сум вiдповiдають графам, у яких вершина x приєднана до точок
пiдмножини \xi з \gamma за допомогою | \xi | ребер.
3. Вiдтворююче ядро. Для заданих \eta , \gamma i факторiв h, \nu введемо ядро Qh,\nu (\eta | \gamma ), яке
однозначно визначається таким рекурентним спiввiдношенням для будь-якого x \in \eta :
Qh,\nu (\eta | \gamma ) = h
\sum
\xi \subseteq \gamma
K\nu (x; \xi )Qh,\nu (\eta
\^x \cup \xi | \gamma \setminus \xi ), | \eta | \geq 1, (3.1)
де
K\nu (x; \xi ) :=
\left\{
\prod
y\in \xi
\nu (x - y),
1, \xi = \varnothing ,
(3.2)
та початковими умовами
Qh,\nu (\varnothing | \varnothing ) = 1, Qh,\nu (\varnothing | \gamma ) = 0, якщо \gamma \not = \varnothing ,
i
Qh,\nu (\eta | \gamma ) = 0, якщо \eta \cap \gamma \not = \varnothing .
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 10
НОВЕ НАЙПРОСТIШЕ ДОВЕДЕННЯ ФОРМУЛИ КЕЛI ТА ЗВ’ЯЗОК IЗ РIВНЯННЯМИ КIРКВУДА . . . 1443
Лема 3.1. Розв’язок рiвняння (3.1) можна записати у виглядi
Qh,\nu (\eta | \gamma ) =
\sum
f\in \frakF \eta ,\gamma
G(f), (3.3)
де G(f) визначено в (2.1).
Доведення. Легко бачити, що (3.3) збiгається з лiвою частиною рiвностi (2.2), а рекурентне
рiвняння (3.1), (3.2) є в точностi правою частиною (2.2).
Тепер ми можемо знайти кiлькiсть цих графiв для заданих \eta , \gamma з | \eta | = m i | \gamma | = n.
Справедливою є така лема (див. також [5]).
Лема 3.2 [5]. Число графiв-лiсiв у сумi (3.3), яка є розв’язком рiвняння (3.1) iз заданими
n = | \gamma | i m = | \eta | , виражається формулою
N(m | n) = m(n+m)n - 1. (3.4)
Доведення. Якщо покласти h = \nu = 1 у виразi (3.3), то Q1,1(\eta | \gamma ) = N(m | n) i задовольняє
рiвняння
N(m | n) =
n\sum
k=0
\biggl(
n
k
\biggr)
N(m+ k - 1 | n - k). (3.5)
За iндукцiєю по n +m припустимо, що формула (3.4) справедлива для N(m + k - 1 | n - k)
при k = 0, 1, . . . , n. Тодi, пiдставивши N(m+ k - 1 | n - k) = (m+ k - 1)(m+ n - 1)n - k - 1 у
праву частину рiвняння (3.5), отримаємо рiвнiсть
n\sum
k=0
\biggl(
n
k
\biggr)
(m+ k - 1)(m+ n - 1)n - k - 1 = M1 + M2,
де
M1 := m
n\sum
k=0
\biggl(
n
k
\biggr)
(m+ n - 1)n - k - 1 =
= m(m+ n - 1) - 1
n\sum
k=0
\biggl(
n
k
\biggr)
(m+ n - 1)n - k = m(m+ n - 1) - 1(m+ n)n
i
M2 :=
n\sum
k=0
\biggl(
n
k
\biggr)
(k - 1)(m+ n - 1)n - k - 1 =
= n
n\sum
k=1
\biggl(
n - 1
k - 1
\biggr)
(m+ n - 1)n - k - 1 - (m+ n - 1) - 1
n\sum
k=0
\biggl(
n
k
\biggr)
(m+ n - 1)n - k =
= n(m+ n - 1) - 1(m+ n)n - 1 - (m+ n - 1) - 1(m+ n)n =
= - m(m+ n - 1) - 1(m+ n)n - 1.
Отже, M1 +M2 = m(m+ n)n - 1, що i завершує доведення леми.
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 10
1444 О. Л. РЕБЕНКО
4. Висновок: формула Келi. Отже, для m = 1 рiвняння (3.4) є формулою Келi. Основним
елементом цього простого доведення є рекурентне рiвняння (3.1) для ядра Qh,\nu (\eta | \gamma ). Це
рiвняння було наведено в роботi [3] як технiчний елемент для зображення розв’язку рiвнянь
Кiрквуда – Зальцбурга (докладнiше див. [5]).
Лiтература
1. M. Aigner, G. M. Ziegler, Proofs from the book, 4th ed., Springer-Verlag, Berlin (2010).
2. S. Guo, V. J. W. Guo, A recursive algorithm for trees and forests, Discrete Math., 340, 695 – 703 (2017).
3. R. A. Minlos, S. K. Poghosyan, Estimates of Ursell functions, group functions, and their derivatives, Theor. Math.
Phys., 31, № 2, 408 – 418 (1977).
4. J. W. Moon, Various proofs of Cayley’s formula for counting trees, A Seminar on Graph Theory (Ed. F. Harary),
Holt, Rinehart, and Winston, New York (1967), p. 70 – 78.
5. O. L. Rebenko, On the connection of some approaches to solving the Kirkwood – Salzburg equations, Ukr. Math. J.,
73, № 3, 93 – 106 (2021).
6. Lajos Takacs, On Cayley’s formula for counting forests, J. Combin. Theory, Ser. A, 53, 321 – 323 (1990).
Одержано 09.02.22
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 10
|
| id | umjimathkievua-article-7156 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-03-24T03:31:46Z |
| publishDate | 2022 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/b3/bf8feff5af62f190d4504f69e30998b3.pdf |
| spelling | umjimathkievua-article-71562022-12-17T13:41:47Z A new simple proof of cayles’s formula and its relationship with the Kirkwood – Salzburg equations Нове найпростіше доведення формули келі та зв’язок із рівняннями Кірквуда – Зальцбурга Rebenko, O. L. Rebenko, Alexei Ребенко, О. Л. граф-дерево, граф-ліс, формула Келі forests, trees, Cayley's formula UDC 519.1 A new very simple proof of the formula for the number of labeled root forest-graphs with a given number of vertices is proposed. As a partial case of this formula, we obtain Cayley's formula. УДК 519.1 Наведено нове найпростіше доведення формули для кількості помічених корінних  графів-лісів із заданою кількістю вершин. Частковим випадком цієї формули є формула Келі.  Institute of Mathematics, NAS of Ukraine 2022-11-27 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/7156 10.37863/umzh.v74i10.7156 Ukrains’kyi Matematychnyi Zhurnal; Vol. 74 No. 10 (2022); 1441 - 1444 Український математичний журнал; Том 74 № 10 (2022); 1441 - 1444 1027-3190 uk https://umj.imath.kiev.ua/index.php/umj/article/view/7156/9319 Copyright (c) 2022 Олексій Лукич Ребенко |
| spellingShingle | Rebenko, O. L. Rebenko, Alexei Ребенко, О. Л. A new simple proof of cayles’s formula and its relationship with the Kirkwood – Salzburg equations |
| title | A new simple proof of cayles’s formula and its relationship with the Kirkwood – Salzburg equations |
| title_alt | Нове найпростіше доведення формули келі та зв’язок із рівняннями Кірквуда – Зальцбурга |
| title_full | A new simple proof of cayles’s formula and its relationship with the Kirkwood – Salzburg equations |
| title_fullStr | A new simple proof of cayles’s formula and its relationship with the Kirkwood – Salzburg equations |
| title_full_unstemmed | A new simple proof of cayles’s formula and its relationship with the Kirkwood – Salzburg equations |
| title_short | A new simple proof of cayles’s formula and its relationship with the Kirkwood – Salzburg equations |
| title_sort | new simple proof of cayles’s formula and its relationship with the kirkwood – salzburg equations |
| topic_facet | граф-дерево граф-ліс формула Келі forests trees Cayley's formula |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/7156 |
| work_keys_str_mv | AT rebenkool anewsimpleproofofcaylessformulaanditsrelationshipwiththekirkwoodsalzburgequations AT rebenkoalexei anewsimpleproofofcaylessformulaanditsrelationshipwiththekirkwoodsalzburgequations AT rebenkool anewsimpleproofofcaylessformulaanditsrelationshipwiththekirkwoodsalzburgequations AT rebenkool novenajprostíšedovedennâformulikelítazvâzokízrívnânnâmikírkvudazalʹcburga AT rebenkoalexei novenajprostíšedovedennâformulikelítazvâzokízrívnânnâmikírkvudazalʹcburga AT rebenkool novenajprostíšedovedennâformulikelítazvâzokízrívnânnâmikírkvudazalʹcburga AT rebenkool newsimpleproofofcaylessformulaanditsrelationshipwiththekirkwoodsalzburgequations AT rebenkoalexei newsimpleproofofcaylessformulaanditsrelationshipwiththekirkwoodsalzburgequations AT rebenkool newsimpleproofofcaylessformulaanditsrelationshipwiththekirkwoodsalzburgequations |