<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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, BA\\
\href{mailto:agnus@blic.net}{\tt agnus@blic.net}\\
\end{center}

\vskip .2 in

\begin{abstract}
In previous papers, we defined functions $f_m$ and $c_m$ based on
an  arithmetical function $f_0$,  and determined numbers 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$.

 Fibonacci, Mersenne, Pell,  Jacosthal, Tribonacci, and Padovan
  numbers all appear as values of $f_m$. We derive their new combinatorial interpretations
   and the explicit formulas.
\end{abstract}

\section{Introduction}
We continue the investigation of
restricted word enumeration from previous papers Janji\c~\cite{ja1,ja2,ja3},
where functions $f_m$ and $c_m$ were defined as follows.
 For an initial arithmetic function $f_0$ and $m\geq 1$, the function $f_m$ 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 integers $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 the value of $f_{m-1}(i)$ is the weight of $i$, then the value of $f_m(n)$ is the number of weighted compositions of $n$,
 and the value of $c_m(n,k)$ is the number of weighted compositions of $n$ into $k$ parts.

In \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 consider the reverse problem. For each of the five types of restricted words,     we first find the initial function $f_0$ which counts these words. We then derive formulas  for $f_m$ and $c_m$ and give their combinatorial meanings in term of restricted words.

To begin with, we restate the results from  papers~\cite{ja1,ja2,ja3} that we will use 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. Assume that there exist constants $a_0(1),a_0(2),\ldots,a_0(k)$ such that
\begin{equation*}f_0(n+k;k)=\sum_{i=1}^ka_0(i)f_0(n+k-i;k),(n\geq 1),\end{equation*}
where $f_0(1;k),f_0(2;k),\ldots,f_0(k;k)$ are arbitrary numbers.
Then, we have
\begin{align*}f_{1}(i;k)&amp;=\sum_{j=1}^if_0(j;k)f_{1}(i-j;k),(i=1,2,\ldots,k),\\
f_{1}(n+k;k)&amp;=\sum_{i=1}^ka_{1}(i)f_{1}(n+k-i;k),(n\geq 1),\end{align*}
where
\begin{align*}a_{1}(1)&amp;=a_0(1)+f_0(1;k),
\\a_{1}(i)&amp;=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{align*}

\item[(B)]~\cite[Corollary 9]{ja1} If  $f_0(1),f_0(2),a_0(1),a_0(2)$ are arbitrary, and
 \begin{equation*}f_0(n+2)=a_0(1)f_0(n+1)+a_0(2)f_0(n),\end{equation*}
then
\begin{align*}f_m(1)&amp;=f_0(1),\;f_m(2)=mf_0(1)^2+f_0(2),\\
f_m(n+2)&amp;=a_m(1)f_m(n+1)+a_m(2)f_m(n),\end{align*}
where \begin{align*}a_m(1)&amp;=a_0(1)+mf_0(1),\\ a_m(2)&amp;=a_0(2)-ma_0(1)f_0(1)+mf_0(2).\end{align*}
\item[(C)]~\cite[Proposition 23]{ja1}
 Assume that $f_0(1)=0$ and $f_0(i)=1,(i&gt;1)$.
Then, we have
\begin{align*}f_m(1)&amp;=0,f_m(2)=1,\\
f_m(n+2)&amp;=f_m(n+1)+mf_m(n).\end{align*}
\item[(D)]\cite[Corollary 2]{ja2} The following formula holds:
\begin{equation*}f_m(n)=\sum_{k=1}^nc_m(n,k).\end{equation*}
\item[(E)]~\cite[Proposition 6]{ja3}
The following formula holds:
\begin{equation*}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).\end{equation*}
\item[(F)]~\cite[Propositions 12]{ja3}
 Assume that $f_{0}(1)=1$, and that $m&gt;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, the value of $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 proceed to consider the following five types of restricted words over a finite alphabet:
\begin{enumerate}
\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
(Property $\mathcal P_1$).
\item[2.]
Words over $\{0,1,\ldots,a-1,\ldots\}$ such that letters $0,1,\ldots,a-1$
avoid a run of odd length (Property $\mathcal P_2$).
\item[3.] Words over  $\{0,1,\ldots,a,\ldots\}$
  avoiding subwords of the form $0i,(i=1,\ldots,b)$ for $b&lt;a$ (Property $\mathcal P_3$).
 \item[4.]
 Words over  $\{0,1,\ldots\}$ such that $0$ and $1$ appear only as  subwords of the form $1i$,  where $i$ is a run of zeros (Property $\mathcal P_4$).
 \item[5.]
 Words over $\{0,1,\ldots\}$ in which $0$ appears only in a run of even length,
 and $1$ appears only in a run of a length  divisible by $3$ (Property $\mathcal P_5$).
\end{enumerate}


We also note that, in all types, the initial function $f_0$ is defined by a linear
homogenous recurrence.
\section{Type 1} In this case, we  consider the following linear recurrence:
\begin{align*}f_0(1)&amp;=1,f_0(2)=a,\\f_0(n+2)&amp;=(a-1)f_0(n+1),(n\geq 1),
\end{align*}
where $a&gt;0$.
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 value of $f_0(n)$ is the number of words of length $n-1$ over
$\{0,1,\ldots,a-1\}$  satisfying $\mathcal P_1$.
\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&gt;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 the following result.
\begin{corollary}\label{co1}
For $m\geq 0$, the following recurrence holds:
\begin{align*}f_m(1)&amp;=1,f_m(2)=m+a,\\f_m(n+2)&amp;=(m+a-1)f_m(n+1)+mf_m(n),(n\geq 1).\end{align*}
\end{corollary}
We now describe words counted by $f_m$.
\begin{proposition}
The number  of words of length $n-1$ over
the alphabet $\{0,1,\ldots,a-1,a,\ldots,m+a-1\}$ satisfying $\mathcal P_1$ is the value of $f_m(n)$.
\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&gt;2$. Consider a word of length $n+1$. At the front of such a word,
 we insert a letter different from the first letter of the word. In this way,
  we obtain all the words of length $n+2$ beginning with two different letters.
   The remaining words must begin with two identical 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, the value of $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 the following result.
\begin{proposition}  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 which satisfy
$\mathcal P_1$ equals the value of $c_m(n,k)$.
\end{proposition}
We next derive an explicit formula for $c_1(n,k)$.
\begin{proposition}\label{c1nk} We have
\begin{align*}c_1(n,n)&amp;=1,\\c_1(n,k)&amp;=\sum_{i=0}^{k-1}a^{k-i}(a-1)^{n-2k+i}{k\choose i}{n-k-1\choose k-i-1},(k&lt;n).\end{align*}
\end{proposition}
\begin{proof}
From (\ref{cmnk}), we first obtain $c_1(n,n)=1$. Assume that $k&lt;n$. Since at most $k-1$ of
 $i_t,(t=1,2,\ldots,k)$  may equal $1$, then
\begin{align*}c_1(n,k)&amp;=\sum_{i=0}^{k-1}{k\choose i}\sum_{j_1+j_2+\cdots+j_{k-i}=n-i}f_0(j_1)f_0(j_2)\cdots f_0(j_{k-i})\\
&amp;=\sum_{i=0}^{k-1}{k\choose i}a^{k-i}(a-1)^{n-2k+i}\sum_{j_1+j_2+\cdots+j_{k-i}=n-i}1,\end{align*}
where the last sum is taken over $j_t\geq 2$. Then we have
\begin{equation}\label{c1nk1}c_1(n,k)=\sum_{i=0}^{k-1}a^{k-i}(a-1)^{n-2k+i}{k\choose i}{n-k-1\choose k-i-1}.
\end{equation}
\end{proof}
\begin{remark} In the preceding formula, terms in which  $i&lt;2k-n$ equal zero.
\end{remark}

 We use (E) to derive an explicit formula for $c_m(n,k)$.
Extracting  the term for $i=n$ yields
  \begin{equation*}c_m(n,k)=(m-1)^{n-k}{n-1\choose k-1}+\sum_{i=k}^{n-1}(m-1)^{i-k}{i-1\choose k-1}c_1(n,i).\end{equation*}
Using (\ref{c1nk1}), we obtain
\begin{equation*}c_m(n,k)=(m-1)^{n-k}{n-1\choose k-1}+\sum_{i=k}^{n-1}\sum_{j=0}^{i-1}(m-1)^{i-k}a^{i-j}(a-1)^{n-2i+j}{i\choose j}{i-1\choose k-1}{n-i-1\choose i-j-1}.
  \end{equation*}
An explicit formula for $f_m(n)$ can easily be obtained from (C).

The following arrays in~Sloane \cite{slo} are related to this type:
\seqnum{A154929}, \seqnum{A113413}, \seqnum{A054458}, \seqnum{A116412}.

\section{Type 2}
Let $a$ be a positive integer. Define $f_0$ by
\begin{align*}\label{r1}f_0(1)&amp;=1,f_0(2)=0,\\ f_0(n+2)&amp;=af_0(n),(n\geq
1).\end{align*}
\begin{proposition}\label{ll1} For $a&gt;0$, the value of $f_0(n)$ is the number of words of
 length $n-1$ over the alphabet $\{0,1,\ldots,a-1\}$ satisfying $\mathcal P_2$.
\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&gt;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}\label{r1}d(0)=1,d(1)=0, d(n)=ad(n-2),(n\geq 2),\end{equation}
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}\label{parni}
f_0(n)=\begin{cases}0,&amp;\text{ if $n=2t$};\\a^t,&amp;\text{ if $n=2t+1$}.
\end{cases}
\end{equation}
Using (B), we obtain the following result.
\begin{corollary}\label{co2}
For $m\geq 0$, we have
\begin{align*}f_m(1)&amp;=1,f_m(2)=m,\\f_m(n+2)&amp;=mf_m(n+1)+af_m(n),(n\geq 1).\end{align*}
\end{corollary}
\begin{proposition}\label{pp5}
 The value of $f_m(n)$ is the number of words of length $n-1$ over
$\{0,1,\ldots,a-1,\ldots,a+m-1\}$ which satisfy $\mathcal P_2$.
\end{proposition}
\begin{proof}
We let $d(n)$ denote the number of  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 words. If a word begins with a letter from $\{0,1,\ldots,a-1\}$, the second  letter must be the same.  Hence, there are $ad(n-1)$ such words. We conclude that next $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 the Fibonacci, the Pell, and the Jacobhstal numbers.
  \begin{enumerate}
\item The case  $a=1,m=1$ is related to 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$ is related to 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$ is related to 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} We have
\begin{equation}\label{mmnn}f_m(n)=\sum_{j=0}^{\lfloor\frac {n-1}{2}\rfloor}m^{n-2j-1}a^{j}{n-1-j\choose j}.\end{equation}
\end{proposition}
\begin{proof} A word of length $n-1$ can contain $2j$ letters from $\{0,1,\ldots,a-1\}$, so that each letter appears in a run of even length, where
$0\leq j\leq\lfloor\frac{n-1}{2}\rfloor$.
The remaining $n-1-2j$ places are filled by letters from $\{a,a+1,\ldots,a+m-1\}$ arbitrarily. For a fixed $j$, we have $a^j\cdot{n-j-1\choose j}$ subwords from
 $\{0,1,\ldots,a-1\}$ and $m^{n-1-2j}$ subwords from $\{a,a+1,\ldots,a+m-1\}$. Summing over $j$, we obtain  (\ref{mmnn}).
     \end{proof}
As a consequence, we obtain the following explicit formulas for the Fibonacci, the Pell, and the Jacobsthal numbers:
\begin{gather*}F_n=\sum_{j=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}{n-j-1\choose j},\quad  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 the following result.
\begin{proposition}
The value of $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 which satisfy $\mathcal P_2$.
\end{proposition}
We now derive an explicit formula  for $c_1(n,k)$.
\begin{proposition}\label{plr} The following formula holds:
\begin{equation*}c_1(n,k)=\begin{cases}a^{\frac{n-k}{2}}{\frac{n+k}{2}-1\choose k-1},&amp;\text{ if $n-k$ is even};\\0,&amp;\text{ if $n-k$ is odd.}\end{cases}
\end{equation*}
\end{proposition}
\begin{proof}
According to (\ref{parni}), each term in formula (\ref{cmnk}) equals zero if some $i_t$ is even. Hence, (\ref{cmnk}) becomes
\begin{align*}c_1(n,k)&amp;=\sum_{2j_1+1+2j_2+1+\cdots+2j_k+1=n}a^{j_1}\cdot a^{j_2}\cdots a^{j_k}\\&amp;=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{align*}
Note that the last sum is over positive integers $s_1,s_2,\ldots,s_k$.
\end{proof}
As a consequence of (D), we obtain the following explicit formulas for the Fibonacci and the 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*}
Now, we derive an explicit formula for $c_2(2n,k)$.
Using (E), we obtain
\begin{align*}c_2(2n,k)&amp;=\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)\\
&amp;=\sum_{j=\lceil\frac k2\rceil}^{n}a^{n-j}{2j-1\choose k-1}{n+j-1\choose n-j}.
\end{align*}
Furthermore,
\begin{align*}c_2(2n-1,k)&amp;=\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)\\
&amp;=\sum_{j=\lceil\frac {k+1}{2}\rceil}^{n}a^{n-j}{2j-2\choose k-1}{n+j-2\choose n-j}.
\end{align*}
In particular, for $a=1$, we obtain the following formulas for the Pell numbers:
\begin{equation*}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{equation*}
\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 to this type:
\seqnum{A000129}, \seqnum{A001045}, \seqnum{A168561}, \seqnum{A037027}, \seqnum{A054456}, \seqnum{A132964}, \seqnum{A073370}.

\section{Type 3}
 Let $a&gt;b&gt;0$ be integers. We define $f_0$ by \begin{equation*}\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{equation*}
\begin{proposition}
 The value of $f_0(n)$
is the number of words of length $n-1$ over $\{0,1,\ldots,a\}$
satisfying $\mathcal P_3$.
\end{proposition}
\begin{proof} We let $d(n)$ denote the number of  words of length $n-1$. Since only the empty word has length $0$, we have $d(0)=1$. Since there are no restrictions on words of length $1$, we have $d(1)=a$. Assume that $n&gt;1$. We have $a\cdot d(n-1)$  words beginning with an arbitrary letter. From this number, we must subtract the number of words which begin with subwords $0i,(i=1,2,\ldots,b)$.
Hence, $d(n)$ satisfies the same recurrence as $f_0(n)$ does.
\end{proof}
\begin{example}
\begin{enumerate}
\item
If $a=2,b=1$, we have
\begin{equation*}f_0(1)=1,f_0(2)=2,f_0(n+2)=2f_0(n+1)-f_0(n),(n\geq 1),\end{equation*}
which yields  $f_0(n)=n$. Hence, $n$ is the number of binary words of length $n-1$
 avoiding $01$, for obvious reasons.
\item If $a=3,b=1$, we have the well-known recurrence for the Fibonacci numbers $F_{2n}$:
    \begin{equation*}f_0(1)=1,f_0(2)=3,f_0(n+2)=3f_0(n+1)-f_0(n),(n\geq 1).\end{equation*}
\end{enumerate}
\end{example}
 Thus, we obtain the following combinatorial interpretation of the bisection of the Fibonacci numbers.
\begin{corollary}
The number of ternary words of length $n-1$ avoiding $01$ is $F_{2n}$.
\end{corollary}
We now consider the case when $a=b+1$.
\begin{corollary}
If $b&gt;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$. Furthermore,
\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 the following result.
\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{equation*}
\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{equation*}
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 value of $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  $k-1$  letters equal $m+a-1$
which  satisfy $\mathcal P_3$.
\item The value of $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\}$ which satisfy $\mathcal P_3$.
\end{enumerate}
\end{corollary}
Next, we 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$.
\begin{proposition}\label{p10} The following equality 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$ with $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,(t=1,2,\ldots,k)$ are positive integers.
\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 to this type:
\seqnum{A078812}, \seqnum{A125662}, \seqnum{A207823}, \seqnum{A207824}, \seqnum{A110441}, \seqnum{A116414}.

\section{Type 4}
 We solve the problem for binary words  first.
\begin{proposition}Let $f_0(n)$ be the number of binary words of length $n-1$ satisfying $\mathcal P_4$. Then,
\begin{align*}
 f_0(1)&amp;=1,f_0(2)=0,\\f_0(n+2)&amp;=f_0(n+1)+f_0(n),(n&gt;1),\\
 f_0(n)&amp;=F_{n-2},(n&gt;1).
\end{align*}
\end{proposition}
\begin{proof}
  We have $f_0(1)=1$, since only the empty word has length $0$. Next, $f_0(2)=0$, since no words of length $1$ satisfy $\mathcal P_4$. Also, $f_0(3)=1$, since $10$ is the only word of length $2$ satisfying $\mathcal P_4$.
 Next, $f_0(4)=1$, since $100$ is the only word of length $3$ which satisfies $\mathcal P_4$. Assume that $n&gt;1$. Then,
    \begin{equation*}f_0(n+4)=f_0(n+2)+f_0(n+1)+\cdots,\end{equation*}
    since the 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  equalities, 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 value of $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 P_4$.
\item  The value of $f_m(n)$ is the number of words of length $n-1$ over
the alphabet $\{0,1,\ldots,m+1\}$ which  satisfy $\mathcal P_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&gt;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) implies
\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}
 Let $X$ denote $\sum_{i=1}^\infty F_{i-1}x^i$.
 We expand the  expression $Y^k$, where $Y=\sum_{i=1}^\infty F_{i-2}x^i.$
Since $F_{-1}=1$, we have  $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 is $\sum_{i=1}^k{k\choose i}\overline{c}_2(n-k,i)$.
\begin{proposition}\label{p16} We have
\begin{align*}c_1(n,n)&amp;=1,\\
c_1(n,k)&amp;=\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&gt;k).\end{align*}
\end{proposition}
Using (B), we easily obtain
\begin{align*}f_m(1)&amp;=1,f_m(2)=m,\\f_m(n+2)&amp;=(m+1)f_m(n+1)-(m-1)f_m(n).\end{align*}
We examine two particular cases.
In the case $m=1$, we obtain
\begin{align*}f_1(1)&amp;=1,f_1(2)=1,\\f_1(n+2)&amp;=2f_1(n+1),(n&gt;1),\end{align*}
which implies
\begin{gather*}f_1(1)=f_1(2)=1,f_1(n)=2^{n-2},(n&gt;2).\end{gather*}
 Thus we 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$  which
satisfy $\mathcal P_4$.
\end{corollary}
As a consequence, the following Euler-type identity holds.
\begin{identity} For $n&gt;2$, the number of binary words of length $n-2$ equals 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&gt;2).\end{equation*}
\end{identity}
We now consider the  case $m=2$. We have
\begin{align*}f_2(1)&amp;=1,f_2(2)=2,\\f_2(n+2)&amp;=3f_2(n+1)-f_2(n),\end{align*} which is the recurrence for the Fibonacci numbers $F_{2n-1}$.
\begin{corollary}
The number $F_{2n-1}$ is the number of quaternary words of length $n-1$ which
 satisfy $\mathcal P_4$.
\end{corollary}
Calculating values for $c_2(n,k)$, we obtain a peculiar 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 to this type:
\seqnum{A105422}, \seqnum{A105306}, \seqnum{A062110}, \seqnum{A188137}.

\section{Type 5}
 Again, we  consider binary words first.
 \begin{proposition} The following recurrence holds:
 \begin{align*}f_0(1)&amp;=1,f_0(2)=0,f_0(3)=1,\\
 f_0(n+3)&amp;=f_0(n+1)+f_0(n),(n\geq 1).\end{align*}
 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 satisfied.
A word of length $n+2$ begins with either two zeros or three ones and
the recurrence  follows.

Since we have a 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 of lengths divisible by  $3$. This is equivalent to the fact
that the Padovan numbers count the compositions into parts $2$ and $3$ (see the comment in \seqnum{A000931}).
\begin{corollary}\label{fib}
\begin{enumerate}
\item
 The function $f_m$ satisfies
\begin{align*}f_m(1)&amp;=1,f_m(2)=m,f_m(3)=m^2+1,\\f_m(n+3)&amp;=mf_m(n+2)+f_m(n+1)+f_m(n),(n&gt;1).
\end{align*}
\item  The value $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 P_5$.
\item  The value $f_m(n)$ is the number of words of length $n-1$ over $\{0,1,\ldots,m+1\}$
which  satisfy $\mathcal P_5$.
\end{enumerate}
\end{corollary}
\begin{proof}
 Claim 1  follows from (A) easily.
Claims 2 and 3 follow from (F) and (D).

We add a short combinatorial proof of 2.
Equality $f_m(1)=1$ means that the empty word satisfies $\mathcal P_5$. Furthermore, $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&gt;2$ may begin with any letter from  $\{2,3,\ldots,m+1\}$,
 or with $00$, or with $111$.
\end{proof}
The case $m=1$ in Corollary \ref{fib} is the recurrence for Tribonacci numbers.
\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, the Tribonacci numbers count ternary words satisfying $\mathcal P_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}$, and
  \begin{align*}\overline{f}_1(1)&amp;=0,\overline{f}_1(2)=1,\overline{f}_1(3)=1,\\
 \overline{f}_1(n+3)&amp;=\overline{f}_0(n+1)+\overline{f}_0(n).\end{align*}
This implies that $\overline{f}_1(n)=f_0(n-1),(n&gt;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 implies \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 (\ref{jjj})  implies
\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 the following result.
\begin{proposition} The following formulas hold:
\begin{align*}c_1(n,n)&amp;=1,\\c_1(n,k)&amp;=\sum_{i=0}^k\sum_{j=i}^{n-k}{k\choose i}{j-1\choose i-1}{j\choose n-k-2j},(k&lt;n).\end{align*}
\end{proposition}
In particular, we have the following identity for the Tribonacci numbers.

\begin{identity}
\begin{equation*} T_n=1+\sum_{k=1}^{n-1}\sum_{i=0}^k\sum_{j=i}^{n-k}{k\choose i}{j-1\choose i-1}{j\choose n-k-2j}.\end{equation*}
\end{identity}
\begin{remark} Using (E) and  (D), we  obtain explicit formulas  for $c_m(n,k)$ and $f_m(n)$.
\end{remark}
The following arrays in~Sloane \cite{slo} are related to this type:
\seqnum{A104578}, \seqnum{A104580}.

\section{Acknowledgment} I would like to thank the referee for a very careful reading of the manuscript and several useful suggestions.
\begin{thebibliography}{9}

\bibitem{bir} D. Birmajer, J. B. Gil, and M. D. Weiner, On the enumeration of restricted words over a finite alphabet, {\it J. Integer Sequences} {\bf 19} (2016),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL19/Gil/gil6.html}{Article 16.1.3}.

\bibitem{ja1}M. Janji\'c, On linear recurrence equation arising from compositions of positive integers, {\it J. Integer Sequences} {\bf 18} (2015),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL18/Janjic/janjic63.html}{Article 15.4.7}.

\bibitem{ja2} M. Janji\'c, Binomial coefficients and enumeration of restricted words,
{\it J. Integer Sequences} {\bf 19} (2016),
\href{https//cs.uwaterlo.ca.journals/JIS/VOL19/Janjic/janjic73.html}{Article 16.7.3}.

\bibitem{ja3} M. Janji\'c, Some formulas for numbers of restricted words, {\it  J. Integer Sequences} {\bf 20} (2017),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL20/Janjic/janjic83.html}{Article 17.6.5}.

\bibitem{slo}  N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences,
\url{https://oeis.org}.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: Primary
05A10; Secondary 11B39.

\noindent \emph{Keywords:}
restricted word, linear recurrence equation,  Fibonacci number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences:
\seqnum{A000129},
\seqnum{A000931},
\seqnum{A001045},
\seqnum{A037027},
\seqnum{A054456},
\seqnum{A054458},
\seqnum{A062110},
\seqnum{A073370},
\seqnum{A078812},
\seqnum{A104578},
\seqnum{A104580},
\seqnum{A105306},
\seqnum{A105422},
\seqnum{A110441},
\seqnum{A113413},
\seqnum{A116412},
\seqnum{A116414},
\seqnum{A125662},
\seqnum{A132964},
\seqnum{A154929},
\seqnum{A168561},
\seqnum{A188137},
\seqnum{A207823}, and
\seqnum{A207824}.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  July 26 2017;
revised versions received  November 30 2017; December 24 2017;
December 25 2017.
Published in {\it Journal of Integer Sequences},
January 21 2018.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                


</pre></body></html>