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

Журнал СВМО, 2018, том 20, номер 1, страницы 46–54 (Mi svmo689)

Эта публикация цитируется в 1 статье

Математика

О свойствах решения рекуррентного уравнения, перечисляющего максимальные независимые множества в полных деревьях

Д. С. Талецкий

Национальный исследовательский Нижегородский государственный университет им. Н. И. Лобачевского

Аннотация: В настоящей работе рассматривается нелинейное рекуррентное уравнение второго порядка, возникающее при анализе количества независимых множеств в полных $q$-арных деревьях. Ранее было доказано, что при $q=2$ решение данного уравнения имеет предел, а при любом достаточно большом $q$ оно распадается на три сходящиеся подпоследовательности, индексы которых соответствуют классам вычетов по модулю три. Ранее проведенный вычислительный эксперимент позволил предположить, что этот эффект имеет место при любом $q\geq 11$. В настоящей работе доказывается расходимость решения при любом $q\geq 3$. Необходимым условием одновременной сходимости всех трех подпоследовательностей решения, индексы которых соответствуют классам вычетов по модулю три, является существование специального решения некоторой системы нелинейных уравнений. Проведенный в настоящей работе численный поиск решений системы показал, что при $3\leq q\leq 9$ соответствующего решения системы не существует. Численно-аналитическим образом в данной работе показывается нераспадаемость на три подпоследовательности и для $q=10$.

Ключевые слова: рекуррентное уравнение, теорема расходимости, вычислительный эксперимент.

УДК: 519.17

MSC: 05C30

DOI: 10.15507/2079-6900.20.201801.46-54



Реферативные базы данных:


© МИАН, 2024