A combinatorial approach for constructing non-monotonic solutions to the generalized Golomb recursion. (English) Zbl 1418.05023
In the present paper, the authors provide how to modify the tree-based methodology in order to construct nonmonotonic solutions to the generalized Golomb recursion, which gives a combinatorial interpretation for such non-monotonic solutions. This method indicates the first example, where a combinatorial interpretation is available for a non-monotonic solution to a nested recursion. Also using this combinatorial interpretation, the asymptotic properties of these solutions are derived.
Reviewer: Uğur Duran (Hatay)
MSC:
| 05A19 | Combinatorial identities, bijective combinatorics |
| 11B37 | Recurrences |
| 05A15 | Exact enumeration problems, generating functions |
| 05C05 | Trees |
Keywords:
non-homogeneous nested recursion; generalized Golomb recursion; non-monotonic; meta-Fibonacci sequence; tree-based methodology; combinatorial counting argumentReferences:
| [1] | Callaghan, J.; Chew Iii, J. J.; Tanny, S. M., On the behavior of a family of meta-Fibonacci sequences, SIAM J. Discrete Math., 18, 4, 794-824 (2005) · Zbl 1121.11015 · doi:10.1137/S0895480103421397 |
| [2] | Dalton, B.; Rahman, M.; Tanny, S., Spot-based generations for meta-Fibonacci sequences, Experiment. Math., 20, 2, 129-137 (2011) · Zbl 1269.11013 · doi:10.1080/10586458.2011.544565 |
| [3] | Deugau, C. and Ruskey, F., Complete k-ary trees and generalized meta-Fibonacci sequences, in Fourth Colloquium on Mathematics and Computer Science: Algorithms, trees, Combinatorics and Probabilities. DMTCS Proceedings Series, Nancy, France, 2006, 203-214. · Zbl 1190.11008 |
| [4] | Deugau, C.; Ruskey, F., The combinatorics of certain k-ary meta-Fibonacci sequences, J. Integer Seq., 12, 4, 3 (2009) · Zbl 1165.05310 |
| [5] | Golomb, S.W., Discrete chaos: sequences satisfying “strange” recursions, preprint no date |
| [6] | Higham, J.; Tanny, S., More well-behaved meta-Fibonacci sequences, Congr. Numer., 98, 2-17 (1993) · Zbl 0808.11019 |
| [7] | Higham, J.; Tanny, S., A tamely chaotic meta-Fibonacci sequence, Congr. Numer., 99, 67-94 (1994) · Zbl 0821.11006 |
| [8] | Isgur, A., Solving nested recursions with trees, Ph.D. diss. University of Toronto, 2012. |
| [9] | Isgur, A.; Kuznetsov, V.; Rahman, M.; Tanny, S. M., Nested recursions, simultaneous parameters and tree superpositions, Electron. J. Combin., 21, 1, 1-49 (2014) · Zbl 1331.11008 |
| [10] | Isgur, A.; Kuznetsov, V.; Tanny, S., A combinatorial approach for solving certain nested recursions with non-slow solutions, J. Differ. Equ. Appl., 19, 605-614 (2012) · Zbl 1262.05028 · doi:10.1080/10236198.2012.662967 |
| [11] | Isgur, A.; Lech, R.; Moore, S.; Tanny, S.; Verberne, Y.; Zhang, Y., Constructing new families of nested recursions with slow solutions, SIAM J. Discrete Math., 30, 2, 1128-1147 (2016) · Zbl 1415.11025 · doi:10.1137/15M1040505 |
| [12] | Isgur, A.; Rahman, M.; Tanny, S., Solving non-homogeneous nested recursions using trees, Ann. Comb., 17, 4, 695-710 (2013) · Zbl 1328.05016 · doi:10.1007/s00026-013-0202-9 |
| [13] | Isgur, A.; Reiss, M. D.; Tanny, S., Trees and meta-Fibonacci sequences, Electr. J. Comb., 16, 1, R129 (2009) · Zbl 1188.05011 |
| [14] | Jackson, B. W.; Ruskey, F., Meta-Fibonacci sequences, binary trees and extremal compact codes, Electr. J. Comb., 13, 1, R26 (2006) · Zbl 1084.05004 |
| [15] | Sunohara, M. and Tanny, S., On the solution space of the Golomb recursion, J. Difference Equ. Appl. (2018), DOI: > · Zbl 1444.11029 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
