\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>1)$ or $f_m,(m>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)>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 >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>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>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>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>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>1$. We have
\begin{equation*}d_{a+1}(n-1)=d_a(n-1)+d_{a+1}(n-2),(n>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)&=&d_a(n-1),\\
d_{a+1}(n-2)-d_{a+1}(n-3)&=&d_a(n-2),\\
&\vdots&\\
d_{a+1}(1)-d_{a+1}(0)&=&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 > 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>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 > 0$ and
$1\leq k\leq n$. We have
\begin{align*}c_m(n,k)&=\sum_{i=k}^n(m-1)^{i-k}{i-1\choose k-1}{n+ai-i-1\choose ai-1},\\
f_m(n)&=\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