<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}}}

\DeclareMathOperator{\mc}{mc}

\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
 Binomial Coefficients and  Enumeration\\
 \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}
We derive partial solutions for a recently-posed problem of the
enumeration of restricted words. We obtain several explicit formulas in
which the number of restricted   words is expressed in terms of the
binomial coefficients.
These  results  establish relations between  the partial Bell
polynomials and the binomial  coefficients.

In particular, we link the $r$-step Fibonacci numbers, the binomial
coefficients, and the partitions of a positive integer into at most $r$
parts.
Also, we prove that several well-known classes of integers  can be
interpreted in terms of compositions. We finish the paper with an
extension of a recent result about Euler-type identities for integer
compositions.
\end{abstract}

 \section{Introduction}
 We firstly recall the notion of the invert transform, which we express in terms of the formal power series.  For an arithmetic function $f_0$,  its invert transform $f_1$ is defined by  \[\left(1+\sum_{i=1}^\infty f_0(i)x^i\right)\cdot\left(1-\sum_{i=1}^\infty f_1(i)x^i\right)=1.\]
 In this paper, we consider the case when values of $f_0$ are either $0$ or $1$. Then $f_1$ takes non-negative integer values.
 In a previous work, Janji\'c~\cite{mj} defined the sequence $f_1,f_2,\ldots$ of arithmetic functions so that $f_{m}$ is the invert  transform of $f_{m-1}$ for $m=1,2,\ldots$. The function $f_m$ is called the $m$th invert transform  of $f_0$. The functions $f_1,f_2,\ldots$ generalize the notion of the composition of a positive integer. Namely, if $f_{m-1}$ takes only nonnegative integer values, then $f_m(n)$ equals the number of the colored compositions of $n$ in which the part $i$ may appear in $f_{m-1}(i)$ different colors.
For an arithmetic function $f$, and a positive integer $k$, we define the formal power series $g(x,k;f)$ as \[g(x,k;f)=\left(\sum_{i=1}^\infty f(i)x^{i}\right)^k.\]
We consider the expansion
      \begin{equation}\label{gf}g(x,k;f)=\sum_{n=k}^\infty G(n,k;f)x^{n}.\end{equation}
 It follows that $g(x,k;f)$ is a generating function for the sequence $G(n,k;f),(n=k,k+1,\ldots)$.
 The  functions $g(x,k;f)$ and  the partial Bell polynomials
$B_{n,k}(x_1,x_2,\ldots)$  are related by
     \begin{equation}\label{bel}G(n,k;f)=\frac{k!}{n!} B_{n,k}(1!f(1),2!f(2),\ldots).
     \end{equation}
Also, the following equation  is  well-known:
\begin{equation}\label{f1}G(n,k;f)=\sum_{i_1+i_2+\cdots+i_k=n}f(i_1)\cdots
f(i_k),\end{equation} where the sum is over  positive $i_t,\;(t=1,\ldots,k)$.
Similar expansions have recently been considered by several authors. For instance, Eger~\cite{eg1} called  the numbers $G(n,k;f)$ the weighted integer compositions.
     A number of results of the weighted integer compositions and the partial Bell polynomials may be found in Eger~\cite{eg1,eg2,eg3}. The equation (\ref{f1}) slightly differs from Eger~\cite[Equation (1)]{eg1}, where the sum is over non-negative $i_t,(t=1,2,\ldots,k)$.
D. Birmajer et al.~\cite{bir} proved the following formula:
     \begin{equation}\label{fmn}
f_m(n)=\sum_{k=1}^nm^{k-1}\frac{k!}{n!}B_{n,k}(1!f_0(1),2!f_0(2),\ldots).\end{equation}
In this paper, we investigate the problem of  the  enumeration of some restricted words, counted by the functions $f_1,f_2,\ldots$, when $f_0$ is a binary function (Janji\'c~\cite[Problem 21]{mj}).   We derive several explicit formulas for $G(n,k;f_0)$.
Consequently, we obtain a combinatorial interpretation of $f_m$ in terms of the restricted words over the alphabet $\{0,1,\ldots,m\}$. The obtained results yield a number  identities for the partial Bell   polynomials. Furthermore, each $G(n,k;f_0)$ is expressed  in terms of the binomial coefficients. In this way, we obtain the identities  connecting  the partial Bell polynomials and the binomial coefficients.

In particular, we derive a result linking the $r$-step Fibonacci numbers, the binomial coefficients, and the partitions of positive integers into at most $r$ parts.
We also prove that several well-known classes of integers, such as positive integers, squares, cubes, triangular numbers, and so on,  can be interpreted in terms of compositions. As a consequence, we generalize  a recent result about  Euler-type identities for integer compositions.


For a set $X\subseteq \mathbb P$, where $\mathbb P$ is the set of positive integers,
we will use the following notation:
  \begin{enumerate}
  \item
$G(n,k;X)$ will be the number of compositions of $n$ with $k$ parts in $X$.
Also, $f_1(n;X)$ will be  the number of all compositions of $n$ with parts in  $X$.
\item
$G(n,k;X^c)$ will be the number of compositions of $n$ into $k$ parts, none of which is from  $X$.
 Also, $f_1(n;X^c)$ will be the number of all compositions of $n$ into parts which are not from $X$.
\end{enumerate}
For a binary function $f_0$, we denote  \[A=\lbrace i : f_0(i)=1\rbrace, B=\lbrace i: f_0(i)=0\rbrace.\]
There is a natural bijection between compositions of $n$ and the binary words of length $n-1$, which is given by the correspondence
\[1\to 1,2\to 10,3\to 100,\ldots,\] and then omitting  the leading $1$.
Hence, for $X\subseteq \mathbb P$, $f_1(n;X)$, and $f_1(n;X^c)$ also count the appropriate binary words of length $n-1$.

As an illustration, we present a well-known example.
\begin{example}\label{pp1}{\rm
 If $A=\{1,2\}$, then $G(n,k;A)$ equals the number of compositions of $n$ into $k$ parts
 in $\{1,2\}$. It is well known  that
 \[G(n,k;A)={k\choose n-k}, \quad f_1(n;A)=F_{n+1},\]
 where $F_{n+1}$ is a Fibonacci number.
  By the preceding bijection, we obtain that  $F_{n+1}$ equals the number of binary words of length $n-1$ having all zeros isolated, which  is also a well-known property of the Fibonacci numbers.}
\end{example}
As a consequence of  Birmajer at al.~\cite[Corollary 2.2]{bir}, we obtain
\begin{corollary}\label{cbg}
 The number  $f_m(n;A)$ equals
  the number of words of length $n-1$  over the alphabet $\{0,1,\ldots,m\}$, in which $0$   appears only in a run of length $i-1,\text{ for }i\in A$.

Also, the equation   \[f_m(n;A)=\sum_{k=1}^nm^{k-1}G(n,k;A)\]
holds.
\end{corollary}
Thus, whenever the values of $G(n,k;A)$ are known, we can obtain the corresponding number $f_m(n;A)$ of restricted words over the alphabet $\{0,1,\ldots,m\}$.

We consider the following cases:
\begin{enumerate}
\item $A$ is finite.
\item $B$ is finite.
\item $f_0$ is periodic.
\end{enumerate}

 We start with a simple example.
\begin{example}{\rm Let $A=\mathbb P$.
 A well-known property of compositions implies
\[G(n,k;A)={n-1\choose k-1}\text{ for }k=1,\ldots,n.\]
 As a consequence of Corollary  \ref{cbg}   and the binomial formula, we get
\[f_m(n;A)=(m+1)^{n-1}.\]}
  \end{example}

 Equation (\ref{bel}) implies the following well-known identity:
\begin{identity} \[B_{n,k}(1!,2!,\ldots)=\frac{n!}{k!}{n-1\choose k-1}.\]
The Lah numbers are on the right-hand side of the equation.
\end{identity}
\section{The case when $A$ is finite}
Assume that   $A=\{a_1,a_2,\ldots,a_r\}$, where $1\leq a_1&lt;a_2&lt;\cdots&lt;a_r,(r\geq 1)$. A formula for $G(n,k;A)$ may be derived from the multinomial formula. We derive a formula in a different  way, as a  generalization of the formula from Example \ref{pp1}.
\begin{proposition}\label{visp}We have
\begin{equation}\label{par1}G(n,k;A)=\sum_{(j_1,\ldots,j_{r-1})}{k\choose j_1}{j_1\choose j_2}\cdots {j_{r-2}\choose j_{r-1}},\end{equation} where  the sum 
is over all non-increasing sequences
of non-negative integers $(j_1,\ldots,j_{r-1}),$ such that
 \begin{equation}\label{vlado}n=ka_1+j_1(a_2-a_1)+\cdots +j_{r-2}(a_{r-1}-a_{r-2})+
 j_{r-1}(a_r-a_{r-1}).\end{equation}
If Equation (\ref{vlado}) does not hold, then  $G(n,k;A)=0$. \end{proposition}
\begin{proof} We write $G(n,k;A)$ in the form $G(n,k;a_1,a_2,\ldots,a_r)$. According to (\ref{f1}), we have to solve the Diophantine equation
\begin{equation}\label{jd1}i_1+i_2+\cdots
+i_k=n,\end{equation} where  $i_t$ are in $A$.
 Take $s\in\{0,1,\ldots,k\}$. If there is a solution of (\ref{jd1}) in which $a_1$ appears $s$ times, then  there are ${k\choose s}$ such solutions. In particular, when  $k = s$, there is only one solution. We now subtract $a_1$ from each $i_t,(t=1,2,\ldots,k)$ in (\ref{jd1}). For $s&lt;k$, we obtain
\begin{equation}\label{jd2}j_1+\cdots+j_{k-s}=n-ka_1,\end{equation}
where $j_t\in\{a_2-a_1,\ldots,a_r-a_{r-1}\}$.
     In the case  $s=k$, Equation (\ref{jd1}) has only one solution when $n=ka_1$. This is the case when  in (\ref{par1}) we take
     $j_1=\cdots=j_{r-1}=0$. If $n\not=ka_1$, then  Equation (\ref{jd1}) has no solution.
  It follows that
  \[G(n,k;a_1,\ldots,a_r)=\sum_{j_1=0}^k{k\choose j_1}G(n-ka_1,k-j_1;a_2-a_1,\ldots,a_r-a_{r-1}),\]
where $G(n-ka_1,0;a_2-a_1,\ldots,a_r-a_{r-1})=1$ if $n=ka_1$, and
 $G(n-ka_1,0;a_2-p_1,\ldots,a_r-a_{r-1})=0$ otherwise.
Repeating the same argument, we obtain
\[G(n,k;a_1,\ldots,a_r)=\sum_{k\geq j_1\geq\cdots\geq j_{r-1}\geq
0}{k\choose j_1}{j_1\choose j_2}\cdots  {j_{r-2}\choose j_{r-1}}\cdot X,\] where
\[X=G(n-ka_1-j_1(a_2-a_1)-\cdots-j_{r-2}(a_{r-1}-a_{r-2}),j_{r-1};a_r-a_{r-1}).\]
 The number $X$ equals the number of compositions of  $n-k(a_1-1)-j_1(a_2-a_1)-\cdots -j_{r-2}(a_{r-1}-a_{r-2})$   into $j_{r-1}$ parts, each part equals to $a_r-a_{r-1}$.
As in the case $k=s$, we conclude  that $X=1$, if
$n=ka_1+j_1(a_2-a_1)+\cdots+ j_{r-2}(a_{r-1}-a_{r-2})+j_{r-1}(a_r-a_{r-1})$. If $n\not =ka_1$, then $X=0$. \end{proof}
Proposition \ref{visp} yields the following:
\begin{identity}\label{id2} We have
\[B_{n,k}(0,\ldots,0,a_1!,0\ldots,0,a_2!,0,\ldots)=\frac{n!}{k!}\sum{k\choose
j_1}{j_1\choose j_2}\cdots  {j_{r-2}\choose j_{r-1}},\] where the sum 
is over all  $j_1\geq
j_2 \geq \cdots \geq j_{r-1}\geq 0$ such that \[n=ka_1+j_1(a_2-a_1)+\cdots
+j_{r-2}(a_{r-1}-a_{r-2})+j_{r-1}(a_r-a_{r-1}).\]
 \end{identity}
\begin{note}  We point out that Identity \ref{id2}, as well as the remaining identities of the partial Bell  polynomials,  may be proved directly from  the properties of the partial Bell polynomials.
\end{note}
From Equation (\ref{fmn}), we obtain the following:
\begin{corollary} Let $N$ be the number of words of length $n-1$ over the alphabet
$\{0,1,\ldots,m\}$ such that  $0$ appears only in a run whose length belongs to the set
$\{a_1-1,a_2-1,\ldots,a_r-1\}$. Then \[N=\sum_{k=1}^nm^{k-1}G(n,k;a_1,\ldots,a_r).\]
\end{corollary}

We now consider some special cases.
\begin{corollary} Let $A=\{1,p\}\text{ for }(p&gt;1)$. Then
\begin{equation}
\label{rr1}G(n,n-ip+i;A)={n-ip+i\choose i} \text{ for }i=0,\ldots
\left\lfloor\frac{n}{p}\right\rfloor,\end{equation}
and
\[f_1(n;A)=\sum_{i=0}^{\left\lfloor\frac{n}{p}\right\rfloor}{n-ip+i\choose i}.\]
\end{corollary}
\begin{corollary} If $A=\{1,2,\ldots,r\}$, then \begin{equation}\label{par}G(n,k;A)=\sum{k\choose j_1}{j_1\choose j_2}\cdots{j_{r-2}\choose j_{r-1}},\end{equation}
 where the sum is over all partitions
 $(j_1,j_2,\cdots, j_{r-1})$ of $n-k$ into at most
 $r-1$  parts, each part having the size at most $k$.
\end{corollary}
\begin{proof} Using Proposition \ref{visp}, we have $a_1=1$ and $a_{i}-a_{i-1}=1$ for $i=2,3,\ldots,r$. It follows that the sum is over all $j_1,j_2,\ldots,j_{r-1}$ such that
\[n=k+j_1+\cdots+j_{r-1}.\]
Since $k\geq j_1\geq \cdots\geq j_{r-1}$,  the sequences $(j_1,j_2,\ldots,j_{r-1})$ are
partitions of $n-k$.
\end{proof}
We know that  $f_1(n;A)$ equals the number of all compositions of $n$ with parts in $\{1,2,\ldots,r\}$. These compositions are counted by the $r$-step Fibonacci numbers $F^r_n$. Denoting $k=j_0\geq 1$,  we obtain a result connecting the partitions and the binomial coefficients  with  the $r$-step Fibonacci numbers.
\begin{corollary} We have
\[F^r_{n+r-1}=\sum{j_0\choose j_1}{j_1\choose j_2}\cdots  {j_{r-2}\choose j_{r-1}},\] where the
sum is  over all partitions $(j_0,j_1,j_2,\ldots,j_{r-1})$ of $n$ into at most $r$ parts.
\end{corollary}
Note that the terms of the partitions are written in a non-increasing order.
We finish this section with the following particular case.
\begin{corollary} Consider the set $A=\{1,3,5\}$. If
$n-k\equiv 0 \ (\mathrm{mod} \ 2)$, then
\[G(n,k;A)=\sum_{i=0}^{\min{\{k,\frac{n-k}{2}\}}}{k\choose i}{i\choose \frac{n-k}{2}-i}.\]
Otherwise, $G(n,k;1,3,5)=0$.
\end{corollary}
\begin{proof} From Proposition \ref{visp}, we conclude that \[G(n,k;A)=\sum_{j_1,j_2}{k\choose
j_1}{j_1\choose j_2},\] where $n-k=2j_1+2j_2$, and $k\geq j_1\geq j_2\geq 0$.
It follows that
\[n-k\equiv 0 \ (\mathrm{mod} \ 2),\ \quad j_1\leq \min\left\{k,\frac{n-k}{2}\right\}, \ \quad 
j_2=\frac{n-k}{2}-j_1.\]
 \end{proof}
Some related sequences in Sloane~\cite{slo} are \seqnum{A000930}, \seqnum{A000931},
 \seqnum{A017817}, \seqnum{A052920}, \seqnum{A071675}, \seqnum{A079960},  \seqnum{A079976}, \seqnum{A117760}, \seqnum{A124304}, \seqnum{A191238}, \seqnum{A198295}, \seqnum{A253189}.
\section{The case when $B$ is finite}
This section opens  with a particular case.
\begin{proposition}\label{sve} Let $p&gt;1$ be an integer, and
$B=\{1,2,\ldots p-1\}$. Then
\begin{equation}\label{druga}G(n+p,i+1;B^c)={n-pi+i\choose i},\text{ for
}i=0,\ldots,\left\lfloor\frac{n}{p}\right\rfloor.
\end{equation}
\end{proposition}
\begin{proof}We write the formula (\ref{gf}) in the form
\[(x^{p}+x^{p+1}+\ldots)^k=\sum_{n=0}^\infty G(n+k,k;B^c)x^{n+k}.\]
Since
\begin{equation}\label{sve1}(x^{p}+x^{p+1}+\ldots)^k=\sum_{t=0}^{\infty}{t+k-1\choose k-1}x^{t+kp},\end{equation} we have
\[\sum_{n=0}^\infty G(n+k,k;B^c)x^{n}=\sum_{t=0}^{\infty}{t+k-1\choose k-1}x^{t+kp}.\]
It follows that \[G(n+k,k;B^c)={t+k-1\choose k-1},\] for $n+k=t+kp$, that is, for
 $t=n-k(p-1)\geq 0$. When  $n&lt;k(p-1)$, we have $G(n+k,k;B^c)=0$.
If $n\geq k(p-1)$, then
   $G(n+k,k;B^c)={n-kp+2k-1\choose k-1}$. Taking $n-k$ instead of $n$ gives
     \begin{equation}\label{bc}G(n,k;B^c)={n-kp+k-1\choose k-1}.\end{equation}
By denoting $k=i+1$, and by replacing $n$ by $n+p$, we obtain Equation (\ref{druga}).
\end{proof}
Summing over all $i$ in (\ref{druga}) yields
\begin{corollary}
 The formula  \[f_1(n+p;B^c)=\sum_{i=0}^{\left\lfloor\frac{n}{p}\right\rfloor}{n-pi+i\choose
i} \text{ for }n\geq p\] holds.
Also, the number  $f_m(n+p;B^c)$ equals the number of words of length $n+p$ over the alphabet $\{0,1,\ldots,m\}$, in which $0$ appears only in a run of length $\leq p-1$.
\end{corollary}
\begin{note} Using a different method, the same result is
obtained in \cite[Example 9]{bir}.
\end{note}

\begin{identity} We have
\[B_{n+p,i+1}(0,0,\ldots,p!,(p+1)!,\ldots)=\frac{(n+p)!}{(i+1)!}{n-pi+i\choose i},\left(0\leq
i\leq
\left\lfloor\frac{n}{p}\right\rfloor\right).\]
\end{identity}
For $p=2$, we  obtain the  well-known formula
\begin{equation}\label{fib}F_{n+1}=\sum_{i=0}^{\left\lfloor\frac{n}{2}\right\rfloor}{n-i\choose
i}\text{ for }n\geq 1,\end{equation}
where $F_{n+1}$ is a Fibonacci number.

Assume that $B\not=\emptyset$ is finite, and let $p-1$ be the greatest element of $B$. If $f_0(i)=0$ for each $i\leq p-1$, then we find $g(n,k,B^c)$, as in Proposition \ref{sve}. This also includes the case $p=2$.
 So, we may assume that $p&gt;2$. Take $A_1=\{a_1,\ldots,a_r\}\subset \{1,2,\ldots,p-2\}$, which consists   of all $i\in \{1,2,\ldots,p-2\}$, such that $f_0(i)=1$. We may assume that $A_1\not=\emptyset$. It follows that $B^c=A_1\cup \{p,p+1,\ldots\}$.
\begin{proposition}\label{prr} The following equation holds:
  \[G(n,k;B^c)=\sum_{i=0}^{\min\left\{k,\left\lfloor\frac{n-k}{p-1}\right\rfloor\right \}}\sum_{t=0}^{n-k+i-ip}{k\choose i}{t+i-1\choose i-1}G(n-ip-t,k-i;A_1).\]
\end{proposition}
\begin{proof}We have
 \[g(x,k;B^c)=\left[(x^{a_1}+\cdots+x^{a_r})+(x^p+x^{p+1}+\cdots)\right]^k.\]
The binomial theorem implies
 \begin{gather*}g(x,k;B^c)=\sum_{i=0}^k{k\choose i}(x^{a_1}+\cdots+x^{a_r})^{k-i}(x^p+x^{p+1}+\cdots)^i.
 \end{gather*}
Let $X=(x^{a_1}+\cdots+x^{a_r})^{k-i}(x^p+x^{p+1}+\cdots)^i$.
Proposition \ref{visp} yields
 \[[(x^{a_1}+\cdots+x^{a_r})^{k-i}=\sum_{s=0}^\infty G(s+k-i,k-i;A_1)\cdot x^{s+k-i}.\]
Note that this equation is also true for $i=k$, since $G(s,0;A_1)=1$ if and only if $s=0$.
 Otherwise, $G(s,0;A_1)=0$, by the definition of $G(s,k;A_1)$.

 We also have
 \[ (x^p+x^{p+1}+\cdots)^i=\sum_{s=0}^\infty{s+i-1\choose i-1}x^{s+ip}.\]
This equation also   holds for $i=0$, since ${s+i-1\choose i-1}={s-1\choose s}$, which equals $0$ if $s\not=0$. If $s=0$, from ${-1\choose 0}=1$, we see that the right-hand side  equals $1$.
 We thus obtain
 \begin{gather*}X=\sum_{s=0}^\infty G(s+k-i,k-i;A_1)x^{s+k-i}\cdot \sum_{s=0}^\infty{s+i-1\choose i-1}x^{s+ip}.\end{gather*}

 Multiplying the series on the right-hand side yields
  \[X=\sum_{s=0}^\infty
  \left[\sum_{t=0}^s{t+i-1\choose i-1}G(s-t+k-i,k-i;A_1)\right]x^{s+k-i+ip}.\]
       Hence,
  \begin{equation}\label{j1}g(x,k;B^c)=\sum_{s=0}^\infty
  \sum_{t=0}^s\sum_{i=0}^k{k\choose i}{t+i-1\choose i-1}G(s-t+k-i,k-i;A_1)\cdot x^{s+k-i+ip}.\end{equation}
  If we write (\ref{gf}) in the form
  \[g(x,k;B^c)=\sum_{n=0}^\infty G(n+k,k;B^c)x^{n+k},\]
  then, by comparing the coefficients of the same powers of $x$, we conclude that
    $n=s-i+ip$. Hence, in Equation (\ref{j1}), the sum over $s$ has only one term, obtained for $s=n-ip+i$.
 If $s\geq 0$, then
$i\leq{\left\lfloor\frac{n}{p-1}\right\rfloor}$, which implies that
\[0\leq i\leq \min\left\{k,\left\lfloor\frac{n}{p-1}\right\rfloor\right \}.\]
  We conclude that
 \[G(n+k,k;B^c)=\sum_{i=0}^{\min\left\{k,\left\lfloor\frac{n}{p-1}\right\rfloor\right \}}\sum_{t=0}^{n+i-ip}{k\choose i}{t+i-1\choose t}G(n-ip-t+k,k-i;A_1).\]
 Replacing $n$ by $n-k$ proves our statement.
 \end{proof}
 In particular, if $A_1=\{1\}$, then $G(n-ip-t,k-i;A_1)=1$ if  $n-ip-t=k-i$.
 Otherwise,  $G(n-ip-t,k-i;A_1)=0$. We thus obtain
 \begin{corollary}\label{razni1} If $B=\{2,3,\ldots,p-1\}$, then
 \[G(n,k;B^c)=\sum_{i=0}^{\min\left\{k,\left\lfloor\frac{n-k}{p-1}\right\rfloor\right \}}
 {k\choose i}{n-k-(p-2)i-1\choose i-1}.\]
 \end{corollary}
An immediate consequence is
\begin{identity} The following identity is true
\[B_{n,k}(1,0,\ldots,0,p!,(p+1)!,\ldots)=\frac{k!}{n!}\sum_{i=1}^{\min\{\lfloor\frac{n-k}{p-1}\rfloor,k\}}{k\choose
i}{n-k-(p-2)i-1\choose i-1}.\]
\end{identity}

As a consequence of Corollary \ref{razni1}, we prove that the following well-known classes of
integers count some restricted compositions.
\begin{corollary}
\ \vphantom{x} \ 
\begin{enumerate}
\item {\bf The positive integer} $k$ gives the number of compositions of $k + 2$ into $k$ parts, none of which is equal to $2$. \seqnum{A000027}

\item {\bf The triangular number}  $\frac{k(k+1)}{2}$ gives the number of compositions of $k + 4$ into $k$ parts, none of which is equal to $2$. \seqnum{A000217}

\item {\bf The square} $k^2$ gives the number of compositions of $k+5$ into $k$ parts, none of which is equal to $2$. \seqnum{A000290}

\item {\bf The number  of $k$-dimensional partitions of $4$} $\frac{k(k^2+6k-1)}{6}$
 gives the number of compositions of $k+6$ into $k$ parts, none of which is equal to $2$.
  \seqnum{A008778}

\item {\bf The pentagonal pyramidal number} $\frac{k^2(k+1)}{2}$ gives the number of compositions of $k+7$ into $k$ parts, none of which is equal to $2$. \seqnum{A002411}


\item {\bf 	Number of $k$-dimensional partition of $5$} $\frac{k(k^3+18k^2-k+6)}{24}$ gives the number of compositions of $k+8$ into $k$ parts, none of which is equal to $2$.
    \seqnum{A008779}

\item {\bf The pentagonal number} $\frac{k(3k-1)}{2}$ gives the number of compositions of $k+8$ into $k$ parts,
none of which is equal either $2$ or $3$.\seqnum{A000326}


\item {\bf The cube} $k^3$ gives the number of compositions of $k+11$ into $k$ parts, none of which is equal either $2$ or $3$. \seqnum{A000578}




\item {\bf The hexagonal number} $k(2k-1)$ gives the number of compositions of $k+11$ into $k$ parts, none of which belongs to $\{2,3,4\}$. \seqnum{A000384}

\item {\bf The octagonal pyramidal number} $\frac{k(k+1)(2k-1)}{2}$ gives  the number of compositions of $k+14$ into $k$ parts, none of which belongs to $\{2,3,4\}$.
 \seqnum{A002414}

\item {\bf 	The Cupolar number} $\frac{k(5k^2-3k+1)}{3}$ gives the number of compositions of $k+15$ into $k$ parts, none of which belongs to $\{2,3,4\}$.
 \seqnum{A096000}

\item{\bf Heptagonal number} $\frac{k(5k-3)}{2}$ give the number of compositions of $k+14$ into $k$ parts, none of which belongs to $\{2,3,4,5\}$. \seqnum{A000566}
     (This example is suggested by the referee).
\end{enumerate}
\end{corollary}
\begin{proof} The above  statements are an immediate consequence of Proposition \ref{razni1}.
As an illustration, we prove items 3, 8 and 11.

3. We have $p=3,n=5$, so that Proposition \ref{razni1} reduces to the identity
\[k^2=\sum_{i=1}^2{k\choose i}{5-i-1\choose i-1},(k\geq 2),\]
which is easy to prove.

8. In this case, we have $p=4,n=11$. Denoting $a_k=G(11+k,k;f)$, we obtain
\[a_1=1,a_2=\sum_{i=1}^2{2\choose i}{11-2i-1\choose i-1}=8.\]
If $k\geq 3$, then
\[a_k=\sum_{i=1}^3{k\choose i}{11-2i-1\choose i-1}={k\choose 1}+6{k\choose 2}+6{k\choose
3}=k^3.\]

11. This case reduces to the identity
\[\frac{k(5k^2-3k+1)}{3}=\sum_{i=1}^4{k\choose i}{15-3i-1\choose i-1},\]
which is easy to prove.
\end{proof}


In some cases, we can obtain a simpler formula for $G(n,k;B)$. We illustrate this by
\begin{proposition}\label{pop} If  $B=\{p\} \text{ for }p&gt;1$, then
\begin{enumerate}
\item \[G(pk,k;B^c)=(-1)^k+\sum_{i=1}^k(-1)^{k-i}{k\choose i}{pi-1\choose i-1}.\]
\item If $n&gt;pk$, then \[G(n,k;B^c)=\sum_{i=1}^k(-1)^{k-i}{k\choose
    i}{n-pk+pi-1\choose i-1}.\]
\item If $n&lt;pk$, then
    \[G(n,k;B^c)=\sum_{i=\lceil\frac{pk-n}{p-1}\rceil}^k(-1)^{k-i}{k\choose
    i}{n-pk+pi-1\choose i-1}.\]
\end{enumerate}
\end{proposition}
\begin{proof} In this case, (\ref{gf}) has the form
\[g(x,k;B^c)=[(x+x^2+\cdots)-x^p]^k.\]
Using the binomial theorem yields
\begin{gather*}g(x,k;B^c)=\sum_{i=0}^k{k\choose i}(-x^p)^{k-i}(x+x^2+\cdots)^{i}
\\=(-1)^kx^{pk}+\sum_{i=1}^k{k\choose i}(-x^p)^{k-i}(x+x^2+\cdots)^{i}.\end{gather*}
For $i\geq 1$, applying  equation $(x+x^2+\cdots)^k=\sum_{j=0}^\infty{j+i-1\choose
j}x^{i+j}$, we obtain
\[g(x,k;B^c)=(-1)^kx^{pk}+\sum_{i=1}^k\sum_{j=0}^\infty (-1)^{k-i}{k\choose i}{j+i-1\choose
j}x^{j+i+p(k-i)}.\]
It follows that
\[\sum_{n=0}^\infty G(n,k;B^c)x^{n
}\\=(-1)^kx^{pk}+\sum_{i=1}^k\sum_{j=0}^\infty (-1)^{k-i}{k\choose i}{j+i-1\choose
j}x^{j+i+p(k-i)}.\]
We consider three cases:
\begin{enumerate}
\item $n=pk$. In this case, $pk=j+i+p(k-i)$, which yields $j=pi-i$, and the statement
    holds.
\item $n&gt;pk$. In this case, $j=n-pk+pi-i&gt;0$, and the statement holds.
 \item $n&lt;pk$. The equation $j=n-pk+pi-i&gt;0$ yields $pk-n+j=(p-1)i$,
 that is, $pk-n\leq (p-1)i$. It follows that $i\geq\frac {pk-n}{p-1}$, which proves the statement.
  \end{enumerate}
\end{proof}
\begin{note} These formulas are simpler than the formula derived from Example 11 in \cite{bir}, but are essentially the same.
\end{note}
The referee suggested the following direct proof of 1.
\begin{proof}
If $n=pk$ and $l=p-1$, then~\cite[Identity 3]{bir} implies
\begin{gather*}G(pk,k;B^c)=\frac{k!}{(pk)!}B_{pk,k}(1!,\ldots,(p-1)!,0,(p+1)!,\ldots)\\
=(-1)^k+\sum_{l=0}^{k-1}(-1)^l{k\choose l}{p(k-l)-1\choose k-l-1}=(-1)^k+\sum_{i=1}^k(-1)^{k-i}{k\choose i}{pi-1\choose i-1},\end{gather*}
with the simple change of variables $i=k-l$.
\end{proof}
The remaining two cases can be verified similarly.
\begin{note}
It is easy to obtain  the appropriate formulas for $f_m(n;B^c)$, and their interpretations
in terms of restricted words.
\end{note}

      Some related sequences in Sloane~\cite{slo} are \seqnum{A005251},
      \seqnum{A005252}, \seqnum{A005253}, \seqnum{A049856},
      \seqnum{A051937}, \seqnum{A108758}, \seqnum{A180177}, and
      \seqnum{A205553}.

\section{The case when $f_0$ is periodic}
We first  consider the case when $1$ appears periodically in the sequence $f_0(1),f_0(2),\ldots$.
\begin{proposition}\label{1p1}
Let $p$ be a positive integer, and let  $q$ be a nonnegative integer.
 If $A=\lbrace i : i\equiv q \ (\mathrm{mod} \ p)\rbrace,$
then \[G(n,k;A)={\frac{n-qk}{p}+k-1\choose k-1},\] for
$n-kq\equiv 0 \ (\mathrm{mod} \ p)$. Otherwise, $G(n,k;A)=0$.
\end{proposition}
\begin{proof} In this case, we use formula (\ref{f1}). Each term of the sum in (\ref{f1})
is either $0$ or $1$. For the terms equal $1$, each $i_t$ must be of the form
$i_t=(j_t-1)p+q,(j_t&gt;0)$. It follows that $p(j_1+j_2+\cdots+j_k)=n+(p-q)k$.
We  conclude that  $G(n,k;A)=0$, if $n-kq\not\equiv 0 \ (\mathrm{mod} \ p)$.

 Otherwise, we have\[G(n,k;A)=\sum_{j_1+j_2+\cdots+j_k=\frac{n+(p-q)k}{p}}1,\]
which implies that \[G(n,k;A)={\frac{n-qk}{p}+k-1\choose k-1}.\]
\end{proof}
Applying   (\ref{bel}) in the case $n=kq+rp$, we obtain
\begin{identity}
 \[B_{kq+rp,k}(\ldots,0,q!,0,\ldots,0,(q+p)!,0\ldots)=\frac{(kq+rp)!}{k!}{r+k-1\choose
 k-1}\] .
\end{identity}
In particular,  for $q=1$, we replace $n$ by $n-k$ to obtain
$G(n,k;A)={\frac{n-k}{p}+k-1\choose k-1}$, if $n-k\equiv 0 \ (\mathrm{mod} \ p)$.
 Denoting $\frac{n-k}{p}$ by $i$
implies $G(n,n-ip;A)={i+n-ip-1\choose i}$. Replacing $n$ by $n+1$ yields
 \begin{corollary}
 \begin{equation}\label{rem21}G(n+1,n+1-ip;A)={n-ip+i\choose i}, \text{ for }  i=0,\ldots,
 \left\lfloor\frac{n}{p}\right\rfloor . 
 \end{equation}
Summing over all $i$ we obtain
\[f_1(n+1;A)=\sum_{i=0}^{\lfloor\frac{n}{p}\rfloor}{n-ip+i\choose i}.\]
 \end{corollary}
\begin{remark}
Note that $f_1(n+1;A)$ equals the number of compositions of $n+1$ into parts congruent $1\bmod p$.
\end{remark}
We state two particular cases.
\begin{remark}
 In the case  $p=2$, we obtain Equation (\ref{fib}) once again.
 For $p=3$, the sequence $\lbrace f_1(n+1,A): n=0,1,\ldots\rbrace$  is
	Narayana's cows sequence \seqnum{A000930}.
\end{remark}
Let $q&gt;1$ be a positive integer, and let
$P=\lbrace p_1,p_2,\ldots,p_r\rbrace$ be a set of positive integers. Define $f_0$ in the following way:
\[f_0(n)=\begin{cases}1,&amp;\text{ if $n\equiv p \ (\mathrm{mod} \ q)$, for some  $p\in P$};\\
0,&amp;\text{ otherwise}.\end{cases}\]
 \begin{proposition}\label{zd} The
following formula holds
\[G(n,k;A)=\sum_{i=0}^{\lfloor\frac{n-k}{q}\rfloor}G(n-qi,k;P)\cdot{i+k-1\choose
k-1},\]
where $G(n-qi,k;P)$ can be calculated as in  Proposition \ref{visp}.
\end{proposition}
\begin{proof} The function $g(x,k;A)$ has the form
\[g(x,k;A)=(x^{p_1}+\cdots+x^{p_r})^k(1+x^q+x^{2q}+\cdots)^k.\] It follows that
\[g(x,k;A)=\sum_{i=0}^\infty G(i+k,k;P)x^{i+k}\cdot\sum_{i=0}^\infty{i+k-1\choose k-1}x^{iq}.\]
We conclude that
\begin{equation}\label{jjj}g(x,k;A)=\sum_{u=0}^\infty\sum_{v=0}^uG(u-v+k,k;P)\cdot{v+k-1\choose
k-1}x^{u-v+k+vq}.\end{equation}
Comparing this equation with the expansion (\ref{gf}), we obtain that
\[n=u+(q-1)v.\] This implies that $0\leq u\leq n$ so that (\ref{jjj}) yields
\[G(n+k,k;A)=\sum_{u=0}^n\sum_{v=0}^uG(u-v+k,k;P)\cdot{v+k-1\choose k-1}.\] Changing the order of summation implies \[G(n+k,k;A)=\sum_{v=0}^n\sum_{u=v}^nG(u-v+k,k;P)\cdot{v+k-1\choose k-1}.\] Since  $n=u+(q-1)v$, we obtain  $u-v=n-(q-1)v-v=n-qv$. The condition  $u\geq v$ yields $v\leq
\frac{n}{q}$. Denoting $v=i$ and taking $n-k$ instead of $n$ proves our statements.
\end{proof}
\begin{note}
It is easy to obtain the appropriate  formula for $f_m(n;A)$ and its interpretation
in terms of restricted words.
\end{note}
We finish this section with a particular case.
 \begin{corollary} Assume that $f_0$ consists
of the repeating string $110$. Then
\[G(n,k;A)=\sum_{i=0}^{\lfloor\frac{n-k}{3}\rfloor}{k\choose
n-k-3i}{i+k-1\choose k-1}.\]
\end{corollary} \begin{proof} In this case $q=3, P=\{1,2\}$ so that we have $G(n-3i,k;P)={k\choose
n-k-3i},$ and
the the statement is true. \end{proof}
\begin{corollary}
\ \vphantom{x} \ 
\begin{enumerate}

\item The array $\lbrace G(n,k;A):n=1,2,\ldots;k=1,2,\ldots,n\rbrace$ is the Riordan array of the pair $\left(1,\frac{x(1+x)}{1-x^3}\right),$ without the first column.  \seqnum{A198295}
\item In particular,  {\bf the cake number } ${k\choose 3}+k$ gives the number of compositions of $k+3$ into $k$ parts, none of which is divided by  $3$. \seqnum{A000125}
\end{enumerate}
\end{corollary}


Some other related sequences in Sloane~\cite{slo} are
 \seqnum{A001590}, \seqnum{A003269}, \seqnum{A008998},
 \seqnum{A008999}, \seqnum{A017898}, \seqnum{A052541},
 \seqnum{A052917},  \seqnum{A052927}, \seqnum{A099524},
  \seqnum{A126030}, and \seqnum{A159284}.

\section{ Some Euler-type identities}
In this section, we derive some identities connecting different kinds of compositions. As a particular case, we obtain an Euler-type identity proved in Munagi~\cite{mun}.

By comparing equations (\ref{rr1}), (\ref{druga}),  and (\ref{rem21}), we obtain
\begin{gather*}G(n,n-ip+i;1,p)=G(n+p,i+1;p,p+1,\ldots)\\=G(n+1,n+1-ip;1,1+p,1+2p,\ldots)
={n-ip+i\choose i},\left(i=0,\ldots, \left\lfloor\frac{n}{p}\right\rfloor\right).\end{gather*}
In other words, we have
\begin{corollary} Let $n,p$ be positive integers, and $0\leq
i\leq\lfloor\frac{n}{p}\rfloor$.  The following sets have ${n-ip+i\choose i}$ elements:
\begin{enumerate}
\item The set of compositions of $n$ into $n-ip+i$ parts in $\{1,p\}$.
\item The set of compositions of $n+p$ into $i+1$ parts in
    $\{p,p+1,\ldots\}$. \item The
set of compositions of $n+1$ into $n+1-ip$ parts in
$\{1,1+p,1+2p,\ldots\}$.
 \end{enumerate}
    \end{corollary}
    \noindent
    Since the numbers of all composition of $n$ equals the sum of the numbers of compositions
    into   $1,2,\ldots,n$ parts, we obtain
\begin{corollary} The following sets have the same number of elements:
\begin{enumerate} \item  The set of
compositions of $n+1$ into parts $\equiv 1 \ (\mathrm{mod} \ p)$.
\item The set of compositions of $n$ into parts in $\{1,p\}$.
\item The set of compositions of $n+p$ into parts greater than $p-1$.
 \end{enumerate}
 \end{corollary}
\begin{note} Note that this corollary is the assertion of Theorem 1.2  in Munagi~ \cite{mun},
where the bijections  are obtained by using properties of zig-zag graphs. We also note that if $N$ is the number of elements  in the above sets, then
\[N=\sum_{i=0}^{\left\lfloor\frac{n}{p}\right\rfloor}{n-ip+i\choose i}.\] \end{note}
 We finish the paper with the following Euler-type identities for the partial Bell polynomials.
 \begin{identity}
\begin{gather*}\frac{(n-ip+i)!}{n!}B_{n,n-ip+i}(1,0,\ldots,0,p,0,\ldots)=
\frac{(i+1)!}{(n+p)!}B_{n+p,i+1}(0,\ldots
0,p,p+1,\ldots)\\=
\frac{(n+1-ip)!}{(n+1)!}B_{n+1,n+1-ip}(1,0,\ldots,0,1+p,0\ldots,0,1+2p,0,\ldots)
.\end{gather*}
\end{identity}\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 Seq.} {\bf 19} (2016), 
    \href{https://cs.uwaterloo.ca/journals/JIS/VOL19/Gil/gil6.html}{Article 16.1.3}.
 \bibitem{eg1} S. Eger, Restricted weighted integer compositions
and extended binomial coefficients, {\it J.
    Integer Seq.} {\bf 16} (2013), 
    \href{https://cs.uwaterloo.ca/journals/JIS/VOL16/Eger/eger6.html}{Article 13.1.3}.
 \bibitem{eg2} S. Eger, Some elementary congruences for the number of weighted integer compositions,  {\it J.
    Integer Seq.} {\bf 18} (2015), 
    \href{https://cs.uwaterloo.ca/journals/JIS/VOL18/Eger/eger11.html}{Article 15.4.1}.
  \bibitem{eg3}  S. Eger, Identities for partial Bell polynomials derived from identities for weighted integer compositions,
{\it Aequat. Math.} {\bf 90} (2016), 299--306.
\bibitem{mj} 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{mun} A. O. Munagi, Euler-type identities for integer compositions via zig-zag graphs,
    {\it Integers}
    {\bf 12} (2012), Article 60.
\bibitem{slo}  N. J. A. Sloane, 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: }  binary word, integer composition,
restricted word, enumeration.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000027},
\seqnum{A000125},
\seqnum{A000217},
\seqnum{A000270},
\seqnum{A000290},
\seqnum{A000326},
\seqnum{A000384},
\seqnum{A000566},
\seqnum{A000578},
\seqnum{A000930},
\seqnum{A000931},
\seqnum{A001590},
\seqnum{A002411},
\seqnum{A002414},
\seqnum{A003269},
\seqnum{A005251},
\seqnum{A005252},
\seqnum{A005253},
\seqnum{A008778},
\seqnum{A008779},
\seqnum{A008998},
\seqnum{A008999},
\seqnum{A017817},
\seqnum{A017898},
\seqnum{A049856},
\seqnum{A051937},
\seqnum{A052541},
\seqnum{A052917},
\seqnum{A052920},
\seqnum{A052927},
\seqnum{A071675},
\seqnum{A079960},
\seqnum{A079976},
\seqnum{A096000},
\seqnum{A099524},
\seqnum{A108750},
\seqnum{A108758},
\seqnum{A117760},
\seqnum{A124304},
\seqnum{A126030},
\seqnum{A159284},
\seqnum{A180177},
\seqnum{A191238},
\seqnum{A198295},
\seqnum{A205553}, and
\seqnum{A253189}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 7 2016;
revised versions received  June 13 2016; June 28 2016; July 10 2016.
Published in {\it Journal of Integer Sequences}, August 29 2016.

\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>