\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{identity}[theorem]{Identity} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \begin{center} \vskip 1cm{\LARGE\bf Words and Linear Recurrences} \vskip 1cm \large Milan Janji\'c \\ Department of Mathematics and Informatics\\ University of Banja Luka\\ Banja Luka, 78000\\ Republic of Srpska\\ Bosnia and Herzegovina \\ \href{mailto:agnus@blic.net}{\tt agnus@blic.net}\\ \end{center} \vskip .2 in \begin{abstract} In previous papers, for an arithmetical function $f_0$, we defined the functions $f_m$ and $c_m$, and designated the number of restricted words over a finite alphabet counted by these functions. In this paper, we examine the reverse problem. For each of the five specific types of restricted words, we find the initial function $f_0$ such that $f_m$ and $c_m$ enumerate these words. We derive explicit formulas for $f_m$ and $c_m$. The Fibonacci, Mersenne, Pell, Jacosthal, Tribonacci, and Padovan numbers all appear as values of $f_m$. We give new combinatorial interpretations and explicit formulas for $f_m$. \end{abstract} \section{Introduction} This paper is a continuation of the investigations of the problem of restricted words enumeration from the author's previous papers~\cite{ja1,ja2,ja3}, where two functions $f_m$ and $c_m$ were defined as follows. For an initial arithmetic function $f_0$, the function $f_m,(m\geq 1)$ is the $m^\text{th}$ invert transform of $f_0$. The function $c_m(n,k)$ was defined as \begin{equation}\label{cmnk} c_m(n,k)=\sum_{i_1+i_2+\cdots+i_k=n}f_{m-1}(i_1)\cdot f_{m-1}(i_2)\cdots f_{m-1}(i_k),\end{equation} where the sum is over positive $i_1,i_2,\ldots,i_k$. The functions $f_m$ and $c_m$ depend only on the initial function $f_0$, and are related to the enumeration of weighted compositions. Namely, if $f_{m-1}(i),(i=1,2,\ldots)$ is the weight of $i$, then $f_m(n)$ is the number of all weighted compositions of $n$, and $c_m(n,k)$ is the number of weighted compositions of $n$ into $k$ parts. In Janji\'c~\cite{ja1,ja2,ja3}, weighted compositions were related to restricted words over a finite alphabet. For a given initial function $f_0$, we investigated restricted words counted by $f_m$ and $c_m$. In this paper, we reverse the problem. Namely, for each of five types of restricted words, we first find the initial function $f_0$ that counts such words. We then derive formulas for $f_m$ and $c_m$ and give its combinatorial meanings in terms of restricted words. We firstly restate results from our recent papers~\cite{ja1,ja2,ja3}, which will be used in this work. \begin{enumerate} \item[(A)]~\cite[Theorem 6]{ja1} Let $f_0$ be an arithmetic function, and let $k$ be a positive integer. If there exist constants $a_0(1),a_0(2),\ldots,a_0(k)$ such that \[f_0(n+k;k)=\sum_{i=1}^ka_0(i)f_0(n+k-i;k),(n\geq 1),\] where $f_0(1;k),f_0(2;k),\ldots,f_0(k;k)$ are arbitrary numbers. Then we have \begin{gather*}f_{1}(i;k)=\sum_{j=1}^if_0(j;k)f_{1}(i-j;k),(i=1,2,\ldots,k),\text{ and}\\ f_{1}(n+k;k)=\sum_{i=1}^ka_{1}(i)f_{1}(n+k-i;k),(n\geq 1),\end{gather*} where \begin{gather*}a_{1}(1)=a_0(1)+f_0(1;k), \\a_{1}(i)=a_0(i)+f_0(i;k)-\sum_{j=1}^{i-1}a_0(j)f_0(i-j;k),(2\leq i\leq k). \end{gather*} \item[(B)]~\cite[Corollary 9]{ja1}. If $f_0(1),f_0(2),a_0(1),a_0(2)$ are arbitrary, and \[f_0(n+2)=a_0(1)f_0(n+1)+a_0(2)f_0(n),\] then \begin{gather*}f_m(1)=f_0(1),\;f_m(2)=mf_0(1)^2+f_0(2),\\ f_m(n+2)=a_m(1)f_m(n+1)+a_m(2)f_m(n),\end{gather*} where \[a_m(1)=a_0(1)+mf_0(1), a_m(2)=a_0(2)-ma_0(1)f_0(1)+mf_0(2).\] \item[(C)]~\cite[Proposition 23]{ja1}. Assume that $f_0(1)=0$, and $f_0(i)=1,(i>1)$. Then we have \[f_m(1)=0,f_m(2)=1,\] and \[f_m(n+2)=f_m(n+1)+mf_m(n).\] \item[(D)]\cite[Corollary 2]{ja2}. The following formula holds: \[f_m(n)=\sum_{k=1}^nc_m(n,k).\] \item[(E)]~\cite[Proposition 6]{ja3}. The following formula holds: \[c_m(n,k)=\sum_{i=k}^n(m-1)^{i-k}{i-1\choose k-1}c_1(n,i),\;(1\leq k\leq n).\] \item[(F)]~\cite[Propositions 12]{ja3}. Assume that $f_{0}(1)=1$ and $m>1$. Assume next that, for $n\geq 1$, we have $f_{m-1}(n)$ words of length $n-1$ over a finite alphabet $\alpha$. Let $x$ be a letter which is not in $\alpha$. Then, $c_m(n,k)$ is the number of words of length $n-1$ over the alphabet $\alpha\cup\{x\}$ in which $x$ appears exactly $k-1$ times. \end{enumerate} We consider the following five types of restricted words over a finite alphabet: \begin{itemize} \item[1.] Words over $\{0,1,\ldots,a-1,\ldots\}$, such that no two adjacent letters from $\{0,1,\ldots,a-1\}$ are the same. \item[2.] Words over $\{0,1,\ldots,a-1,\ldots\}$ such that letters $0,1,\ldots,a-1$ avoid a run of odd length. \item[3.] Words over $\{0,1,\ldots,a,\ldots\}$ avoiding subwords of the form $0i,(i=1,\ldots,b)$, for $b0$. It is easy to see that \begin{equation*}f_0(n)=a(a-1)^{n-2},(n\geq 2).\end{equation*} \begin{remark} This formula appears in Birmajer at al.~\cite[Example 17]{bir}. Also, the case $a=1$ is considered in~\cite[Example 18]{ja3}. \end{remark} The function $f_0$ has the following combinatorial interpretation: \begin{proposition} The number $f_0(n)$ is the number of words of length $n-1$ over $\{0,1,\ldots,a-1\}$ such that no two adjacent letters are the same. \end{proposition} \begin{proof} We have $f_0(1)=1$, since only the empty word has length $0$. Also, $f_0(2)=a$, since a word of length $1$ may consist of an arbitrary letter. To obtain a word of length $n+2$, for $n>0$, we need to insert $a-1$ letters in front of each word of length $n+1$. \end{proof} As an immediate consequence of (B), we obtain \begin{corollary}\label{co1} For $m\geq 0$, the following recurrence holds: \begin{gather*}f_m(1)=1,f_m(2)=m+a,\\f_m(n+2)=(m+a-1)f_m(n+1)+mf_m(n),(n\geq 1).\end{gather*} \end{corollary} We now describe words counting by $f_m$. \begin{proposition} The number $f_m(n)$ is the number of words of length $n-1$ over the alphabet $\{0,1,\ldots,a-1,a,\ldots,m+a-1\}$, such that no two adjacent letters from $\{0,1,\ldots,a-1\}$ are the same. \end{proposition} \begin{proof} We have $f_m(1)=1$, since only the empty word has length $0$. Also, $f_m(2)=m+a$ since a word of length $1$ may consist of any letter of the alphabet. Assume that $n>2$. Consider a word of length $n+1$. In front of such a word, we insert a letter different from the first letter of the word. In this way, we obtain all words of length $n+2$ beginning with two different letters. The remaining words must begin with two same letters. Since there are $mf_m(n)$ such words, the statement is true. \end{proof} \begin{remark} For $a=2$, the continued fraction $[f_0(1);f_0(2),f_0(3),\ldots]$ equals $\sqrt 2$. The sequence $f_1(1),f_1(2),\ldots,f_1(n)$ is the numerator of the $n$th convergent of $\sqrt 2$. Also, $f_1(n)$ is the number of ternary words of length $n-1$ avoiding $00$ and $11$. \end{remark} Since $f_m(1)=1$, we may apply (F) to obtain \begin{proposition} The number $c_m(n,k)$ is the number of words of length $n-1$ over $\{0,1,\ldots,a-1,\ldots,m+a-1\}$ in which $k-1$ letters equal $m+a-1$, and no two adjacent letter from $\{0,1,\ldots,a-1\}$ are identical. \end{proposition} We next derive an explicit formula for $c_1(n,k)$. \begin{proposition}\label{c1nk} We have \begin{gather*}c_1(n,n)=1,\\c_1(n,k)=\sum_{i=0}^{k-1}{k\choose i}{n-k-1\choose k-i-1}a^{k-i}(a-1)^{n-2k+i},(k0$, the number $f_0(n)$ is the number of words of length $n-1$ over the alphabet $\{0,1,\ldots,a-1\}$ in which there are no runs of odd length. \end{proposition} \begin{proof} Let $d(n)$ denote the number of words of length $n$, which we wish to count. Firstly, $d(0)=1$ since only the empty word has length $0$. Next, $d(1)=0$ as there are no runs of length $1$. Assume that $n>2$. A word of length $n$ must begin with two identical letters. Hence, there are $ad(n-2)$ such words. We conclude that the following recurrence holds: \begin{equation*}d(0)=1,d(1)=0, d(n)=ad(n-2),(n\geq 2),\] which yields $d(n-1)=f_0(n),(n\geq 1)$. \end{proof} From (\ref{r1}), we easily obtain the following explicit formula for $f_0$: \begin{equation*} f_0(n)=\begin{cases}0,&\text{ if $n=2t$};\\a^t,&\text{ if $n=2t+1$}. \end{cases} \end{equation*} Using (B) yields \begin{corollary}\label{co2} For $m\geq 0$, the following recurrence holds: \begin{gather*}f_m(1)=1,f_m(2)=m,\\f_m(n+2)=mf_m(n+1)+af_m(n),(n\geq 1).\end{gather*} \end{corollary} \begin{proposition}\label{pp5} The number $f_m(n)$ is the number of words of length $n-1$ over $\{0,1,\ldots,a-1,\ldots,a+m-1\}$, such that letters $0,1,\ldots,a-1$ avoid runs of odd length. \end{proposition} \begin{proof} We let $d(n)$ denote the number of desired words of length $n-1$. It is clear that $d(0)=1$ and $d(1)=m$. A word of length $n+1$ may begin with a letter from $\{a,a+1,\ldots,a+m-1\}$. There are $md(n)$ such word. If a word begins with a letter from $\{0,1,\ldots,a-1\}$, it must be followed by the same letter. Hence, there are $ad(n-1)$ such words. We conclude that $d(n)=f_m(n+1)$. \end{proof} Some well-known classes of numbers satisfy the recurrence from Corollary \ref{co2}. We give the appropriate combinatorial meaning for some of them. \begin{enumerate} \item The case $a=1,m=1$ concerns the Fibonacci numbers. The number of binary words of length $n-1$ in which $0$ avoids a run of odd length is $F_{n}$. \item The case $a=1,m=2$ concerns the Pell numbers $P_n$ ( \seqnum{A000129}). The number of ternary words of length $n-1$ in which $0$ avoids runs of odd length is $P_n$. \item The case $a=2,m=1$ concerns the Jacobsthal numbers $J_n$ (\seqnum{A001045}). The number of ternary words of length $n-1$ in which $0$ and $1$ avoid runs of odd length is $J_n$. \end{enumerate} From the combinatorial interpretation, we easily derive an explicit formula for $f_m(n)$. \begin{proposition}\label{lrj} We have \begin{equation*}f_m(n)=\sum_{j=0}^{\lfloor\frac {n-1}{2}\rfloor}m^{n-2j-1}a^{j}{n-1-j\choose j}.\] \end{proposition} \begin{proof}According to Proposition \ref{pp5}, in a word counted by $f_m$, the letters from $\{0,1,\ldots,a-1\}$ may appear only in pairs. There are $a$ such pairs. We may choose $j,(0\leq j\leq \lfloor\frac{n-1}{2}\rfloor)$ pairs in a word of length $n-1$. These $j$ pairs may be chosen in ${n-j-1\choose j}$ ways. When we have chosen $j$ pairs from $\{0,1,\ldots,a-1\}$, the remaining $n-1-2j$ letters are from $\{a,a+1,\ldots,a+m-1\}$, which are $m$ in number. \end{proof} As a consequence, we obtain the following similar explicit formulas for the Fibonacci, Pell and Jacobsthal numbers: \begin{gather*}F_n=\sum_{j=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}{n-j-1\choose j}, P_n=\sum_{j=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}2^{n-2j-1}{n-j-1\choose j},\\J_n=\sum_{j=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}2^{j}{n-j-1\choose j} .\end{gather*} From (F), we obtain \begin{proposition} The number $c_m(n,k)$ is the number of words of length $n-1$ over the alphabet $\{0,1,\ldots,a-1,\ldots,a+m-1\}$ in which the letter $a+m-1$ appears $k-1$ times, and letters from $\{0,1,\ldots,a-1\}$ avoid runs of odd length. \end{proposition} We now derive an explicit formula for $c_1(n,k)$. \begin{proposition}\label{plr} The following equation holds: \begin{equation*}c_1(n,k)=\begin{cases}a^{\frac{n-k}{2}}{\frac{n+k}{2}-1\choose k-1},&\text{ if $n-k$ is even};\\0,&\text{ if $n-k$ is odd }.\end{cases} \end{equation*} \end{proposition} \begin{proof} Each term in (\ref{cmnk}) in which $i_t$ is even equals zero. Hence, (\ref{cmnk}) becomes \begin{gather*}c_1(n,k)=\sum_{2j_1+1+2j_2+1+\cdots+2j_k+1=n}a^{j_1}\cdot a^{j_2}\cdots a^{j_k}\\=a^{\frac{n-k}{2}}\sum_{s_1+s_2+\cdots+s_k=\frac{n+k}{2}}1=a^{\frac{n-k}{2}}{\frac{n+k}{2}-1\choose k-1}. \end{gather*} Note that the last sum is over positive $s_1,s_2,\ldots,s_k$. \end{proof} As a consequence of (D), we obtain the following explicit formulas for the Fibonacci and Jacobsthal numbers: \begin{gather*}F_{2n}=\sum_{k=1}^n{n+k-1\choose n-k},F_{2n-1}=\sum_{k=1}^n{n+k-2\choose n-k},\\ J_{2n}=\sum_{k=1}^n2^{n-k}{n+k-1\choose n-k},J_{2n-1}=\sum_{k=1}^n2^{n-k}{n+k-2\choose n-k}. \end{gather*} Furthermore, we derive an explicit formula for $c_2(n,k)$. Using (E), for even $n$, we obtain \begin{gather*}c_2(2n,k)=\sum_{i=k}^{2n}{i-1\choose k-1} c_1(2n,i)= \sum_{j=\lceil\frac k2\rceil}^{n}{2j-1\choose k-1} c_1(2n,2j)\\ =\sum_{j=\lceil\frac k2\rceil}^{n}a^{n-j}{2j-1\choose k-1}{n+j-1\choose n-j}. \end{gather*} For odd $n$, we have \begin{gather*}c_2(2n-1,k)=\sum_{i=k}^{2n-1}{i-1\choose k-1}c_1(2n,i)= \sum_{j=\lceil\frac {k+1}{2}\rceil}^{n}{2j-2\choose k-1}c_1(2n-1,2j-1)\\ =\sum_{j=\lceil\frac {k+1}{2}\rceil}^{n}a^{n-j}{2j-2\choose k-1}{n+j-2\choose n-j}. \end{gather*} In particular, for $a=1$, we obtain the following formulas for Pell numbers: \begin{gather*}P_{2n}=\sum_{k=1}^{2n}\sum_{j=\lceil\frac k2\rceil}^{n}{2j-1\choose k-1}{n+j-1\choose n-j},\\ P_{2n-1}=\sum_{k=1}^{2n-1}\sum_{j=\lceil\frac{k+1}{2}\rceil}^{n}{2j-2\choose k-1}{n+j-2\choose n-j}. \end{gather*} \begin{remark} Using (E), we easily obtain an explicit formula for $c_m(n,k)$. \end{remark} The following arrays in~\cite{slo} are related with this case: \seqnum{A000129},\seqnum{A001045},\seqnum{A168561}, \seqnum{A037027}, \seqnum{A054456}, \seqnum{A132964}, \seqnum{A073370}. \section{Case 3} Let $a>b>0$ be integers. We define $f_0$ by the following recurrence: \begin{gather*}\label{re2}f_0(1)=1,f_0(2)=a,\\ f_0(n+2)=af_0(n+1)-bf_0(n),(n\geq 1).\end{gather*} \begin{proposition} The number $f_0(n)$ is the number of words of length $n-1$ over the alphabet $\{0,1,\ldots,a\}$, avoiding subwords of the form: $0i,(i=1,\ldots,b)$. \end{proposition} \begin{proof} We let $d(n)$ denote the number of words of length $n-1$. Firstly, $d(0)=1$, since only the empty word has length $0$. Next, $d(1)=a$, since there are no restrictions on words of length $1$. Assume that $n>1$. We have $a\cdot d(n-1)$ words beginning with arbitrary letter. From this number, we must subtract words which begin with subwords $0i,(i=1,2,\ldots,b)$. Hence, $d(n)$ satisfies the same recurrence as $f_0(n)$. \end{proof} \begin{example} \begin{enumerate} \item If $a=2,b=1$, we have \begin{gather*}f_0(1)=1,f_0(2)=2,\\f_0(n+2)=2f_0(n+1)-f_0(n),(n\geq 1),\end{gather*} which yields that $f_0(n)=n$. Hence, $n$ is the number of binary words of length $n-1$ avoiding subword $01$, which is obvious. \item If $a=3,b=1$, we have \begin{gather*}f_0(1)=1,f_0(2)=3,\\f_0(n+2)=3f_0(n+1)-f_0(n),(n\geq 1),\end{gather*} which is a well-known recurrence for the Fibonacci numbers $F_{2n}$. \end{enumerate} \end{example} We thus obtain the following combinatorial interpretation of the bisection of the Fiboncci numbers. \begin{corollary} The number of ternary words of length $n-1$ avoiding $01$ is $F_{2n}$. \end{corollary} We consider the particular case $a=b+1$. \begin{corollary} If $b>1$ and $a=b+1$, then \begin{equation*}f_0(n)=\frac{b^n-1}{b-1}.\end{equation*} \end{corollary} \begin{proof} We denote $\frac{b^n-1}{b-1}$ by $g_0(n)$. We have $g_0(1)=1,g_0(2)=1+b=a$. Further, \begin{equation*} (b+1)\cdot g_0(n+1)-b\cdot g_0(n)=(b+1)\cdot\frac{b^{n+1}-1}{b-1}-b\cdot\frac{b^n-1}{b-1}=\frac{b^{n+2}-1}{b-1}. \end{equation*} By induction, we conclude that $g_0=f_0$. \end{proof} In particular, for $a=3,b=2$, we have $f_0(n)=2^n-1$, which yields \begin{corollary} The Mersenne number $2^n-1$ is the number of ternary words of length $n-1$ avoiding $01$ and $02$. \end{corollary} Using (B), we obtain \begin{gather*} \label{ab1}f_m(1)=1,f_m(2)=m+a,\\f_m(n+2)=(a+m)f_m(n+1)-bf_m(n),(n\geq 1).\end{gather*} This means that $f_m$ counts the same sort of words as $f_0$, with $m+a$ instead of $a$. Using (F) and (D), we obtain the following combinatorial interpretations of $c_m(n,k)$ and $f_m(n)$. \begin{corollary} \begin{enumerate} \item The number $c_m(n,k)$ is the number of words of length $n-1$ over $\{0,1,\ldots,b-1,b\ldots,m+a-1\}$ having exactly $k-1$ letters equal $m+a-1$ and avoiding subwords $0j,(j=1,2,\ldots,b)$. \item The number $f_m(n)$ is the number of words of length $n-1$ over the alphabet $\{0,1,\ldots,b-1,b\ldots,m+a-1\}$ and avoiding subwords $0j,(j=1,2,\ldots,b)$. \end{enumerate} \end{corollary} We next derive an explicit formula for $c_1(n,k)$. A generating function for the sequence $f_0(1),f_0(2),\ldots$ is $\frac{1}{bx^2-ax+1}$. According to~\cite[Equation (1)]{ja3}, we have \begin{equation*}\frac{x^k}{(bx^2-ax+1)^k}=\sum_{n=k}^\infty c_1(n,k)x^k.\end{equation*} The numbers $\alpha=\frac{a+\sqrt{a^2-4b}}{2b}$ and $\beta=\frac{a-\sqrt{a^2-4b}}{2b}$ are the solutions of the equation $bx^2-ax+1=0$. We thus obtain \begin{proposition}\label{p10} The following equation holds: \begin{equation*}c_1(n,k)=\frac{1}{b^k}\sum_{j=0}^{n-k}\frac{1}{\alpha^{j+k}\beta^{n-j}}{n-j-1\choose k-1}{k+j-1\choose k-1}.\] \end{proposition} \begin{proof} We expand $\frac{x^k}{b^k(\alpha-x)^k(\beta-x)^k}$ into powers of $x$. Since \begin{equation*}\frac{1}{(\gamma -x)^k}=\sum_{i=0}^\infty{k+i-1\choose k-1}\frac{x^i}{\gamma^{i+k}},\end{equation*} we easily obtain \begin{equation*}\frac{x^k}{b^k(\alpha-x)^k(\beta-x)^k}=\sum_{i=0}^\infty \left[\sum_{j=0}^i\frac{1}{b^k\alpha^{j+k} \beta^{i-j+k}} {k+j-1\choose k-1}{k+i-j-1\choose k-1}\right]x^{i+k},\end{equation*} and the statement follows by replacing $i$ by $n-k$. \end{proof} In the case $a=b+1$, we have $\alpha=1$ and $\beta=\frac 1b$. Therefore, the following formula holds: \begin{equation}\label{amb}c_1(n,k)=\sum_{i=0}^{n-k} b^{n-k-i}{n-i-1\choose k-1}{k+i-1\choose k-1}.\end{equation} Using (\ref{cmnk}), we obtain the following identity: \begin{identity} \begin{equation*} \sum_{i_1+i_2+\cdots+i_k=n}\left[\prod_{t=1}^k(b^{i_t}-1)\right]=\sum_{i=0}^{n-k} b^{n-k-i}{n-i-1\choose k-1}{k+i-1\choose k-1}, \end{equation*} where $i_t>0,(t=1,2,\ldots,k)$. \end{identity} \begin{remark} Using (D) and (E), we obtain explicit formulas for $f_m(n)$ and $c_m(n,k)$. \end{remark} The following arrays in~\cite{slo} are related with this case: \seqnum{A078812}, \seqnum{A125662}, \seqnum{A207823}, \seqnum{A207824}, \seqnum{A110441}, \seqnum{A116414}. \section{Case 4} We let $\mathcal R_4$ denote the condition given in this case. We first solve the problem for binary words. \begin{proposition}Let $f_0(n)$ be the number of binary words satisfying $\mathcal R_4$. Then, \begin{gather*} f_0(1)=1,f_0(2)=0,\\f_0(n+2)=f_0(n+1)+f_0(n),(n>1).\\ f_0(n)=F_{n-2},(n>1). \end{gather*} \end{proposition} \begin{proof} We have $f_0(1)=1$, since the empty word has length $0$. Next, $f_0(2)=0$, since no words of length $1$ satisfy $\mathcal R_4$. Also, $f_0(3)=1$, since $10$ is the only word of length $2$ satisfying $\mathcal R_4$. Next, $f_0(4)=1$, since $100$ is the only word of length $3$ satisfying $\mathcal R_4$. Assume that $n>1$. Then, \begin{equation*}f_0(n+4)=f_0(n+2)+f_0(n+1)+\cdots,\end{equation*} since a word of length greater than $3$ must begin with a subword of the form $10\ldots 0$. Analogously, we obtain \begin{equation*}f_0(n+5)=f_0(n+3)+f_0(n+2)+\cdots.\end{equation*} Comparing these two equations, we get \begin{equation*}f_0(n+5)=f_0(n+4)+f_0(n+3).\end{equation*} The explicit formula follows from the preceding recurrence. \end{proof} Since $f_0(1)=1$, and so $f_m(1)=1$, using (D) and (F), we obtain the following combinatorial interpretations of $f_m$ and $c_m(n,k)$. \begin{corollary} \begin{enumerate} \item The number $c_m(n,k)$ is the number of words of length $n-1$ over $\{0,1,\ldots,m+1\}$ having $k-1$ letters equal $m+1$ and satisfying $\mathcal R_4$. \item The number $f_m(n)$ is the number of words of length $n-1$ over the alphabet $\{0,1,\ldots,m+1\}$ satisfying $\mathcal R_4$. \end{enumerate} \end{corollary} We next derive an explicit formula for $c_1(n,k)$. It is known that $c_1(n,k)$ is the coefficient of $x^n$ in the expansion of $\left(\sum_{i=1}^\infty F_{i-2}x^i\right)^k$ into powers of $x$. We consider the following auxiliary initial function: \begin{equation*}\overline{f}_0(1)=0,\overline{f}_0(n)=1,(n>1).\end{equation*} From~\cite[Proposition 23]{ja1}, we obtain $\overline{f}_1(n)=F_{n-1}$. It is proved in~\cite[Proposition 13]{ja2} that \begin{equation*}\overline{c}_1(n,k)={n-k-1\choose k-1},\left(k=1,2,\ldots,\left\lfloor\frac n2\right\rfloor\right),\end{equation*} and $\overline{c}_1(n,k)=0$ otherwise. Using (E) yields \begin{equation*}\overline{c}_2(n,k)=\sum_{i=k}^{\left\lfloor\frac n2\right\rfloor}{i-1\choose k-1}{n-i-1\choose i-1}.\end{equation*} Hence, \begin{equation}\label{xy}\left(\sum_{i=1}^\infty F_{i-1}x^i\right)^k=\sum_{n=k}^\infty\overline{c}_2(n,k)x^n.\end{equation} We let $X$ denote $\sum_{i=1}^\infty F_{i-1}x^i$. We have to expand the expression $Y^k$, where $Y=\sum_{i=1}^\infty F_{i-2}x^i.$ Since $F_{-1}=1$, we have that $Y=x(1+X)$, which yields \begin{equation*}Y^k=x^k\left(1+\sum_{i=1}^k{k\choose i}X^i\right)^k=\sum_{n=k}^\infty c_1(n,k)x^n.\end{equation*} Using the binomial theorem and (\ref{xy}) yields \begin{equation*}Y^k=x^k+\sum_{i=1}^k\sum_{j=i}^\infty{k\choose i}\overline{c}_2(j,i)x^{j+k}.\end{equation*} For $j+k=n$, the coefficient of $x^n$ on the right-hand side of this equation equals $\sum_{i=1}^k{k\choose i}\overline{c}_2(n-k,i)$. We thus obtain \begin{proposition}\label{p16} The following equations hold: \begin{gather*}c_1(n,n)=1,\\ c_1(n,k)=\sum_{i=1}^k\sum_{j=i}^{\left\lfloor\frac{n-k}{2}\right\rfloor}{k\choose i}{j-1\choose i-1}{n-k-j-1\choose j-1},(n>k).\end{gather*} \end{proposition} \begin{proposition}\label{p16} We have \begin{gather*}c_1(n,n)=1,\\ c_1(n,k)=\sum_{t=1}^k\sum_{j=t}^{\left\lfloor\frac{n-k}{2}\right\rfloor}{k\choose t}{j-1\choose t-1}{n-k-j-1\choose j-1},(n>k).\end{gather*} \end{proposition} Using (B), we easily obtain the following recurrence for $f_m$: \begin{gather*}f_m(1)=1,f_m(2)=m,\\f_m(n+2)=(m+1)f_m(n+1)-(m-1)f_m(n).\end{gather*} We examine two particular cases. In the case $m=1$, we obtain \begin{gather*}f_1(1)=1,f_1(2)=1,\\f_1(n+2)=2f_1(n+1),(n>1),\end{gather*} which implies \begin{gather*}f_1(1)=f_1(2)=1,f_1(n)=2^{n-2},(n>2).\end{gather*} We thus obtain the following property of powers of $2$. \begin{corollary} For $n\geq 2$, the number $2^{n-2}$ is the number of ternary words of length $n-1$ satisfying $\mathcal R_4$. \end{corollary} As a consequence, the following Euler-type identity holds: \begin{identity} For $n>2$, the number of binary words of length $n-2$ is the number of ternary words of length $n-1$, in which $0$ and $1$ appear only in a run of the form $1i$, where $i$ is the run of zeros of length $i\geq 1$. \end{identity} From Propositions \ref{p16} and (D), we obtain the following identity for the Mersenne numbers: \begin{identity} \begin{equation*}2^{n-2}-1=\sum_{k=1}^{n}\sum_{i=1}^k\sum_{j=i}^{\left\lfloor\frac{n-k}{2}\right\rfloor}{k\choose i}{j-1\choose i-1}{n-k-j-1\choose j-1},(n>2).\end{equation*} \end{identity} We now consider the case $m=2$. We have \begin{gather*}f_2(1)=1,f_2(2)=2,\\f_2(n+2)=3f_2(n+1)-f_2(n),\end{gather*} which is the recurrence for Fibonacci numbers $F_{2n-1}$. We thus have \begin{corollary} The Fibonacci number $F_{2n-1}$ is the number of quaternary words of length $n-1$ satisfying $\mathcal R_4$. \end{corollary} Calculating values for $c_2(n,k)$, we obtain an odious expression for $F_{2n-1}$. \begin{identity} \begin{equation*}F_{2n-1}=\sum_{k=1}^n\sum_{i=k}^{n}\sum_{t=0}^i\sum_{j=t}^{\left\lfloor\frac{n-i}{2}\right\rfloor} {i-1\choose k-1}{i\choose t}{j-1\choose t-1}{n-i-j-1\choose j-1}.\end{equation*} \end{identity} \begin{remark} Using (E) and (D), we obtain the explicit formulas for $c_m(n,k)$ and $f_m(n)$. \end{remark} The following arrays in~\cite{slo} are related with this case: \seqnum{A105422}, \seqnum{A105306}, \seqnum{A062110}, \seqnum{A188137}. \section{Case 5} We let $\mathcal R_5$ denote the given condition. Again, we first consider the binary words. \begin{proposition} \begin{equation*}f_0(1)=1,f_0(2)=0,f_0(3)=1.\end{equation*} \begin{equation}\label{rkk}f_0(n+3)=f_0(n+1)+f_0(n),(n\geq 1).\end{equation} We have $f_0(n)=p_{n+2}$, where $p_n$ is the $n$th Padovan number (\seqnum{A000931}). \end{proposition} \begin{proof} It is easy to see that the initial conditions are fulfilled. A word of length $n+2$ begins with either two zeros or three ones and (\ref{rkk}) follows. Since $(\ref{rkk})$ is the recurrence for the Padovan numbers, the second statement is true. \end{proof} This means that the Padovan number $p_{n+2}$ is the number of binary words of length $n-1$ in which $0$ appears in runs of even length, while $1$ appears in runs, the lengths of which are divisible by $3$. This is equivalent to the fact that the Padovan numbers count the compositions into parts $2$ and $3$, which is known fact (see comment of \seqnum{A000931}). \begin{corollary}\label{fib} \begin{enumerate} \item The function $f_m$ satisfies the following recurrence: \begin{gather*}f_m(1)=1,f_m(2)=m,f_m(3)=m^2+1,\\f_m(n+3)=mf_m(n+2)+f_m(n+1)+f_m(n),(n>1).\end{gather*} \item Then, $c_m(n,k)$ is the number of words of length $n-1$ over $\{0,1,\ldots,m+1\}$ having $k-1$ letters equal to $m+1$, and satisfying $\mathcal R_5$. \item Then, $f_m(n)$ is the number of words of length $n-1$ over $\{0,1,\ldots,m+1\}$ satisfying $\mathcal R_5$. \end{enumerate} \end{corollary} \begin{proof} The claim 1. easily follows from (A). The claims 2. and 3. follow from $(F)$ and (D). We add a short combinatorial proof for 2. Equation $f_m(1)=1$ means that the empty word satisfies $\mathcal R_5$. Further, $f_m(2)=m$ means that a word of length $1$ may consist of any letter except $0$ and $1$. Next, $f_m(3)=m^2+1$ means that a word of length $2$ may consist of pairs from $\{2,3,\ldots,m+1\}$, which are $m^2$ in number, plus the word $00$. Finally, a word of length $n>2$ may begin with any letter from $\{2,3,\ldots,m+1\}$, or from $00$, or from $111$. \end{proof} The case $m=1$ in Corollary \ref{fib} is the recurrence for Tribonacci numbers. Hence, \begin{corollary} The sequence $1, 1, 2, 4, 7,\ldots$ of the Tribonacci numbers is the invert transform of the sequence $1,0,1,1,1,2,\ldots$ of the Padovan numbers. Also, Tribonacci numbers count ternary words satisfying $\mathcal R_5$. \end{corollary} Finally, we calculate $c_1(n,k)$. We define the arithmetic function $\overline{f}_0$ such that $\overline{f}_0(2)=\overline{f}_0(3)=1$, and $\overline{f}_0(n)=0$ otherwise. It is proved in~\cite[Propositon 5]{ja2} that $\overline{c}_1(n,k)={k\choose n-2k}$. \begin{gather*}\overline{f}_1(1)=0,\overline{f}_1(2)=1,\overline{f}_1(3)=1,\\ \overline{f}_1(n+3)=\overline{f}_0(n+1)+\overline{f}_0(n).\end{gather*} This implies that $\overline{f}_1(n)=f_0(n-1),(n>1)$. The sequence $f_0(1),f_0(2),\ldots$ is thus obtained by inserting $1$ at the beginning of the sequence $\overline{f}_1(1),\overline{f}_1(2),\ldots$. Using (E), we obtain \begin{equation*}\overline{c}_2(n,k)=\sum_{i=k}^n{i-1\choose k-1}\cdot{i\choose n-2\cdot i},\end{equation*} which yields \begin{equation}\label{jjj}\left(\sum_{i=1}^\infty\overline{f}_1(i)x^i\right)^k= \sum_{n=k}^\infty\overline{c}_2(n,k)x^n.\end{equation} To obtain an explicit formula for $c_1(n,k)$, we need to expand the expression $X$ given by $X=\left(\sum_{i=1}^\infty f_0(i)x^i\right)^k$ into powers of $x$. We have \begin{equation*}X=\left(x+\sum_{i=2}^\infty f_0(i)x^i\right)^k=(x+xY)^k,\end{equation*} where $Y=\sum_{i=1}^\infty \overline{f}_1(i)x^i$. Hence, \begin{equation*}X=x^k\sum_{i=0}^k{k\choose i}Y^i.\end{equation*} Applying Equation(\ref{jjj}) yields \begin{equation*}X=\sum_{i=0}^k{k\choose i}\sum_{j=i}^\infty\overline{c}_2(j,i)x^{j+k}.\end{equation*} Taking $n=j+k$, we get \begin{proposition} The following formulas hold: \begin{gather*}c_1(n,n)=1,\\c_1(n,k)=\sum_{i=0}^k\sum_{j=i}^{n-k}{k\choose i}{j-1\choose i-1}{j\choose n-k-2j},(k