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

%\usepackage{amsmath,amssymb,amsbsy,amsfonts,amsthm,latexsym,amsopn,amstext,amsxtra,euscript,amscd}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
Unimodal Rays in the Ordinary and \\
\vskip .1in
Generalized Pascal Triangles}
\bigskip

\vskip 1cm
\large
Hac\`ene Belbachir\footnote{Research supported by LAID3
Laboratory of USTHB University and by TASSILI CMEP Accord 05 MDU641b.}\\
USTHB, Faculty of Mathematics\\
P.O.~Box 32\\
El Alia, Algiers\\
Algeria\\
\href{hbelbachir@usthb.dz}{\tt hbelbachir@usthb.dz}\\
\href{hacenebelbachir@gmail.com}{\tt hacenebelbachir@gmail.com}

\ \\

L\'aszl\'o Szalay\footnote{Research supported
by a J\'anos Bolyai Scholarship of HAS, and by Hungarian
National Foundation for Scientific Research Grant No.~T 048954
MAT, No.~T 61800 FT.} \\
Institute of Mathematics and Statistics\\
University of West Hungary\\
Erzs\'ebet utca 9\\
H-9400 Sopron\\
Hungary \\
\href{laszalay@ktk.nyme.hu}{\tt laszalay@ktk.nyme.hu}\\
\end{center}

\vskip .2 in

\begin{abstract}
The present paper provides the solution of two problems recently posed
by Bencherif, Belbachir and Szalay. For example, they
conjectured that any sequence of binomial coefficients lying along a
ray in Pascal's triangle is unimodal.
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
%\newtheorem{theorem}{Theorem}
%\newtheorem{lemma}{Lemma}
%\newtheorem{claim}[theorem]{Claim}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{definition}{Definition}
\newtheorem{question}{Question}
\newtheorem{rem}[theorem]{Remark}
\newtheorem{conj}{Conjecture}





\section{Introduction}

Let $\omega$ denote a positive integer or infinity.
A real sequence $\{a_k\}_{k=0}^\omega$ is {\it unimodal} if there
exists a non-negative integer $\lambda$ such that the subsequence
$\{a_k\}_{k=0}^\lambda$ increases, while $\{a_k\}_{k=\lambda}^\omega$
decreases.

If $\lambda=0$ then the sequence is monotone decreasing.
Therefore it is also natural to consider a monotone increasing
sequence as unimodal with $\lambda=\omega$, even if $\omega=\infty$.

If $a_0\le a_1\le\cdots \le a_{m-1}&lt;a_m=\cdots=a_{M}&gt;a_{M+1}\ge
a_{M+2}\ge\cdots$ then the integers $m,\dots,M$ are called the
{\it modes} of the sequence. In case of $m=M$, we talk about a {\it
peak}; otherwise the set of modes is called a {\it plateau}.

A non-negative real sequence $\{a_k\}$ is {\it
logarithmically concave} ({\it log-concave} or {\it LC} 
for short) if $$a_k^2\ge a_{k-1}a_{k+1}$$
for all $k\ge 1$.

Unimodal and log-concave sequences occur in several branches of
mathematics (see, for example \cite{Br,S}).

Our main interest is to examine combinatorial sequences connected to Pascal's triangle and its generalizations.
The first
result dealing with unimodality of the elements of the 
Pascal triangle is due to Tanny and Zuker \cite{TZ1}, who
showed that the sequence of the terms 
$n-k \choose k$ $(k=0,\dots,\left\lfloor \frac{n}{2}\right\rfloor)$ is
unimodal.
In fact, the LC property of the sequence formed by the binomial
coefficients $n-k \choose k$ was proved, and this implies unimodality
by Theorem~\ref{t:LCUM}. They  also investigated  the unimodality of
$\left\{{n-\alpha k \choose k}\right\}$ in \cite{TZ1fel,TZ2}.

Benoumhani \cite{B} justified the unimodality of the
sequence $\left\{\frac{n}{n-k}{n-k \choose k}\right\}$ connected to Lucas
numbers. Recently, Belbachir and Bencherif 
\cite{BB2} proved that
the elements $2^{n-2k}{n-k \choose k}$ and
$2^{n-2k}\frac{n}{n-k}{n-k \choose k}$ linked to the Pell sequence and its
companion sequence, respectively, provide unimodal sequences.
In all the aforesaid cases the
authors descibe the peaks and the plateaus with two elements.
Incidentally, the paper \cite{BBSz}
generalizes certain results on unimodality of sequences mentioned above. 

One of the purposes of this work is to prove that any ray crossing
Pascal's triangle hits elements of an unimodal sequence
(Theorem~\ref{t:ray} and Corollary \ref{cor0}).
Further, we will show that unimodality 
appears when we consider the generalized Pascal triangle linked to
the homogeneous linear recurrence $\{T_n\}$ of order $s$ given by the
recurrence relation 
\begin{equation}\label{T}
T_n=T_{n-1}+\cdots+T_{n-s},\quad n\ge s
\end{equation} 
and
by the initial values 
\begin{equation}\label{Tini}
T_{0}=\cdots=T_{s-2}=0,\;T_{s-1}=1
\end{equation}
(Theorem~\ref{t:raygen} and Corollary \ref{cor1}).
Questions of a similar kind
were posed in the paper of Belbachir, Bencherif and Szalay \cite{BBSz}.

For the proofs we will need the following two theorems.

\begin{theorem} \label{t:LCUM} 
A log-concave sequence $\{a_k\}$ with no
internal zeros is also unimodal. \end{theorem}

See, for instance, \cite{Br}.

\begin{theorem} \label{t:ordconv} The ordinary convolution of two log-concave sequences preserves the LC property.
More precisely, if both $\{a_n\}$ and $\{b_n\}$ are log-concave, then so is $\{c_n\}$ with
$$
c_n=\sum_{i=0}^na_ib_{n-i}\quad\quad (n=0,1,\dots).
$$
\end{theorem}

See, for instance, \cite{WY}.

\section{Rays in Pascal's triangle}

Let $u\ge0$ and $v$ denote integers, and as usual let
\begin{equation}\label{binplus}
{u\choose v}=\left\{%
\begin{array}{ll}
    \frac{u!}{v!(u-v)!}, &amp; \hbox{if $0\le v\le u$;} \\
    0, &amp; \hbox{otherwise.} \\
\end{array}%
\right.    
\end{equation}
The main advantage of such an interpretation of binomial coefficients is, for example, that one can omit the use of exact limits in sums like
$\sum_{i=0}^u{u\choose i}$ by simply writing   $\sum_i{u\choose i}$ instead. In the sequel, for the sake of convenience, we exploit 
this kind of allowance. As a demonstration, we state Vandermonde's identity
here, without proof.

\begin{lemma}\label{l1}
For arbitrary integers $u\ge0$, $k\ge0$ and $v$ we have
$$
{u+k\choose v}=\sum_i{k\choose i}{u\choose v-i}.
$$
\end{lemma}

\noindent For the set of non-zero binomial coefficients we 
use the phrase {\it Pascal's triangle}. 
Since any row $R^{(u)}$ ($u\ge0$) of the Pascal triangle is the
convolution powers of the log-concave constant sequences $\{1\}$ and
$\{1\}$, it follows that $R^{(u)}$ is a log-concave sequence by Theorem
\ref{t:ordconv}, even if we extend $R^{(u)}$ by (\ref{binplus}). (The
log-concavity of a row in the Pascal triangle also follows from the
direct application of the definition of LC property.)


Now we are ready to prove

\begin{theorem}\label{t:ray}
The sequence of binomial coefficients located along a ray is log-concave.
\end{theorem}

By Theorem {\ref{t:LCUM}}, we immediately  obtain
\begin{cor}\label{cor0}
The sequence of binomial coefficients located along a ray is unimodal.
\end{cor}
\bigskip



{\it Proof of Theorem {\ref{t:ray}}.} 
Since the sequence of zeros is trivially log-concave,
it is sufficient to prove the case when the ray
passes through at least one binomial coefficient in the Pascal triangle. 
Let ${u_0\choose v_0}$ denote such a coefficient. Thus $0\le v_0\le u_0$,
and with the integers $\alpha$ and $\beta$ satisfying $\alpha^2+\beta^2&gt;0$
let us consider the sequence $\{x_k\}$ given by
\begin{equation}
x_k={u_0+\alpha k\choose v_0+\beta k},
\end{equation}
where the integer $k$ varies over all cases when $u_0+\alpha k\ge v_0+\beta k\ge0$.
Since the choice $k=0$ is feasible,
the sequence $\{x_k\}$ contains at least one positive element. 
Without loss of generality we may suppose that
$\gcd(\alpha,\beta)=1$.  
If $\alpha=0$ then $\{x_k\}=\left\{{u_0\choose v_0\pm k}\right\}$ is
the log-concave row $R^{(u_0)}$ of binomial coefficients.

Similarly, if $\beta=0$ then one can readily show that the terms
$x_k={u_0\pm k\choose v_0}$ provide log-concave sequence.  To deduce
this statement,  it suffices to show by recalling the definition of
log-concavity, that
\begin{equation}\label{insx}
{u_0+1\choose v_0}{u_0-1\choose v_0}\le{u_0\choose v_0}^2, \quad\quad\text{if}\;\;0\le v_0\le u_0-1,
\end{equation}
since the direction of a ray is reversible.
By simply extracting the binomial coefficients,
we can check that the above inequality is equivalent to $u_0-v_0\le u_0$.

Moreover, there is no restriction in assuming that $\alpha$ and
$\beta$ are positive because of the symmetry ${n\choose k}={n\choose
n-k}$ of Pascal's triangle (or generally, by (\ref{binplus}), the
symmetry of binomial coefficients).

Suppose now, that ${u\choose v}$ (where $0\le v\le u$) is the element
of $\{x_k\}$ for which $0\le u=u_0+\alpha k$ is minimum. Then the
sequence $\{\bar{x}_k\}=\left\{{u+\alpha k\choose v+\beta
k}\right\}_{k\ge0}$ contains $\{x_k\}$ as a subsequence.

By Lemma \ref{l1}, it is clear that
\begin{equation}\label{fo}
\bar{x}_k={u+\alpha k\choose v+\beta k}=\sum_i{k\choose i}{u+(\alpha-1) k\choose v+\beta k-i}.
%=\sum_i{k\choose i}{u+(\alpha-1) k\choose u-v+(\alpha-\beta-1)k+i}.
\end{equation}
Since the terms $a_i={k\choose i}$, and $b_i={u+(\alpha-1) k\choose
v+\beta k-i}$ are from the row $R^{(k)}$ and $R^{(u+(\alpha-1)k)}$ of
binomial coefficients, respectively, they clearly form log-concave
sequences. Thus $\{\bar{x}_k\}$  is also log-concave. Indeed, $k\ge0$,
and by $u\ge0$ and $\alpha\ge1$ we have $u+(\alpha-1)k\ge0$, so the two
sequences framing the convolution really exist.  Then the proof of
Theorem \ref{t:ray} is complete. $\diamond$


\section{Generalized Pascal triangle and sequences $T_n$}


The elements ${n\choose k}_s$ of the generalized Pascal triangle
have the following combinatorial interpretation. The term ${n\choose k}_s$
assigns the number of different ways of distributing $k$ uniform objects
among $n$ boxes, where each box may contain at most $s$ objects.
Clearly, $0\le k\le sn$. 
In other words, ${n\choose k}_s=\left|\left\{
f:\{0,\dots,n-1\}\rightarrow
\{0,\dots,s\}\mid\sum_{i=0}^{n-1}f(i)=k\right\}\right|$.


For instance, if $s=2$ we obtain
the triangle

\begin{center}
\begin{tabular}{ccccccc}
   &amp;  &amp;  &amp; 1 &amp;  &amp;  &amp;  \\
  &amp; &amp; 1 &amp; 1 &amp; 1 &amp;  &amp;  \\
   &amp; 1 &amp; 2 &amp; 3 &amp; 2 &amp; 1 &amp;  \\
  1 &amp; 3 &amp; 6 &amp; 7 &amp; 6 &amp; 3 &amp; 1 \ ,\\
   &amp;  &amp;  &amp; \vdots &amp;  &amp;  &amp;  \\
\end{tabular}
\end{center}
where ${n\choose k}_2={n-1\choose k-2}_2+{n-1\choose
k-1}_2+{n-1\choose k}_2$, supposing non-negative $u$ in ${u\choose v}_2$ having the value zero  if $v&lt;0$ or
$2u&lt;v$. 
Note that  we omit the subscript 1 and write only ${n\choose k}$ for the usual binomial coefficients if $s=1$.
Now we formulate a lemma on generalized binomial coefficients, which will be useful in the proof of Theorem \ref{t:raygen}.

\begin{lemma}\label{uj}
If $s\ge2$ then we have
\begin{equation}\label{indu}
{n\choose k}_s=\sum_{k_1=\left\lceil\frac{k}{s}\right\rceil}^{\min\{k,n\}}{n\choose
k_1}{k_1\choose k-k_1}_{s-1}.
\end{equation}
\end{lemma}

{\it Proof of Lemma \ref{uj}.} 
Clearly, if we want to distribute $k$ elements, first we choose $k_1$ 
boxes by putting one object into each of them, and then we distribute
the remaining $k-k_1$ elements among the $k_1$  boxes that have been 
chosen, with at most
$s-1$ elements per box. $\diamond$
\bigskip

Notice that we can ignore the indication of limits in the sum
(\ref{indu}) by recalling that for non-negative $u$ the coefficent
${u\choose v}_s=0$ if the integer $v$ is out of the range
$0,\dots,su$.

The generalized Pascal triangle ${n\choose k}_s$, $n\in\mathbb{N};~0\le k\le sn$ is linked to the linear recurrence
$\{T_n\}$ given by (\ref{T}) and (\ref{Tini}) via
the diagonal sum
\begin{equation}\label{sum1}
\sum_{k=0}^{\left\lfloor \frac{sn}{s+1}\right\rfloor}{n-k\choose k}_s=T_{n+s}.
\end{equation}
(For reference, see, for instance \cite{BBK}.) The case $s=1$ returns the nice identity
$$\sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor}{n-k\choose k}=F_{n+1}$$
for Fibonacci numbers \seqnum{A000045},
while $s=2$ is connected to the Tribonacci numbers \seqnum{A000073}.
In the sequel, to extend Theorem \ref{t:ray}, we investigate not only the 
diagonal elements ${n-k\choose k}_s$, but any sequence of elements locating along a ray. 
Hence, in the generalized Pascal triangle, we consider the
log-concavity of a more general sequence $\{w_k\}$ given by
$w_{k}(s;u,v;\alpha,\beta)={u+\alpha k\choose v+\beta k}_s$. We will
prove that the sequence $\{w_k\}$ is log-concave, and consequently
unimodal.  We have


\begin{theorem}\label{t:raygen}
The sequence containing the terms $w_k={u+\alpha k\choose v+\beta k}_s$ is log-concave if $s\ge2$.
\end{theorem}

\begin{cor}\label{cor1}
The sequence $\{w_k\}=\left\{{u+\alpha k\choose v+\beta k}_s\right\}$ is unimodal for any positive integer $s$.
\end{cor}
\bigskip

{\it Proof of Corollary \ref{cor1}.} It comes immediately from Corollary \ref{cor0} and Theorem \ref{t:raygen}. $\diamond$
\bigskip

\noindent For the proof of Theorem \ref{t:raygen} we need the following

\begin{lemma}\label{l2}
Given positive integers $n$ and $s$, the sequence $\{ y_k\}=\left\{{k\choose n-k}_s\right\}$ is log-concave.
\end{lemma}

{\it Proof of Lemma \ref{l2}.}  
In case of $s=1$ the possible values for $k$ are 
\begin{equation}\label{sorrend}
\left\lceil \frac{n}{2}\right\rceil,\left\lceil \frac{n}{2}\right\rceil+1,\dots, n.
\end{equation}
Put $t=n-k$, which goes through on the range $\left\lfloor  \frac{n}{2}\right\rfloor,\left\lfloor  \frac{n}{2}\right\rfloor-1,\dots,0$ when $k$ takes its 
values from the range (\ref{sorrend}). From the reversibility of the order,  the sequence of the terms
${k\choose n-k}={n-t\choose t}$
is log-concave by \cite{TZ1} (or see Introduction of the present paper). 

Assume now that Lemma \ref{l2}
holds for $s-1\ge1$ with all non-negative integer $n$. We have
\begin{equation}
y_k={k\choose
n-k}_s=\sum_{m}^{}{k\choose
m}{m\choose n-k-m}_{s-1}.
\end{equation}
As remarked above, the Pascal triangle row $R^{(k)}=\left\{{k\choose
m}\right\}_m$ is log-concave. By the assertion of the induction, $\left\{{m\choose n-k-m}_{s-1}\right\}_m$ is also
log-concave. Applying Theorem \ref{t:ordconv}, we conclude that the terms  $y_k={k\choose n-k}_s$ form a log-concave sequence. $\diamond$
\bigskip

Now we turn our attention to the 
\bigskip

{\it Proof of Theorem \ref{t:raygen}.}

If $s\ge 2$, by Lemma \ref{uj} we have
\begin{equation}\label{veg}
w_k={u+\alpha k\choose
v+\beta k}_s=\sum_{m}{u+\alpha k\choose
m}{m\choose v+\beta k-m}_{s-1}.
\end{equation}

As we have already noted, the row $R^{(u+\alpha k)}=\left\{{u+\alpha k\choose m}\right\}_m$ of the Pascal triangle is log-concave.
On the other hand, the log-concavity of the sequence $\left\{{m\choose v+\beta k-m}_{s-1}\right\}_m$ is provided by Lemma \ref{l2}. Now it follows from Theorem \ref{t:ordconv} that the ordinary convolution (\ref{veg}) is also log-concave. The proof of Theorem \ref{t:raygen} is complete. $\diamond$


\section{Acknowledgments}

This work was prepared during the visit
by the first author to the University of West Hungary; he wishes to
express his thanks for the support and kind hospitality of the
Institution of Mathematics and Statistics. The second author would like
to thank F.~Luca for his valuable remarks.

\begin{thebibliography}{29}

\bibitem{BB2} H.~Belbachir and F.~Bencherif,
Unimodality of sequences associated to Pell numbers, to appear,
{\it Ars Combinatoria}.

\bibitem{BBSz} H.~Belbachir, F.~Bencherif and L.~Szalay, \\ 
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Szalay/szalay14.html}{Unimodality of
certain sequences connected to binomial coefficients}, {\it J.~Integer Seq.} {\bf 10} (2007), Ar\-tic\-le 07.2.3.

\bibitem{BBK} H.~Belbachir, S.~Bouroubi and A.~Khelladi, Connection between ordinary multinomials, generalized Fibonacci numbers, partial Bell partition polynomials and convolution powers of discrete uniform distribution,
\href{http://arxiv.org/abs/0708.2195}{\tt http://arxiv.org/abs/0708.2195}.

\bibitem{B} M.~Benoumhani, 
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Benoumhani/benoumhani8.html}{A sequence of binomial coefficients related to Lucas and Fibonacci numbers}, {\it J.~Integer Seq.} {\bf 6} (2003), Article 03.2.1.

\bibitem{Br} F.~Brenti, Unimodal, log-concave, and P\'olya
frequency sequences in combinatorics, {\it Mem.~Amer.~Math.~Soc.}
{\bf 81} (1989), no.\ 413.

\bibitem{S} R.~P.~Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry,
{\it Ann.~New York Acad.~Sci.} {\bf 576} (1989), 500--534.

\bibitem{TZ1} S.~Tanny and M.~Zuker, On a unimodality sequence of binomial coefficients, {\it Discrete Math.} {\bf 9} (1974), 79--89.

\bibitem{TZ1fel} S.~Tanny and M.~Zuker, On a unimodal sequence of binomial coefficients, {\it J.~Combin.~Inform.~System Sci.} {\bf 1} (1976), 81--91.

\bibitem{TZ2} S.~Tanny and M.~Zuker, Analytic methods applied to a sequence of binomial coefficients, {\it Discrete Math.} {\bf 24} (1978), 299--310.

\bibitem{WY} Y.~Wang and Y.~N.~Yeh, Log-concavity and LC-positivity, {\it J. Combin. Theory, Ser. A} {\bf 114 } (2007), 195--210.




\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: } unimodality, log-concavity, generalized binomial coefficients, generalized Fibonacci numbers.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A000045} and \seqnum{A000073}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 6 2008;
revised version received  June 9 2008.
Published in {\it Journal of Integer Sequences}, June 20 2008.

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