<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
 Pascal Matrices and Restricted Words}
\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 examined two functions $f_m$ and $c_m$, related to the  enumeration of restricted words over a finite alphabet. The definitions of these functions depend on an initial arithmetic function $f_0$ taking nonnegative integer values. In this paper, we consider four types of initial functions,  the values of which  are  binomial coefficients.

 In particular, we give a new combinatorial interpretation of the figurate numbers.
\end{abstract}

 \section{Introduction}
 In the previous papers~\cite{ja1,ja3}, for an initial arithmetic function $f_0$ having nonnegative integer values, we defined  two functions $f_m$ and $c_m$  in the following way: The function  $f_m$ is the $m$th invert transform of $f_0$. The function $c_m(n,k)$ is defined  by
\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}
We  investigate the problem of enumeration of some words over a finite alphabet relating to these functions.
In~\cite{ja1, ja3}, a  number of results about restricted words enumeration is obtained. Since the problem may be reduced to enumeration of weighted compositions, other authors also obtained results of this kind, for instance~\cite{bir1,jma,mw}.

We first restate some results from~\cite{ja1,ja3}, necessary for the present investigation:
\begin{enumerate}
\item[(A)] The following recurrence holds:
\begin{equation*}c_m(n,k)=\sum_{i=1}^{n-k+1}f_{m-1}(i)c_{m}(n-i,k-1),\end{equation*}
In particular,
$c_m(n,1)=f_{m-1}(n).$
\item[(B)] We consider the array $c_m(n,k)$  as a lower triangular matrix of order $n$, which we denote by $C_m(n)$. If $L_n$ is the lower triangular Pascal matrix, then
\begin{equation*} C_m(n)=C_1(n)\cdot L_n^{m-1}.
\end{equation*}
In other words, we have
\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[(C)] We have \begin{equation*}f_m(n)=\sum_{k=1}^nm^{k-1}c_1(n,k)=\sum_{k=1}^nc_m(n,k).\end{equation*}
\item[(D)] The following formula is true:
\begin{equation*}
\sum_{n=k}^\infty c_m(n,k)x^n=\left(\sum_{i=1}^\infty f_{m-1}(i)x^i\right)^k.
\end{equation*}
\end{enumerate}
We consider four types of   initial functions, the values of which are  binomial coefficients.   In the first case, the values are the binomial coefficients from a row of Pascal matrix. In the second case, they are  from a column, that is,  the figurate numbers. In these cases, we describe the restricted words counted by $f_m$ and $c_m$, and derive explicit formulas for these functions.  In the third case, the values of $f_0$ are the central binomial coefficients.  In the fourth case, we take $f_0(n)={2n-1\choose n},(n\geq 1)$.
\begin{remark}
 In the last two cases, only the functions $f_1,f_2$ and $c_1$ will be investigated.
 Namely, we could not find a sequence in Sloane~\cite{slo},  generated by some of $c_m,(m&gt;1)$ or $f_m,(m&gt;2)$.
 \end{remark}

We investigate the following four types of restricted words:
  \begin{enumerate}
  \item Words in which the letters of particular subwords are arranged in increasing order.
 \item Words in which  particular subwords contain no rises.
 \item Words in which each binary subword has an equal number of ones and zeros.
 \item Words such that in each binary subword, the number of zeros exceeds the number of ones by $1$.
 \end{enumerate}
We start with an extension of~\cite[Proposition 10]{ja3}. Let $1\leq m,\;1\leq k\leq n$ be integers.  Assume  that $f_{m-1}(n)$ is the number of words $w_{n-1}$ of length $d_{m-1}(n-1)$ over the finite alphabet $\Omega$ having a property $\mathcal P$. Assume next that the empty word has the property $\mathcal P$. It follows that  $f_{m-1}(1)=1$ and $d_{m-1}(0)=0$, since the empty word is the only word of length $0$. Furthermore, let  $\Delta$ be a finite alphabet such that  $\Omega\cap\Delta=\emptyset$.

We want to count the words of the form \begin{equation}\label{xx}w_{i_1-1},x_1,w_{i_2-1},x_2,\ldots, w_{i_{k-1}-1},x_{k-1}, w_{i_k-1},\end{equation} where $i_1+i_2+\cdots+i_k=n$. Next, $x_1,x_2,\ldots,x_{k-1}$ are words over $\Delta$ having a property $\mathcal Q$, and its number is $N(k-1)$.
From (\ref{cmnk}), we obtain the following result.
\begin{proposition}\label{pr1} The value of $N(k-1)\cdot c_m(n,k)$ is the number of  words of the form (\ref{xx}) and of  length $\sum_{t=1}^kd_{m-1}(i_t-1)+k-1$.
 \end{proposition}
\begin{remark} If $\Delta$ consists of one letter, and if
 $d_{m-1}(i_t-1)=i_t-1$, for all $t$, then  Proposition \ref{pr1} becomes~\cite[Proposition 10]{ja3}.
\end{remark}
\begin{remark}  Note that, in this case, a letter from $\Delta$ may occupy any position in a word (\ref{xx}).
\end{remark}
We next consider the case when empty the word does not satisfy the property $\mathcal P$.
Hence, in sequence (\ref{xx}), there is no the empty word. We now count
the words of the form
\begin{equation}\label{xxx}w_{i_1},x_1,w_{i_2},x_2,\ldots, w_{i_{k-1}},x_{k-1}, w_{i_k},\end{equation}
where the length of $w_{i_t}$ is $d_{m-1}(i_t)&gt;0$.
We have
\begin{proposition}\label{pr2}
The value of $N(k-1)\cdot c_m(n,k)$ is the number of words of the form (\ref{xxx})
of length equal to the values of $\sum_{t=1}^kd_{m-1}(i_t)+k-1$, where $i_1+i_2+\cdots+i_k=n$.

Also, a letter $x$ from $\Delta$ may appear only in the form $w_ixw_j$, where $w_i,w_j$ are the words from $\Omega$ satisfying $\mathcal P$.
\end{proposition}

\section{Rows of  Pascal matrix}
 For a fixed positive integer $a$,  we want to count the number of  words over
   the finite  alphabet $\Omega=\{0,1,\ldots,a-1,\ldots\}$,  in which  letters  of  each subword over $\{0,1,\ldots,a-1\}$ appear in increasing order. We denote this property by $\mathcal P_1$. The values of the initial function $f_0$  are  given by the binomial coefficients from the $a$th row of the Pascal matrix. Namely, if we define $f_0$ by \begin{equation*}f_0(n)={a\choose n-1},(n=1,2,\ldots),\end{equation*} then  $f_0(n)$ is the number of words of length  $n-1$ over   $\{0,1,\ldots,a-1\}$ satisfying $\mathcal P_1$.
Since $f_0(1)=1$ and the empty word satisfies $\mathcal P_1$, we can use Proposition \ref{pr1} to obtain the following results.
\begin{proposition} Let $m,n,k,a$ be integers such that $a, m &gt;0$ and
$1\leq k\leq n$.
\begin{enumerate}
\item
 Let $\Delta$ be a finite alphabet such that  $\Omega\cap\Delta=\emptyset$. Assume that $N(k-1)$ is the number of words of length $k-1$ over $\Delta$ satisfying  a property $\mathcal Q_1$.  Then, $N(k-1)\cdot c_m(n,k)$ is the number of words of the form (\ref{xx}), and  of length $n-1$ over $\Omega\cup\Delta$.
\item
The number of words of length $n-1$ over the alphabet $\{0,1,\ldots,a-1,a,\ldots,a+m-1\}$ satisfying $\mathcal P_1$ is
 equal to $f_{m}(n)$.
\end{enumerate}
\end{proposition}
We next derive an explicit formula for $c_1(n,k)$.
\begin{proposition}\label{pb1}
For integers $a&gt;0$ and $1\leq k\leq n$, we have
\begin{equation*}c_1(n,k)={ak\choose n-k}.\end{equation*}
\end{proposition}
 \begin{proof} We use induction on $k$. From (A), we obtain $c_1(n,1)=f_0(n)$, which means that the statement holds for $k=1$. Suppose that the statement holds for $k-1,(k&gt;1)$. Using the recurrence (A) and the induction hypothesis, we obtain
\begin{equation}\label{rbk}c_1(n,k)=\sum_{i=1}^{n-k+1}{a\choose i-1}{ak-a\choose n-i-k+1},\end{equation}
and the statement follows by the Vandermonde convolution.
\end{proof}
As a consequence of (B) and (C), we obtain the following explicit formulas for  $c_m(n,k)$ and $f_m(n)$.
\begin{corollary} For integers $a&gt;0$, $m\geq 1$, and $1\leq k\leq n$, we have
\begin{equation*}c_m(n,k)=\sum_{i=k}^n(m-1)^{i-k}{i-1\choose k-1}{ia\choose n-i},
\end{equation*}
 \begin{equation*}f_m(n)=\sum_{i=1}^nm^{i-1}{ia\choose
n-i}.
\end{equation*}
\end{corollary}
We illustrate our results with several particular cases which give new combinatorial interpretations for some known sequences of integers. The
corresponding A-numbers in the
{\it On-line Encylopedia of Integer Sequences}~\cite{slo} are given at the end of each item.
\begin{example}
 \begin{enumerate}
\item For $a=2$, the binomial coefficient   ${2k\choose n-k}$
is equal to the number of ternary words of length $n-1$ having $k-1$ letters equal to $2$, and the letters of each binary subword are written in increasing order.
 \seqnum{A116088} (without the first column)
\item For $a=2$, the value of  $\sum_{k=1}^n{2k\choose n-k}$ equals the number of ternary words  of length $n-1$, in which the letters of each binary subword are  written in increasing order. \seqnum{A002478} (the bisection of the Narayana's cows sequence)
\item For $a=3$, the binomial coefficient   ${3k\choose n-k}$
is equal to the number of quaternary words of length $n-1$ having $k-1$ letters equal  $3$,
 and the letters in each ternary subword are written in increasing order.
 \seqnum{A116089}
\item For $a=3$, the value of $\sum_{k=1}^n{3k\choose n-k}$ equals the number of quaternary words in which the letters in each ternary subword are written in increasing order. \seqnum{A099234}
\item For $a=2,k=n-2,n&gt;2,\Delta=\{2,3\}$,  $2^{n-3}\cdot(2n^2-9n+10)$ is equal to  the number  quaternary words of length $n-1$, in which $n-3$ letters are either equal to $2$ or $3$, and the letters $0$ and $1$ are written in increasing order. \seqnum{A086950}
\item For $a=2,n\geq 3,k=n-2,N(k-1)=k$,   $(n-2)^2\cdot(2n-3)$ is
equal to the number of words of length $n-1$ over $\{0,1,2,\ldots,n\}$ having $n-2$ letters from $2,3,\ldots,n$ which are  written in increasing order, as are the letters in each binary subword. \seqnum{A015237}
\item For  $a=2,n\geq 3,k=n-2,N(k-1)=k!$,  $(n-2)!\cdot(2n-5)$ is equal to
the number of words of length $n-1$ over $\{0,1,2,\ldots,n+1\}$ having $n-2$ letters from $2,3,\ldots,n$,  no two of them ere the same, and the letters of each binary subword are written in increasing order. \seqnum{A175925}
\end{enumerate}
\end{example}

\section{Columns of Pascal matrix}
Let $a$ be a positive integer. We say that a word over $\{0,1,2\ldots,a-1\}$ that has no rises has the property  $\mathcal P_2$.
We examine the following problem: find the number of words of length $n-1$ over the finite alphabet $\{0,1,\ldots,a-1,\ldots\}$  such that subwords from $\{0,1,\ldots,a-1\}$ satisfy  $\mathcal P_2$.
We show that the values of the initial function are  figurate numbers, that is, the numbers forming  columns of the Pascal matrix.
We let $d_a(n-1)$ denote the number of such words of length $n-1$.
\begin{proposition} For positive integers $a,n$, the following formula holds:
\begin{equation}\label{fgb}d_a(n-1)={n+a-2\choose a-1}.\end{equation}
\end{proposition}
\begin{proof} We first have $d_a(0)=1$, since the empty word does not have a rise. Assume that $n&gt;1$. We have
\begin{equation*}d_{a+1}(n-1)=d_a(n-1)+d_{a+1}(n-2),(n&gt;1).\end{equation*}
Namely, if a word of length $n-1$ over $\{0,1,\ldots,a-1,a\}$ having no rises  begins with a letter from $\{0,1,\ldots,a-1\}$, then the letter $a$ can not appear in such a word.
Hence, there are $d_{a}(n-1)$ such words.
There remain the words  of length $n-1$ beginning with $a$. Obviously, there are
$d_{a+1}(n-2)$ such words.
It follows that
\begin{equation*}\begin{array}{ccc}d_{a+1}(n-1)-d_{a+1}(n-2)&amp;=&amp;d_a(n-1),\\
d_{a+1}(n-2)-d_{a+1}(n-3)&amp;=&amp;d_a(n-2),\\
&amp;\vdots&amp;\\
d_{a+1}(1)-d_{a+1}(0)&amp;=&amp;d_a(1).
\end{array}\end{equation*}
Adding the expressions on the left-hand sides, as well as those on the right-hand side, we obtain the following recurrence:
\begin{equation}\label{ww}d_{a+1}(n-1)=\sum_{i=1}^{n}d_a(i-1).\end{equation}
To prove (\ref{fgb}), we use induction on $a$. If $a=1$, then $d(n-1,1)=1$, since the alphabet consists of the empty word.
 Assume that the statement holds for $a\geq 1$. Then, (\ref{ww}) takes the form
\begin{equation*}
d_{a+1}(n-1)=\sum_{i=1}^n{i+a-2\choose a-1},
\end{equation*}
and the statement holds according to the  horizontal recurrence for the binomial coefficients.
\end{proof}
Therefore, $f_0(n)={n+a-2\choose a-1},(n=1,2,\ldots)$.
Since $f_0(1)=1$, and the empty word satisfies $\mathcal P_2$, we may use Proposition \ref{pr1} to obtain the following result.
\begin{proposition} Let $m,n,k,a$ be integers such that $a, m &gt; 0$ and
$1\leq k\leq n$. The following assertions hold:
\begin{enumerate}
\item
 The number of words of length $n-1$ over $\{0,1,\ldots,a-1,a,\ldots,a+m-1\}$ that satisfy $\mathcal P_2$ is $f_m(n)$.
\item  Consider the alphabets $\Omega=\{0,1,\ldots,a+m-1\}$ and $\Delta=\{a+m,a+m+1,\ldots,a+m+p-1\}$. Assume that $N(k-1)$ is the number of words of length $k-1$ over $\Delta$ having a property $\mathcal Q_2$. Then, the number of words of the form (\ref{xx}), of length $n-1$, over $\Omega\cup\Delta$, and satisfying $\mathcal P_2$, and $\mathcal Q_2$ is equal to $N(k-1)\cdot c_m(n,k)$.
    \end{enumerate}
\end{proposition}


To derive an explicit formula for $c_1(n,k)$, we need the following binomial identity.
\begin{identity} Let $u\geq v\geq w\geq 1$ be integers. Then,
\begin{equation}\label{idd1}{u\choose
v}=\sum_{i=w}^{u-v+w}{i-1\choose w-1}{u-i\choose v-w}.\end{equation}
\end{identity}
\begin{proof} We know that ${u\choose v}$ is the number of binary words of length $u$ having  $v$ zeros. We let $i$ denote the position of the $w$th zero in a word, counting from  left to right. It is clear that $w\leq i\leq u-v+w$. For a fixed $i$, the number of words is ${i-1\choose w-1}{u-i\choose v-w}$. Summing over all $i$, we obtain (\ref{idd1}).
\end{proof}
\begin{note}The identity (\ref{idd1}) generalizes the horizontal recurrence for binomial coefficients, which we obtain for either $w=1$ or $w=v$. \end{note}

\begin{proposition}\label{cc}  Let $n,k,a$ be integers such that $a&gt;0$ and
$1\leq k\leq n$. Then
\[c_1(n,k)={n+ak-k-1\choose ak-1}.\]
\end{proposition}
\begin{proof}
We use induction on $k$. From $(A)$, we have
\begin{equation*}c_1(n,1)=f_0(n)={n+a-2\choose a-1},\end{equation*} which means that the statement is true for $k=1$.  Using induction, we  conclude that the  statement  is equivalent to the binomial identity
\begin{equation*}{n+ak-k-1\choose ak-1}=\sum_{i=1}^{n-k+1}{i+a-2\choose a-1}{n+ak-k-a-i\choose ak-a-1}.\end{equation*}
We prove that this identity follows from Identity \ref{idd1}. Namely, taking $w+1$ instead
of $w$  and replacing $i-1$ by $j$ yields
\begin{equation*}{u\choose v}=\sum_{j=w}^{u-v+w}{j\choose w}{u-j-1\choose v-w-1}.\end{equation*}
Then, taking $w=a-1$ and replacing $j$ by $i+a-2$ implies
\begin{equation*}{u\choose v}=\sum_{i=1}^{u-v+1}{i+a-2\choose a-1}{u-a-i+1\choose v-a}.\end{equation*}
Finally, taking $u=n+ak-k-1$, and $v=ak-1$, we obtain the desired result.
\end{proof}
Using (B) and (C), we obtain the following explicit formulas:
\begin{proposition} Let $m,n,k,a$ be integers such that $a, m &gt; 0$ and
$1\leq k\leq n$. We have
 \begin{align*}c_m(n,k)&amp;=\sum_{i=k}^n(m-1)^{i-k}{i-1\choose k-1}{n+ai-i-1\choose ai-1},\\
 f_m(n)&amp;=\sum_{i=1}^nm^{i-1}{n+ai-i-1\choose ai-1}.\end{align*}
\end{proposition}
 Note that the case $a=2$ was considered  in~\cite[Example 31]{ja3}.
We  finish this section with a number of particular results.
\begin{example}
\begin{enumerate}
\item For $a=3,m=1$,
   ${n+2k-1\choose 3k-1}$ is equal to the number of quaternary words of length $n-1$  having $k-1$ letters equal to $3$, and avoiding $01,02$, and $12$. \seqnum{A127893}
\item For $a=3,m=1$,  $\sum_{k=1}^n{n+2k-1\choose 3k-1}$ is the number of quaternary words of length $n-1$  avoiding $01,02,12$. \seqnum{A052529}
 \item For $a=3,m=2$, $\sum_{i=1}^n2^{i-1}{n+2i-1\choose 3i-1}$
  equals the number of words of length $n-1$ over $\{0,1,2,3,4\}$ avoiding
  $01,02$, and $12$.  \seqnum{A200676}
  \item  For $a=4,m=1$,  the value of $\sum_{k=1}^n{n+3k-1\choose 4k-1}$ is equal to the number of words of length $n-1$ over $\{0,1,2,3,4\}$ such that subwords from
      $\{0,1,2,3\}$ have no rises. \seqnum{A055991}
 \item For $a=5,m=1$, the value  $\sum_{k=1}^n{n+4k-1\choose 5k-1}$ is equal to the number of words of length $n-1$ over $\{0,1,2,3,4,5\}$ such that subwords from
      $\{0,1,2,3,4\}$ have no rises. \seqnum{A079675}
   \end{enumerate}
\end{example}
\section{Central binomial coefficients}
In this section, we consider the problem of enumeration of words over a finite alphabet $\{0,1,\ldots\}$ such that each binary subword has the same number of zeros and ones. We let $\mathcal P_3$ denote this property.
If we define $f_0$ by $f_0(n)={2n-2\choose n-1},$ then  $f_0(n)$ is the number of binary words of length $2n-2$  having equal number of zeros and ones.
 The empty word satisfies $\mathcal P_3$. Also, $f_0(1)=1$, so  we may apply Proposition \ref{pr1}. Hence, we  count the words of the form (\ref{xx}). We have $d_0(n-1)=2n-2$. Take $\Omega=\{0,1\}$. Let $\Delta=\{2,3,\ldots\}$ be a finite alphabet, and let  $N(k-1)$ be the number of words of length $k-1$ over $\Delta$ having a property  $\mathcal Q_3$. Taking $x_ix_i$ instead of  $x_i$, for all $x_i\in\Delta$, we obtain the following results.
\begin{proposition} Let $n,k$ be integers such that $1\leq k\leq n$. We have
\begin{enumerate}
\item
The number of  words over $\Omega\cup\Delta$ of length $2n-2$  having $k-1$ subwords of the form $x_ix_i$ from $\Delta$ satisfying $\mathcal Q_3$, and all binary subwords satisfy $\mathcal P_3$ is $N(k-1)\cdot c_1(n,k)$.
\item  The number of ternary words of length $2n-2$  in which $2$ appears only in runs of even lengths, and all binary subwords satisfy $\mathcal P_3$ is equal to $f_1(n)$.
\end{enumerate}
\end{proposition}
We next derive an explicit formula for $c_1(n,k)$.
\begin{proposition}  For integers $1\leq k\leq n$, we have
\begin{gather*}c_1(n,n)=1,\\c_1(n,k)=\frac{2^{n-k}k(k+2)\cdots(2n-k-2)}{(n-k)!},(k&lt;n).
\end{gather*}
\end{proposition}
\begin{proof}
It is well-known that $g(x)=\frac{1}{\sqrt{1-4x}}$ is  the generating function  for the sequence
\begin{equation*}\left\{{2n-2\choose n-1}:n=1,2,\ldots\right\},\end{equation*}
 of the central binomial coefficients.

   According to (D), the formula follows by the use of the Taylor expansion for the binomial series.
\end{proof}
Calculating  $c_1(n,1)$, we obtain the following result.
\begin{identity}\label{ctbk}
For $n\geq 2$ we have
\begin{equation*}n(n+1)\cdots(2n-2)=2^{n-1}(2n-3)!!.\end{equation*}
\end{identity}
\begin{remark} This identity is a solution to a problem posed in Amer. Math. Monthly~\cite{old}.
\end{remark}
In the case $k=2$, we obtain the following  convolution identity for the central binomial coefficients.
\begin{identity} For $n\geq 0$, we have
\begin{equation*}4^n=\sum_{i_1+i_2=n+2}{2i_1-2\choose i_1-1}{2i_2-2\choose i_2-1}.
\end{equation*}
\end{identity}
Again, we finish the section with a few examples. We assume that all binary subwords satisfy $\mathcal P_3$. Note that in the following examples,  in all binary subwords the number of zeros is  equal the number of ones.
\begin{example}
\begin{enumerate}
 \item The array $c_1(n,k)$ is \seqnum{A054335}.
\item
 The number of ternary words of length $2n-2$ in which $2$ appears  in a run of even length only  is equal to $\sum_{k=1}^nc_1(n,k)$. \seqnum{A026671}
\item For $n\geq 2$,  $4^{n-2}$ is equal to the number of ternary words of length $2n-2$ containing one subword $22$. \seqnum{A000302}
\item For $n\geq 3$, $\frac{2^{n-3}(2n-5)!!}{(n-3)!}$ is equal to the number of ternary words of length $2n-2$ containing two subwords $22$.  \seqnum{A002457}
\item For $n\geq 4$,  $(n-3)4^{n-4}$ is equal to the number of ternary words of length $2n-2$ containing three subwords $22$. \seqnum{A002697}
\item For $n\geq 3$, the number $2(n-2)n$ is equal to the number of ternary words of length $2n-2$ containing $n-3$ subwords $22$. \seqnum{A054000}
\item For $n\geq 3$,  $4c_1(n,3)$ is equal to the number of quaternary words of length $2n-2$ having $2$ subwords as either $22$ or $33$. \seqnum{A002011}
\end{enumerate}
\end{example}
\section{Binomial coefficient ${2n-1\choose n}$}
Our final example is the case when $f_0(n)={2n-1\choose n},(n=1,2,\ldots)$. Combinatorially, the value of $f_0(n)$ is the number of binary words of length $2n-1$ in which the number of ones is greater by $1$ than the number of zeros. We denote this property by $\mathcal P_4$.
 The empty word  does not satisfy this condition. Hence,  we count words of the form  (\ref{xxx}).

 We define $\Omega=\{0,1\}$, and $\Delta=\{2,3,\ldots\}$. Let $N(k-1)$ be the number of words of length $k-1$ over $\Delta$ satisfying a property $\mathcal Q_4$. From the fact that  $d_0(n-1)=2n-1$, the following result follows.
\begin{proposition}Let $n,k$ be integers such that $1\leq k\leq n$. We have
\begin{enumerate}
\item
The number of  words over $\Omega\cup\Delta$ of length $2n-1$,  having $k-1$ letters from $\Delta$  satisfying  $\mathcal Q_4$, and all binary subwords satisfy $\mathcal P_4$ is equal to $N(k-1)\cdot c_1(n,k)$.

Also, each letter from $\Delta$ is both preceded and followed by a binary subword satisfying $\mathcal P_4$.
\item The value of $f_1(n)$  is the number of ternary words of length $2n-1$  in which $2$ is preceded and followed by a binary subword satisfying $\mathcal P_4$.
\end{enumerate}
\end{proposition}
It is known that
\begin{equation*}g(x)=\frac{1}{2x\sqrt{1-4x}}-\frac{1}{2x}\end{equation*}
is a generating function for the sequence $f_0(1),f_0(2),\ldots$.
To obtain an explicit formula for $c_1(n,k)$, we use the expansion (D).

Using the binomial theorem and the expansion  of the binomial series, we obtain
\begin{equation}\label{hehe}
[xg(x)]^k=\frac{1}{2^k}\sum_{j=0}^\infty\left(\sum_{i=1}^k(-1)^{k-i}{k\choose i}i(i+2)\cdots(i+2j-2)\right)\frac{2^j}{j!}x^{j}.
\end{equation}
Since $k$ is the least power of $x$ on the left-hand side of the equation, for $n&lt;k$, we obtain the following identity.
\begin{identity}
\begin{equation*}\sum_{i=1}^k(-1)^{k-i}{k\choose i}i(i+2)\cdots(i+2n-2)=0..\end{equation*}
\end{identity}

\begin{proposition} Let $n,k$ be integers such that $1\leq k\leq n$. Then
\begin{equation}\label{ehe}
c_1(n,k)=\frac{2^{n-k}}{n!}\sum_{i=1}^k(-1)^{k-i}{k\choose i}\cdot\prod_{j=0}^{n-1}(i+2j).
\end{equation}
\end{proposition}
We state several particular cases. For $k=1$, we again obtain Identity \ref{ctbk}.
For $k=2$, we have
\begin{identity} For $n\geq 1$, we have
\begin{equation*}
4^{n-1}={2n-1\choose n}+\sum_{i_1+i_2=n}{2i_1-1\choose i_1}{2i_2-1\choose i_2}.
\end{equation*}
\end{identity}
\begin{proof}
\begin{align*}
c_2(n,2)&amp;=\frac{2^{n-2}}{n!}\left[\prod_{j=0}^{n-1}(2+2j)-2\prod_{j=0}^{n-1}(1+2j)\right]
\\&amp;=\frac{2^{n-2}}{n!}\left[(2n)!!-2(2n-1)!!\right]\\&amp;=\frac{2^{n-2}}{n!}\cdot 2^n\cdot n!
-\frac{2^{n-1}(2n-1)!!}{n!}\\&amp;=4^{n-1}-2^{n-1}\frac{(2n-1)!!}{n!}.
\end{align*}
On the other hand, we have
\begin{align*}2^{n-1}\frac{(2n-1)!!}{n!}&amp;=2^{n-1}\frac{(n-1)!(2n-1)!!}{(n-1)!n!}=
\frac{(2n-2)!!(2n-1)!!}{(n-1)!n!}\\&amp;=\frac{(2n-1)!}{(n-1)!n!}={2n-1\choose n}.
\end{align*}
and the proof follows from (\ref{cmnk}).
\end{proof}
Finally, for $k=n$, we have the following identity.
\begin{identity}
\begin{equation*}n!=\sum_{i=1}^n(-1)^{n-i}{n\choose i}\cdot i\cdot(i+2)\cdots(i+2n-2).\end{equation*}
\end{identity}
 Note that in the following examples,  in all binary subwords the number of zeros is  greater than the number of ones by one.
\begin{example}
\begin{enumerate}
\item The array $c_1(n,k)$ is \seqnum{A035324}.
\item The number of ternary words of length $2n-1$ having one letters  $2$ preceded and followed by a binary word is equal to $c_1(n,2)$. \seqnum{A008549}
\item The number of ternary words of length $2n-1$ having  two letters  $2$, both of which are preceded and followed by a binary word is equal to $c_1(n,3)$. \seqnum{A045720}
\item  The number of ternary words of length $2n-1$ having  three letters  $2$, all of which are preceded and followed by a binary word is equal to $c_1(n,4)$. \seqnum{A045894}
\item The number of ternary words of length $2n-1$ having  four letters  $2$, all of which are preceded and followed by a binary word is equal to $c_1(n,5)$. \seqnum{A035330}
\item The value of $\sum_{k=1}^nc_1(n,k)$ is the number of ternary words of length $2n-1$ in which each $2$ is preceded and followed by a binary word. \seqnum{A049027}
\end{enumerate}
\end{example}
\section{Acknowledgment} I would like to thank the referee for careful reading of the manuscript and several useful suggestions.
\begin{thebibliography}{9}
\bibitem{bir1} 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{jma} 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, Words and linear recurrences, {\it J. Integer Sequences} {\bf 18} (2018),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL21/Janjic/janjic93.html}{Article 18.1.4}.
\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{mw} L. Moser and E. L. Whitney, Weighted compositions, {\it Canad. Math. Bull.} {\bf 4} (1961), 39--43.
\bibitem{old} C. D. Olds, Problem E 760, {\it Amer. Math. Monthly}
{\bf 4} (1947), 108.
\bibitem{slo}  N. J. A.
Sloane, {\it The on-line encyclopedia of integer sequences},
 \url{http://oeis.org}.
\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords:}
restricted word, binomial coefficient,  figurate number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000302},
\seqnum{A002011},
\seqnum{A002457},
\seqnum{A002478},
\seqnum{A002697},
\seqnum{A008549},
\seqnum{A015237},
\seqnum{A026671},
\seqnum{A035324},
\seqnum{A035330},
\seqnum{A045720},
\seqnum{A045894},
\seqnum{A049027},
\seqnum{A052529},
\seqnum{A054000},
\seqnum{A054335},
\seqnum{A055991},
\seqnum{A079675},
\seqnum{A086950},
\seqnum{A099234},
\seqnum{A116088},
\seqnum{A116089},
\seqnum{A127893},
\seqnum{A175925}, and
\seqnum{A200676}.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received March 3 2018;
revised versions received  May 10 2018; May 11 2018.
Published in {\it Journal of Integer Sequences}, May 24 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>