\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
 Some Formulas for Numbers\\
 \vskip .12in
  of  Restricted Words}
\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}
For an arithmetic function $f_0$,
we consider the number $c_m(n,k)$ of  weighted compositions of $n$
into $k$ parts, where the weights are the values of the
$(m-1)^{\text{th}}$ invert transform of $f_0$. We connect  $c_m(n,k)$
with $c_{1}(n,k)$ via Pascal matrices. We then  relate $c_m(n,k)$ to
the number of certain restricted words over a finite alphabet. In
addition, we develop a method which transfers some properties of
restricted words over a finite alphabet to  words over a larger
alphabet.


Several examples illustrate our findings. Some examples concern
binomial coefficients and  Fibonacci numbers.  Some examples also
extend the classical results about weighted compositions of Hoggatt and
Lind. In each example, we derive an explicit formula for $c_m(n,k)$.
\end{abstract}

\section{Introduction}
   For a given initial arithmetic function $f_0$, Janji\'c~\cite{ja1} examined some properties of the function $f_m$, which is the $m^{\text{th}}$ invert transform of $f_0$. In that paper, as well as in Birmajer et al.~\cite{bir2}, some cases in which $f_m$ counts the number of restricted words over a finite alphabet were considered. In the present paper, we consider the function $c_m(n,k)$, which is the number of weighted compositions of $n$ into $k$ parts, where the weights are $\{f_{m-1}(1),f_{m-1}(2),\ldots\}$.
 Note that, in Janji\'c~\cite{ja2}, properties of $c_1(n,k)$ were investigated.

 As mentioned by Birmajer at al. in a recent preprint~\cite{bir3}, a formula for the number $c_1(n,k)$ was firstly  given by Hoggatt and Lind~\cite{hh}, based on results by Moser and Whitney~\cite{mw}.
 For a sequence of weights $\{f_{m-1}(1),f_{m-1}(2),\ldots\}$,
 the number of $f_{m-1}$-weighted compositions of $n$ into $k$ parts is
 \begin{equation*}c_m(n,k)=\sum_{\pi_k(n)}\frac{k!}{k_1!\cdots k_n!}f_{m-1}(1)^{k_1}\cdots f_{m-1}(1)^{k_n},\end{equation*}
where the sum runs over all solutions of
\begin{equation*}k_1+2k_2+\cdots+nk_n=n \text{ such that }k_1+\cdots+k_n=k \text{ and }k_j\in \mathbb N_0\text{ for all }j.\end{equation*}
In other words,
\begin{equation}\label{bpp}c_m(n,k)=\frac{k!}{n!}B_{n,k}(1!f_{m-1}(1),2!f_{m-1}(2),\ldots),\end{equation}
where $B_{n,k}(x_1,x_2,\ldots)$ is the Bell partial polynomial.
Moreover, as discussed in Hoggatt and Lind~\cite{hh}, this formula is equivalent to
\begin{equation}\label{kur}c_m(n,k)=\sum_{\gamma_k(n)}f_{m-1}(a_1)\cdots f_{m-1}(a_k),\end{equation}
where $\gamma_k(n)$ indicates summations over $k$-part compositions $a_1+a_2+\cdots+a_k$ of $n$.
As an immediate consequence, we obtain the following two results:
\begin{corollary}
The function $c_m(n,k)$ satisfies the recurrence
\begin{equation*}c_m(0,0)=1,\;c_m(n,0)=0,(n>1),\end{equation*} and \begin{equation}\label{e2}c_m(n,k)=\sum_{i=1}^{n-k+1}f_{m-1}(i)c_m(n-i,k-1),(1\leq k\leq
n).\end{equation}
\end{corollary}
\begin{corollary}
The following formula holds:
\begin{equation}\label{suma}f_m(n)=\sum_{k=1}^nc_m(n,k).\end{equation}
\end{corollary}
Note that, throughout the  paper, letters $m,n,k$ will have the meaning as in the definition of $c_m(n,k)$.  Using Birmajer et al.~\cite[Corollary 10]{bir1}, we  derive a formula connecting $c_m(n,k)$ with $c_{m-1}(n,k)$. The formula may be written in terms of the lower triangular Pascal matrices.  We then  extend this result to obtain a relation between $c_m(n,k)$ and $c_1(n,k)$.

 For the particular case $f_0(1)=1$, we develop a method which allows us to derive an interpretation of $c_m(n,k)$ in terms of restricted words, when we know the number of restricted words counted by $f_{m-1}$.
 We finish the paper with a number of examples illustrating our results.
Some examples extend the classical results on weighted compositions given by Hoggatt and Lind~\cite{hh}.


It is important to note that quantities $f_m(n)$ and $c_m(n,k)$ depend only on the initial arithmetic function $f_0$.
\section{A connection of  $c_m(n,k)$ and $c_{m-1}(n,k)$}
Let $C_m(n)$ be the lower triangular matrix of order $n$, whose $(i,j)$ entry is $c_m(i,j),(i=1,2,\ldots,n;1\leq j\leq i)$. We let $L_n$ denote the lower triangular Pascal matrix of order $n$. Hence, the  $(i,j)$ entry of $L_n$ is ${i-1\choose j-1},(1\leq j\leq i)$. First, we prove the following:
\begin{proposition} For each $m>1$, we have
\begin{equation*}C_m(n)=C_{m-1}(n)\cdot L_n.\end{equation*}
\end{proposition}
\begin{proof}
 It is easy to see that the statement  is equivalent to the  equation
\begin{equation}\label{cmk}c_m(n,k)=\sum_{i=k}^n{i-1\choose k-1}c_{m-1}(n,i).\end{equation}
In our terminology, Birmajer et al.~\cite[Corollary 10]{bir1} may be written in the form
\begin{equation*}\sum_{j_1+j_2+\cdots+j_k=n}f_{m-1}(j_1)\cdots f_{m-1}(j_k)=\sum_{i=1}^n{i+k-1\choose
i}c_{m-1}(n,i),\end{equation*} where the sum is taken over nonnegative $j_1,\ldots,j_k$. Since at most $k-1$ of $j_t$ may be equal $0$, \eqref{kur} yields
\begin{equation*}\sum_{j=0}^{k-1}{k\choose j}c_m(n,k-j)=\sum_{i=1}^n{i+k-1\choose i}c_{m-1}(n,i).\end{equation*}
Replacing $k-j$ by $t$, and denoting $\sum_{i=1}^n{i+k-1\choose i}c_{m-1}(n,i)=a_k$, implies
\begin{equation*}\sum_{t=1}^{k}{k\choose t}c_m(n,t)=a_k,(k=1,2,\ldots,n).\end{equation*}

Denoting $X=(c_m(n,1),c_m(n,2),\ldots,c_m(n,n))^T$, and $A=(a_1,a_2,\ldots,a_n)^T$, this system may be written in the matrix form \begin{equation*}Q\cdot X=A,\end{equation*} where $Q$ is obtained from the Pascal matrix $L_{n+1}$ by omitting the first row and the first column. It follows that $X=Q^{-1}\cdot A$, where $Q^{-1}=\left((-1)^{i+j}{i\choose j}\right)_{n\times n}.$
For $k=1,2,\ldots,n$, we obtain \begin{equation}\label{b2}c_m(n,k)=\sum_{i=1}^n\left(\sum_{j=1}^n(-1)^{j+k}{k\choose
j}{i+j-1\choose i}\right)c_{m-1}(n,i). \end{equation}
Equation \eqref{b2} holds for each $m> 1$, as well as  for any arbitrary arithmetic function $f_0$. In particular, taking  $f_0(1)=1,f_0(i)=0,(i>1)$, we obviously have  $c_1(n,n)=1$, and $c_1(n,k)=0$ for $k<n$. Also, $f_1(n)=1$ for all $n$.
In this case, $c_2(n,k)$ is the number of compositions of $n$ into $k$ parts, that is,
$c_2(n,k)={n-1\choose k-1}$. Therefore,  \eqref{b2} becomes
\begin{equation}\label{id}{n-1\choose k-1}=\sum_{j=1}^n(-1)^{j+k}{k\choose j}{n+j-1\choose n}.\end{equation}
 Hence the expression in the square brackets in  \eqref{b2} equals ${i-1\choose k-1}$, which proves \eqref{cmk}.
\end{proof}
\begin{remark} As a byproduct, we proved the binomial identity (\ref{id}).
\end{remark}
\begin{remark}
Replacing $i-k$ by $t$ in \eqref{cmk}, we obtain
\begin{equation}\label{ekf}c_m(n,k)=\sum_{t=0}^{n-k}{k+t-1\choose
t}c_{m-1}(n,k+t).\end{equation}
\end{remark}
From the equation $C_m(n)=C_{m-1}(n)\cdot L_n$ follows
\begin{equation*}C_m(n)=C_{m-1}(n)\cdot L_n=C_{m-2}(n)\cdot L_n^2=\cdots=C_1(n)\cdot L_n^{m-1}.\end{equation*}
We thus obtain,
\begin{proposition}\label{vv} The following matrix equation holds: \begin{equation*}C_m(n)=C_1(n)L_n^{m-1}.\end{equation*}
 Or, explicitly,
\begin{equation}\label{e3}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}
\end{proposition}
\begin{proof} The assertion is true since $(i,k)$ entry of $L_n^{m-1}$ is $(m-1)^{i-k}{i-1\choose k-1}$.
\end{proof}
Now, we  derive a formula in which $f_m(n)$ is expressed in terms of $c_1(n,k)$.
\begin{proposition}
The following formula holds:
\begin{equation}\label{fmn1}f_m(n)=\sum_{i=1}^n m^{i-1}c_1(n,i).\end{equation}
\end{proposition}
\begin{proof}
Equation~\eqref{suma} yields
\begin{equation*}f_m(n)=\sum_{k=1}^n\sum_{i=k}^n(m-1)^{i-k}{i-1\choose k-1}c_1(n,i).\end{equation*}
Changing the order of summation gives
\begin{equation*}f_m(n)=\sum_{i=1}^n\left(\sum_{k=1}^i(m-1)^{i-k}{i-1\choose k-1}\right)c_1(n,i).\end{equation*}
Using the binomial theorem, we obtain \eqref{fmn1}.
\end{proof}
\begin{note}
Equation~\eqref{fmn1} appears in Birmajer et al.~\cite{bir2} with a combinatorial proof based on the enumeration of certain restricted words.
\end{note}
As an immediate consequence of \eqref{bpp} and \eqref{e3}, we obtain the following identity for the partial Bell polynomials:
\begin{identity}
If the sequence $y_1,y_2,\ldots$ is the invert transform of the sequence $x_1,x_2,\ldots$,
then
\begin{equation*}k!B_{n,k}(y_1,2!\cdot y_2,3!\cdot y_3,\ldots)=\sum_{i=k}^n{i-1\choose
k-1}i!B_{n,i}( x_1,2!\cdot x_2,3!\cdot x_3, \ldots).\end{equation*}
\end{identity}
We next prove the following result.
\begin{proposition}\label{hr}
 Assume that $f_{0}(1)=1$ and $m>1$. Assume next  that, for $n\geq 1$, $f_{m-1}(n)$
is the number of some 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 exactly $k-1$  letters equal $x$.
\end{proposition}
\begin{proof}
Since $f_0(1)=1$, it follows from Janji\'c~\cite[Corollary 2]{ja1}  that $f_{m-1}(1)=1$.
We use induction on $k$. For $k=1$, \eqref{kur} yields $c_m(n,1)=f_{m-1}(n).$
Since $f_{m-1}(n)$ is the number of  words of length $n-1$ over $\alpha$ not containing $x$, we conclude that the statement is true for $k=1$.
 Assume that the claim is true for $k-1$. Consider the first term $f_{m-1}(1)c_m(n-1,k-1)$ in \eqref{e2}.  By the induction hypothesis, $c_{m}(n-1,k-1)$ is the number of  words of length $n-2$ having $k-2$ letters equal to $x$. Adding $x$ at the beginning of each such word, we obtain all the words of length $n-1$ over $\alpha\cup\{x\}$,  having $k-1$ letters equal to  $x$, and all beginning with $x$.

Consider now the term $f_{m-1}(i)\cdot c_m(n-i,k-1),(i>1)$ in \eqref{e2}.
 By the induction hypothesis, $c_m(n-i,k-1)$ is the number of words of  length $n-i-1$ with $k-2$ letters equal to $x$. We first insert $x$ at the beginning of each such word.  In front of $x$, we insert an arbitrary word of length $i-1$ over $\alpha$, which are $f_{m-1}(i)$ in number. We thus obtain all words of length $n-1$ over $\alpha\cup\{x\}$, such that the first appearance of $x$ is at the $i$th  position.
 It follows that the right-hand side of \eqref{e2} counts all the desired words.
\end{proof}
\begin{remark}We stress the fact that the preceding method may be applied only when we know the number of $(n-1)$-length words counted by $f_{m-1}(n)$.
This is always true when  $f_0(1),f_0(2),\ldots$ is a binary  sequence.
Namely, there is a bijection between the compositions counted by $c_1(n,k)$ and the binary words of length $n-1$ with $k-1$ ones.
 This bijection is given by the correspondence
\begin{equation}\label{kor}1\to 1,2\to 10,3\to 100,\ldots \ .\end{equation}
In this way, the compositions of $n$ into $k$ parts designate binary words of length $n$ and  having $k$ ones, all of which begin with $1$. The converse  is also true. Omitting the leading $1$, we obtain the desired correspondence. Equation (\ref{suma}) implies that $f_1$ and $c_1(n,k)$ both count some binary words of length $n-1$. We thus may apply Proposition \ref{hr} to obtain a combinatorial interpretation of $c_m(n,k)$ as well as $f_m(n)$. Note that this method may be applied in non-binary cases also.
\end{remark}
\begin{remark}
\leavevmode
 \begin{enumerate}
\item
Janji\'c~\cite{ja1,ja2} derive several formulas concerning correspondence (\ref{kor}).
\item
Also, Birmajer at al.~\cite[Theorem 3, Corollary 5]{bir2} developed a method to obtain the words counted by $f_{m-1}$ starting with the initial function $f_0$.
\end{enumerate}
\end{remark}
We now illustrate our method by a simple example.
\begin{example}
Assume that $f_0(i)=1$ for $i=1,2,\ldots$. Then, we have $f_{m-1}(n)=m^{n-1}$.
It yields that $f_{m-1}(n)$ is the number of all words of length $n-1$ over $\alpha=\{0,1,\ldots,m-1\}$. Then, $c_1(n,k)={n-1\choose k-1}.$
This means that $C_1(n)=L_n$. It follows that  $C_m(n)=L_n^m.$
From the well-known formula for the terms of $L_n^m$, we obtain
\begin{equation}\label{bu}c_m(n,k)=m^{n-k}{n-1\choose k-1}.\end{equation}
Equation~\eqref{bu} is in accordance with Proposition \ref{hr}. Namely, according to Proposition \ref{hr},  $c_m(n,k)$ is the number of words of length $n-1$ over $\{0,1,\ldots,m\}$ with $k-1$ letters equal to $m$. These $k-1$ letters may be chosen in ${n-1\choose k-1}$ ways. The remaining letters may be arbitrary letters from $\{0,1,\ldots,m-1\}$, which are   $m^{n-k}$ in number.

As a byproduct, using \eqref{e3}, we obtain the following binomial identity:
\begin{identity}
For $m>1$, we have
\begin{equation}\label{cp}m^{n-k}{n-1\choose k-1}=\sum_{j=0}^{n-k}(m-1)^{j}{n-1\choose k+j-1}{k+j-1\choose j}.\end{equation}
\end{identity}
This simple case is related  to the coefficients of the  Tchebychev polynomials $U_n(x)$ of the second kind.
\begin{corollary}
  The  number $\vert[x^{n-k}](U_{n+k-2}(x))\vert$ is the number of words of length $n-1$ over the alphabet $\{0,1,2\}$ having $k-1$ twos.
\end{corollary}
\begin{proof}
 It is a well known that  $(-1)^k2^{n-k}{n-1\choose k-1}$ is the coefficient of $U_{n+k-2}(x)$ by $x^{n-k}$. We thus obtain
 \begin{equation*}[x^{n-k}](U_{n+k-2}(x))=(-1)^{n-k}\sum_{j=0}^{n-k}{n-1\choose k+j-1}{k+j-1\choose j}.\end{equation*}
This is the case when $m=2$ in \eqref{cp}.
\end{proof}
\end{example}
\section{More examples}
Firstly, we revise the result from Janji\'c~\cite[Corollary 9]{ja2}.
\begin{example}\label{ex1}
We define $f_0(1)=f_0(2)=1$, and $f_0(n)=0$ otherwise. According to Janji\'c~\cite[Corollary 33]{ja1}, $f_{m-1}(n)$ is the number of words of length $n-1$ over the alphabet $\{0,1,\ldots,m-1\}$ having all zeros isolated.
\begin{corollary} The number $c_m(n,k)$ is the number of words of length $n-1$ over the alphabet $\{0,1,\ldots,m\}$, which have $k-1$ letters equal to $m$ and all zeros isolated.
Also,
\begin{equation*}c_1(n,k)={k\choose n-k},\] and
\[c_m(n,k)=\sum_{j=\lceil\frac{n}{2}\rceil-k}^{n-k}(m-1)^{j}{j+k-1\choose
k-1}{j+k\choose n-j-k},\left(m>1,\left\lceil\frac{n}{2}\right\rceil\geq k\right).\end{equation*}
\end{corollary}
\begin{proof}
The first formula is Hoggatt and Lind~\cite[Case (ii)]{hh}.
Since $c_1(n,k+j)={k+j\choose n-k-j},(j=0,\ldots,n-k)$, we have $k+j\geq n-k-j$, which yields $2j\geq n-2k$ and $n\geq 2k$.
The second formula is true according  to \eqref{e3}.
\end{proof}
The  arrays \seqnum{A030528} and \seqnum{A154929} in Sloane~\cite{slo} are related to  Example \ref{ex1}.
\end{example}
Next, we reexamine the result in Janji\'c~\cite[Corollary 28]{ja1}.
\begin{example}\label{ex2}
We define $f_0(n)=1$ when $n$ is odd, and $f_0(n)=0$ otherwise.
According to Janji\'c~\cite[Corollary 28]{ja1}, $f_{m-1}(n)$  is the number of words of length $n-1$ over the alphabet $\{0,1,\ldots,m-1\}$, avoiding runs of zeros of odd lengths.
From Janji\'c~\cite[Proposition 24]{ja2}, it follows that
\begin{equation*}c_1(n,k)=\begin{cases}{\frac{n-k}{2}+k-1\choose k-1},&\text{ if $n-k$ is even};\\
0,&\text{ if $n$ is odd}.\end{cases}\end{equation*}

The number $c_1(n,k)$ is the number of  binary words of length $n-1$ with $k-1$ ones, and avoiding runs of zeros of odd lengths. This follows from bijection (\ref{kor}).
 We add a short combinatorial proof.
\begin{proposition} The number  $c_1(n,k)$ is the number of
binary words of length $n-1$ with $k-1$ ones, avoiding runs of zeros of odd lengths.
\end{proposition}
 \begin{proof} Assume that  $n$ and $k$ are of different parities.
  Since a word of length $n-1$ with $k-1$ ones must have $n-k$ zeros, and since  $n-k$ is odd,  we conclude that such a word must have an odd run of zeros. It follows that $c_1(n,k)=0$. If $n$ and $k$ are of the same parity, then $n-k$ is even. This means that there are $\frac{n-k}{2}$ pairs of zeros. Of these $\frac{n-k}{2}$ pairs and $k-1$ ones, we may form ${\frac{n-k}{2}+k-1\choose k-1}$ words of length $n-1$ having $k-1$ ones and avoiding runs of zeros of odd lengths.
 \end{proof}
 \begin{remark} The formula for $c_1(n,k)$  appears in Hoggatt and Lind~\cite[Case (iv)]{hh}.
 \end{remark}
 Using induction and Proposition \ref{hr}, we obtain
 \begin{corollary} The number  $c_m(n,k)$ is the number of words of length $n-1$ over $\{0,1,\ldots,m\}$ with $k-1$ letters equal to $m$, avoiding runs of zeros of odd lengths.
 \end{corollary}
From  \eqref{e3}, we  obtain an explicit formula for $c_m(n,k)$.

The  arrays \seqnum{A037027} and \seqnum{A054456} in Sloane~\cite{slo} are related to Example \ref{ex2}.
 \end{example}
 \begin{example}\label{ex3}
We define $f_0(i)=i,(i=1,2,\ldots)$. According to Janji\'c~\cite[Corollary 37]{ja1},
$f_{m-1}(n)$ is the number of $01$-avoiding words of length $n-1$ over the
alphabet $\{0,1,\ldots,m\}$.

Applying Proposition \ref{hr} several times, we obtain
\begin{corollary}
 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 to $m+1$ and avoiding $01$.
\end{corollary}
\begin{corollary} The following formula holds:
\begin{equation}\label{ff2}c_1(n,k)={n+k-1\choose 2k-1}.\end{equation}
Also,
\begin{equation*}c_m(n,k)=\sum_{i=k}^n(m-1)^{i-k}{i-1\choose k-1}{n+i-1\choose 2i-1}.\end{equation*}
\end{corollary}
\begin{proof} Formula (\ref{ff2})  may be found in Hoggatt and Lind~\cite[Case (iii)]{hh}.
\end{proof}
Since ${n+k-1\choose 2k-1}$ is obviously the number of binary words of length $n+k-1$ with $2k-1$ zeros, we obtain the following Euler-type identity:
\begin{identity}
The number of binary words of length $n+k-1$ with $2k-1$ zeros  equals the number of ternary words of length $n-1$, having $k-1$ letters equal to $2$ and avoiding $01$.
\end{identity}
The  arrays \seqnum{A125662},  \seqnum{A207823}, and \seqnum{A207824} in Sloane~\cite{slo} are related to  Example \ref{ex3}.
\end{example}
The last two examples concern the case $f_0(1)=0$. Note that in these examples, Proposition \ref{hr} can not be used. The first example is an extension of the result from Janji\'c~\cite[Proposition 13]{ja2}.
\begin{example}\label{ex4}
  We define $f_0(1)=0$, and $f_0(n)=1$ otherwise.
  It follows from Janji\'c~\cite[Corollary 24]{ja1} that, for $n>3$,  $f_m(n)$ is the number of words of length $n-3$ over $\{0,1,\ldots,m\}$, where no two consecutive letters are nonzero. From Janji\'c~\cite[Proposition 13]{ja2}, we obtain $c_1(n,k)={n-k-1\choose k-1}$ for $\left(1\leq k\leq \left\lfloor\frac{n}{2}\right\rfloor\right)$, and $c_1(n,k)=0$ otherwise. Equation~\eqref{cmk} implies that $c_m(n,k)=0$ when $k> \left\lfloor\frac{n}{2}\right\rfloor$.
 \begin{remark}
  Note that the formula for $c_1(n,k)$ also appears in Hoggatt and
  Lind~\cite[Case (iii)]{hh}.
\end{remark}

  \begin{corollary}
  For $n>3$ and $1\leq k\leq \left\lfloor\frac{n}{2}\right\rfloor$, the number  $c_m(n,k)$ is the number of words of length $n-3$ over $\{0,1,\ldots,m\}$ with $k-1$ ones, and all nonzero letters are isolated. An explicit formula for $c_m(n,k)$ is
\begin{equation*}c_m(n,k)=\sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor-k}(m-1)^{j}{j+k-1\choose
k-1}{n-k-j-1\choose k+j-1},\left(1\leq k\leq \left\lfloor\frac{n}{2}\right\rfloor\right),\end{equation*}
and $c_m(n,k)=0$ when $k>\lfloor\frac{n}{2}\rfloor$.
\end{corollary}
\begin{proof}
We know that $c_1(n,k)$ is the number of compositions of $n$ into $k$ parts, each of which is greater than $1$. Using the bijection (\ref{kor}), we conclude that, for $n>3$, $c_1(n,k)$ is the number of binary words of length $n$
 beginning with $10$, ending with $0$ and  all ones are isolated. Omitting $10$ at the beginning, and $0$ at the end of each word, we conclude that $c_1(n,k),(n>3)$ is the number of binary words of length $n-3$ with $k-1$ ones, all of which  are isolated.
Hence, the statement is true for $m=1$. Assume that the statement is true for $m-1$.
 In \eqref{ekf}, by the induction hypothesis, $c_{m-1}(n,k+t)$ is the number of words of length $n-3$ with $k+t-1$ ones, in which  all nonzero letters are isolated. Replacing $t$ ones with $m$, we obtain the desired words. The number $t$ may be chosen in ${k+t-1\choose t}$ ways. Hence,  the right-hand side of \eqref{ekf} counts all the desired words.
 The formula follows from \eqref{e3} and the fact that $n-k-j-1\geq k+j-1$.
\end{proof}
The  arrays \seqnum{A037027},  \seqnum{A249139}, and \seqnum{A006130} in Sloane~\cite{slo} are related to  Example \ref{ex4}.
\end{example}
\begin{example} Define $f_0$ in the following way: $f_0(2)=f_0(3)=1$, and $f_0(n)=0$
otherwise. Janji\'c~\cite[Proposition 5]{ja2} proved that
$c_1(n,k)={k\choose n-2k},\left( \left\lceil\frac{n}{3}\right\rceil\leq k\leq \left\lfloor\frac{n}{2}\right\rfloor\right)$
and $c_1(n,k)=0$ otherwise.

We know that $c_1(n,k)$ is the number of compositions of $n$ into $k$ parts equal to
either $2$ or $3$.
In other words, for $n\geq 3$ and  $1\leq k\leq \left\lfloor\frac{n}{2}\right\rfloor$,  $c_1(n,k)$ is the number of binary words of length $n-1$ with $k-1$  ones.
These words begin with $0$ and end with $0$. Also, zero avoids a run of length greater than $2$, and all ones are isolated.
\begin{corollary} For $n>3$, the number $c_m(n,k)$ is the number of words of length $n-1$ over the alphabet $\{0,1,\ldots,m\}$ with $k-1$ ones, which begin and end with $0$. Also, $0$ avoids  a run of length greater than $2$ and all nonzero letters are isolated.
\end{corollary}
\begin{proof}
The statement holds for $m=1$.
Assume that the statement is true for $m-1$. Consider the term
${k+t-1\choose t}c_{m-1}(n,k+t)$ in \eqref{ekf}. The number  $c_{m-1}(n,k+t)$ is the number of the desired words of length $n-1$ over $\{0,1,\ldots,m-1\}$ with $k+t-1$ ones. We replace $t$ of  $k+t-1$ ones with $m$ and then sum over $t$ to obtain $c_m(n,k)$.
\end{proof}
From \eqref{cmk} follows that $c_m(n,k)=0$ if $k>\lfloor\frac{n}{2}\rfloor$.
 Otherwise, from \eqref{e3}, we obtain
\begin{equation*}c_m(n,k)=\sum_{j=0}^{\lfloor\frac{n}{2}\rfloor}(m-1)^j{j+k-1\choose k-1}{k+j\choose n-2k-2j},\left(1\leq k\leq\left\lfloor\frac{n}{2}\right\rfloor\right).\end{equation*}
\end{example}
\section{Acknowledgment} I would like to thank the referee for a very careful reading of the manuscript and many  useful suggestions. A special thanks for providing me with historical facts about weighted compositions.
\begin{thebibliography}{9}
\bibitem{bir1} D. Birmajer, J. B. Gill, and M. D. Weiner, Linear recurrence sequences and their convolutions via Bell polynomials, {\it J. Integer Seq.} {\bf 18} (2015),
 \href{https://cs.uwaterloo.ca/journals/JIS/VOL18/Gil/gil3.html}{Article 15.1.2}.
\bibitem{bir2} D. Birmajer, J. B. Gill, and M. D. Weiner, On the enumeration of restricted words over a finite alphabet, {\it J. Integer Seq.} {\bf 19} (2016),
 \href{https://cs.uwaterloo.ca/journals/JIS/VOL19/Gil/gil6.html}{Article 16.1.3}.
\bibitem{bir3} D. Birmajer, J. B. Gill, and M. D. Weiner, Composition colored by symplicial
 polytopic numbers, preprint 2006, \url{http//arxiv.org/abs/1601.01595}.
 \bibitem{hh} V. E. Hoggatt and D. A. Lind, Fibonacci and binomial properties of weighted compositions, {\it J. Combin. Theory} {\bf 4} (1968), 121--124.
 \bibitem{ja1}M. Janji\'c, On linear recurrence equation arising from compositions of positive integers {\it J. Integer Seq.} {\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 Seq.} {\bf 19} (2016),
\href{https//cs.uwaterlo.ca.journals/JIS/VOL19/Janjic/janjic73.html}{Article 16.7.3}.
\bibitem{mw} L. Moser and E. L. Whitney, Weighted compositions, {\it Canad. Math. Bull.} {\bf 4} (1961), 39--43.
\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:}  binary word, integer composition,
restricted word, Pascal matrix.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000027},
\seqnum{A006130},
\seqnum{A030528},
\seqnum{A037027},
\seqnum{A054456},
\seqnum{A125662},
\seqnum{A154929},
\seqnum{A207823},
\seqnum{A207824}, and
\seqnum{A249139}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  October 3 2016;
revised versions received   March 26 2017; June 1 2017.
Published in {\it Journal of Integer Sequences}, June 25 2017.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                


.