Abstract:
The article considers a second-order nonlinear recurrent equation arising in
analysis of the independent sets' quantity in complete q-ary trees.
We proved earlier that for q=2 its solution has a limit and for any sufficiently large q
the solution splits into three converging subsequences with indices corresponding to the residue classes
modulo 3. Computational experiment allowed to assume that this effect holds for any
q≥11. The present paper proves divergence of the solution for any q≥3.
The necessary condition for simultaneous convergence of all subsequences of the solution,
with indices corresponding to the residue classes modulo 3, is the existence of a special
solution of some nonlinear equations' system. Numerical search for solutions of the system,
conducted in the present paper, showed that there is no corresponding solution of the system
for any 3≤q≤9. We numerically and analytically show that the non-disintegrability
into three subsequences takes place also for q=10.
Citation:
D. S. Taletskii, “On properties of solution of a reccurent equation appearing in enumeration of maximal independent sets in complete trees”, Zhurnal SVMO, 20:1 (2018), 46–54
\Bibitem{Tal18}
\by D.~S.~Taletskii
\paper On properties of solution of a reccurent equation appearing in enumeration of maximal independent sets in complete trees
\jour Zhurnal SVMO
\yr 2018
\vol 20
\issue 1
\pages 46--54
\mathnet{http://mi.mathnet.ru/svmo689}
\crossref{https://doi.org/10.15507/2079-6900.20.201801.46-54}
\elib{https://elibrary.ru/item.asp?id=32780463}
Linking options:
https://www.mathnet.ru/eng/svmo689
https://www.mathnet.ru/eng/svmo/v20/i1/p46
This publication is cited in the following 1 articles:
N. A. Kuz'min, D. S. Malyshev, “Enumeration of Matchings in Complete q-ary Trees”, Math. Notes, 111:3 (2022), 398–406