Pattern Avoidance for Fibonacci Sequences using $k$-Regular Words

Abstract

Two $k$-ary Fibonacci recurrences are $a_k(n)=a_k(n-1)+k\cdot a_k(n-2)$ and $b_k(n)=k\cdot b_k(n-1)+b_k(n-2)$. We provide a simple proof that $a_k(n)$ is the number of $k$-regular words over $[n]=\{1,2,\dots ,n\}$ that avoid patterns $\{121,123,132,213\}$ when using base cases $a_k(0)=a_k(1)=1$ for any $k\ge 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_k(n)$ is the number of $k$-regular words over $[n]$ that avoid $\{122,213\}$ with $b_k(0)=b_k(1)=1$ for any~$k\ge 2$. Finally, we conjecture that $|A{v}_n^2(\underline{121},123,132,213)|=a_1(n{)}^2$ for $n\ge 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