RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические труды // Архив

Матем. тр., 2023, том 26, номер 2, страницы 129–137 (Mi mt682)

О рациональности производящей функции для числа корневых лесов циркулянтных графов

У. П. Камаловab, А. Б. Кутбаевbc, А. Д. Медныхab

a Институт математики им. С.Л.Соболева СОРАН, просп. Академика Коптюга, 4, Новосибирск, 630090, РОССИЯ
b Новосибирский гос. университет, ул. Пирогова, 1, Новосибирск, 630090 РОССИЯ
c Нукусский государственный педагогический институт имени Ажинияза, ул. Сейитова, г. Нукус, Узбекистан

Аннотация: Пусть $\Phi(x)=\sum_{n=1}^\infty f_\Gamma(n)x^n$ – производящая функция для числа корневых лесов $f_\Gamma(n)$ в циркулянтном графе $\Gamma=C_n(s_1,s_2,\dots,s_k)$ либо $\Gamma=C_{2n}(s_1,s_2,\dots,s_k,n)$. Мы покажем, что $\Phi(x)$ является рациональной функцией с целочисленными коэффициентами, удовлетворяющей условию $\Phi(x)=-\Phi(1/x)$. Полученный результат мы иллюстрируем с помощью конкретных примеров.

Ключевые слова и фразы: корневой остовный лес, циркулянтный граф, производящая функция.

УДК: 519.1

Статья поступила: 18.05.2023
Переработанный вариант: 31.07.2023
Принята к публикации: 05.10.2023

DOI: 10.33048/mattrudy.2023.26.206


 Англоязычная версия: Siberian Advances in Mathematics, 2023, 33:4, 322–328


© МИАН, 2024