Эта публикация цитируется в
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