УДК 519.17
О свойствах решения рекуррентного уравнения, перечисляющего максимальные независимые множества в полных деревьях
Д. С. Талецкий1
| Аннотация | В настоящей работе рассматривается нелинейное рекуррентное уравнение второго порядка, возникающее при анализе количества независимых множеств в полных \mbox{$q$-арных} деревьях. Ранее было доказано, что при $q=2$ решение данного уравнения имеет предел, а при любом достаточно большом $q$ оно распадается на три сходящиеся подпоследовательности, индексы которых соответствуют классам вычетов по модулю три. Ранее проведенный вычислительный эксперимент позволил предположить, что этот эффект имеет место при любом $q\geq 11$. В настоящей работе доказывается расходимость решения при любом $q\geq 3$. Необходимым условием одновременной сходимости всех трех подпоследовательностей решения, индексы которых соответствуют классам вычетов по модулю три, является существование специального решения некоторой системы нелинейных уравнений. Проведенный в настоящей работе численный поиск решений системы показал, что при $3\leq q\leq 9$ соответствующего решения системы не существует. Численно-аналитическим образом в данной работе показывается нераспадаемость на три подпоследовательности и для $q=10$. |
|---|---|
| Ключевые слова | рекуррентное уравнение, теорема расходимости, вычислительный эксперимент. |
1Талецкий Дмитрий Сергеевич, лаборант кафедры алгебры, геометрии и дискретной математики, ФГАОУ ВО "Нижегородский государственный университет им. Н. И. Лобачевского" (603950, Россия, г. Нижний Новгород, пр. Гагарина, д. 23), ORCID: http://orcid.org/0000-0003-0966-3903, dmitalmail@gmail.com
Цитирование: Талецкий Д. С. О свойствах решения рекуррентного уравнения, перечисляющего максимальные независимые множества в полных деревьях // Журнал Средневолжского математического общества. 2018. Т. 20, № 1. С. 46–54.
DOI 10.15507/2079-6900.20.201801.46-54
