Pattern Avoidance for Fibonacci Sequences using k-Regular Words

Two k-ary Fibonacci recurrences are aₖ(n) = aₖ(n-1) + k · aₖ(n-2) and bₖ(n) = k · bₖ(n-1) + bₖ(n-2). We provide a simple proof that aₖ(n) is the number of k-regular words over [n] = \1,2,…,n\ that avoid patterns \121, 123, 132, 213\ when using base cases aₖ(0) = aₖ(1) = 1 for any k ≥ 1. This was previously proven by Kuba and Panholzer in the context of Wilf-equivalence for restricted Stirling permutations, and it creates Simion and Schmidt's classic result on the Fibonacci sequence when $k=1$, and the Jacobsthal sequence when $k=2$. We complement this theorem by proving that bₖ(n) is the number of k-regular words over $[n]$ that avoid \122, 213\ with bₖ(0) = bₖ(1) = 1 for any~k ≥ 2. Finally, we conjecture that |Av²ₙ(121, 123, 132, 213)| = a₁(n)² for n ≥ 0. That is, vincularizing the Stirling pattern in Kuba and Panholzer's Jacobsthal result gives the Fibonacci-squared numbers. 20 pages, submitted to special journal issue for Permutation Patterns 2023 (PP23) in DMTCS