\documentclass[12pt]{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}}}

\newcommand\sfo{\mathsf{O}}
\newcommand\sfx{\mathsf{X}}

\newcommand\red{\color{red}}
\newcommand\gr[1]{\rlap{\color{blue}#1}\hphantom{\sf X}}
\newcommand\grr[1]{\rlap{\!\color{blue}#1}\hphantom{\sf X}}

\DeclareMathOperator{\inv}{desc}
\newcommand\N{\mathbb{N}}


\newcommand\dwc{{\footnotesize$\begin{array}{|c|}\hline\sfo\\\hline\sfo\\\hline
\end{array}\ $}} % double white circle
\newcommand\dbs{{\footnotesize$\begin{array}{|c|}\hline\sfx\\\hline\sfx\\\hline
\end{array}\ $}} % double black square
\newcommand\emp{{\footnotesize$\begin{array}{|c|}\hline\gr{}\\\hline\gr{}\\
\hline\end{array}\ $}} % empty

\newcommand\bbs{{\footnotesize$\begin{array}{|c|}\hline\gr{}\\\hline\sfx\\\hline
\end{array}\ $}} % bottom black square
\newcommand\bwc{{\footnotesize$\begin{array}{|c|}\hline\gr{}\\\hline\sfo\\\hline
\end{array}\ $}} % bottom white circle
\newcommand\tbs{{\footnotesize$\begin{array}{|c|}\hline\sfx{}\\\hline\gr{}\\
\hline\end{array}\ $}} % top black square
\newcommand\twc{{\footnotesize$\begin{array}{|c|}\hline\sfo\\\hline\gr{}\\
\hline\end{array}\ $}} % top white circle

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

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
A Famous Identity of Haj\'os in Terms of Sets
}
\vskip 1cm
\large
Rui Duarte \\
Center for Research and Development in Mathematics and Applications \\
Department of Mathematics \\
University of Aveiro \\
3810-193 Aveiro \\
Portugal \\
\href{mailto:rduarte@ua.pt}{\tt rduarte@ua.pt} \\
\ \\
Ant\'onio Guedes de Oliveira \\
CMUP and Mathematics Department \\
Faculty of Sciences \\
University of Porto \\
4099-002 Porto \\
Portugal \\
\href{mailto:agoliv@fc.up.pt}{\tt agoliv@fc.up.pt}
\end{center}

\vskip .2 in

\begin{abstract}
By considering the famous identity on the convolution of the central binomial coefficients
$$\sum_{i+j=n}\binom{2i}{i}\binom{2j}{j} = 4^n$$
in terms of pairs of $\ell$-subsets of $2\ell$-sets, we obtain a new bijective proof and new identities that can be seen as refinements.
\end{abstract}


\section{Introduction}

Thirty years ago, at the end of a captivating article on ``natural
interpretations'' of special identities dealing with natural numbers,
Marta Sved confesses herself defeated by the following identity
\begin{equation}\label{mainId}
\sum_{i+j=n}\binom{2i}{i}\binom{2j}{j} = 4^n \, ,
\end{equation}
which she could not prove combinatorially, and ``invites the reader to
try his bit'' \cite{MSa}. Afterwards, in a ``recount of the letters''
received ``offering solutions to the problem'', she tells us that Paul
Erd\H{o}s ``was quick to point out to [her] that Hungarian
mathematicians tackled it in the thirties: P. Veress proposing and
G. Haj\'os solving it'' \cite{MS} and that ``all solutions are based,
with some variations, on the count of lattice paths, or equivalently
$(1,0)$ sequences''.

In fact, it is well-known that $\tbinom{2 \ell}{\ell}$ counts
the number of paths from $(0,0)$ to $(\ell, \ell)$, where $\ell$ is a positive
integer and each step in the path is of the form $(1,0)$ or $(0,1)$
(see, for instance, the book of Stanley \cite[Exercise 1.3]{RS}).
But there is another way of looking at this
identity, perhaps even more natural, where $\binom{2\ell}{\ell}$
really (and \emph{naturally}) stands for the number of $\ell$-subsets
of a $2\ell$-set, and so where in the left-hand side
of \eqref{mainId} we count the pairs $(A,B)$ such that $A$ is an
$i$-subset of $\{1,\dotsc,2i\}$ and $B$ is a $j$-subset of
$\{1,\dotsc,2j\}$.

In the meantime, different types of proofs appeared \cite{VdA,ChX,DGO}.
Yet, after thirty years, we believe we present here the
first \emph{bijective} proof of \eqref{mainId} not based on lattice
paths. Instead, it is based on properties of these pairs; and it is of
algorithmic nature.

We represent such pairs graphically. For example, we have the
representation
$$ R=\begin{array}{|c|c|c|c|c||c|c|c|c|c|c|}
\hline
\gr{1}&\sfo&\sfo&\sfo&\gr{5}&\gr{1}&\sfx&\sfx&\sfx&\gr{5}&\gr{6}\\
\hline
\gr{6}&\gr{7}&\sfo&\sfo&\grr{10}&\sfx&\sfx&\gr{9}&\sfx&\grr{11}&\grr{12}\\
\hline
\end{array}\,\ \text{ for }\
\,\big(\{2,3,4,8,9\}, \{2,3,4,7,8,10\}\big)\,,$$
formed by a $5$-subset of $\{1,\dotsc,10\}$ and a $6$-subset of
$\{1,\dotsc,12\}$. In this example, there are two
``towers'' with two symbols $\sfo$, in the third and fourth column of the
left-hand side, and two ``towers'' with two symbols $\sfx$, in the second and
fourth column of the six remaining columns. If there were no towers,
all columns would be of one of four types
{\footnotesize$\Bigg( \; \begin{array}{|c|} \hline \sfo \\ \hline \gr{} \\
    \hline \end{array} \;$},
{\footnotesize$\; \begin{array}{|c|} \hline \gr{} \\ \hline \sfo \\
    \hline \end{array} \;$},
{\footnotesize$\; \begin{array}{|c|} \hline \sfx \\ \hline \gr{} \\
    \hline \end{array} \;$} or
{\footnotesize$\; \begin{array}{|c|} \hline \gr{} \\ \hline \sfx \\
    \hline \end{array} \; \Bigg)$}.
But not all the $4^n$ choices of $n$ of such columns would occur,
since in our case they are \emph{ordered}, meaning that any column
with an $\sfo$ must precede any column with an $\sfx$.

The idea behind our proof is to show that there are exactly as many
ordered configurations with towers as there are configurations without
towers where at least one column marked with an $\sfx$ precedes one
column marked with an $\sfo$. More precisely, we build a bijection
$\varphi$ that maps an ordered configuration with $k$ towers to a
configuration without towers where exactly $k$ columns marked with one
$\sfx$ precede a column with one $\sfo$.

The number of configurations with $p$ columns and $i$ towers is
$2^{p-2i}\binom{p}{i}\binom{p-i}{i}$. When $p\in\N_0$ and $i$ is an
integer with $0\leq 2i\leq p$, these numbers form the triangle read by
rows in sequence \seqnum{A051288} of \cite{oeis}, whereas the triangle
$T$ defined by
$$T(p,i)=\binom{p}{i}\binom{p-i}{i}\,,$$
for $p\in\N_0$ and $i\leq p$, is read by rows in \seqnum{A089627}. The first eleven rows of $T$ (for $n=0,1,\dotsc,10$) are as follows: {\footnotesize
$$\begin{array}{rrrrrrrrrrr}
  1&  & & & & & & & & &  \\
  1\rlap{,}& 0& & & & & & & & &\\
  1\rlap{,}& 2\rlap{,}& 0& & & & & & & &\\
  1\rlap{,}& 6\rlap{,}& 0\rlap{,}& 0& & & & & & &\\
  1\rlap{,}& 12\rlap{,}& 6\rlap{,}& 0\rlap{,}& 0& & & & & &\\
  1\rlap{,}& 20\rlap{,}& 30\rlap{,}& 0\rlap{,}& 0\rlap{,}& 0& & & & &\\
  1\rlap{,}& 30\rlap{,}& 90\rlap{,}& 20\rlap{,}& 0\rlap{,}& 0\rlap{,}& 0&&&&\\
  1\rlap{,}& 42\rlap{,}& 210\rlap{,}& 140\rlap{,}& 0\rlap{,}& 0\rlap{,}&
  0\rlap{,}& 0&&&  \\
  1\rlap{,}& 56\rlap{,}& 420\rlap{,}& 560\rlap{,}& 70\rlap{,}& 0\rlap{,}&
  0\rlap{,}& 0\rlap{,}& 0&&  \\
  1\rlap{,}& 72\rlap{,}& 756\rlap{,}& 1680\rlap{,}& 630\rlap{,}& 0\rlap{,}&
  0\rlap{,}& 0\rlap{,}& 0\rlap{,}& 0&  \\
  1\rlap{,}& 90\rlap{,}& 1260\rlap{,}& 4200\rlap{,}& 3150\rlap{,}& 252\rlap{,}&
  \ 0\rlap{,}&\ 0\rlap{,}&\ 0\rlap{,}&\ 0\rlap{,}&\ 0
\end{array}$$}


As a consequence of our bijection, we shall see in
Corollary~\ref{mainIddesd} that, for any fixed natural number $n$, if
we define sequence $A_p$ as the convolution of sequence
$\big(T(p,i)\big)_{i\in\N_0}$ with
$\big(T(n-p,i)\big)_{i\in\N_0}$, the sum $S_n$ of $A_p$ for $0\leq
p\leq n$ is row $n$ of \seqnum{A229032} of \cite{oeis},
given by $S_n(k)=4^k\binom{n+1}{2k+1}$. In other words, if
$\ 0\leq2k\leq n\,$,
\begin{equation}\label{mainRes}
\sum_{p=0}^n \sum_{i=0}^k \binom{p}{i} \binom{p-i}{i} \binom{n-p}{k-i} \binom{n-p-k+i}{k-i} =4^k \binom{n+1}{2k+1}.
\end{equation}
Note that if $T(n,k)$ is defined as in \seqnum{A085841} of \cite{oeis}
and $n$ is even then $S_n(k)=T(n/2,k)$. On the other hand, if $T(n,k)$
is defined as in \seqnum{A105070} then $S_n(k)=2^kT(n+1,k)$.

\begin{example}[$n=10$]
{\footnotesize
$$\begin{array}{lrrrrrrrr}
 A_0\,=&(\ 1,& 90,& 1260,& 4200,& 3150,& 252,& 0,& \cdots )\\
 A_1\,=&(\ 1,& 72,& 756,& 1680,& 630,& 0,& 0,& \cdots )\\
 A_2\,=&(\ 1,& 58,& 532,& 1400,& 1190,& 140,& 0,& \cdots )\\
 A_3\,=&(\ 1,& 48,& 462,& 1400,& 840,& 0,& 0,& \cdots )\\
 A_4\,=&(\ 1,& 42,& 456,& 1280,& 780,& 120,& 0,& \cdots )\\
 A_5\,=&(\ 1,& 40,& 460,& 1200,& 900,& 0,& 0,& \cdots )\\
 A_6\,=&(\ 1,& 42,& 456,& 1280,& 780,& 120,& 0,& \cdots )\\
 A_7\,=&(\ 1,& 48,& 462,& 1400,& 840,& 0,& 0,& \cdots )\\
 A_8\,=&(\ 1,& 58,& 532,& 1400,& 1190,& 140,& 0,& \cdots )\\
 A_9\,=&(\ 1,& 72,& 756,& 1680,& 630,& 0,& 0,& \cdots )\\
 A_{10}\,=&(\ 1,& 90,& 1260,& 4200,& 3150,& 252,& 0,& \cdots )\\
 \hline
S_{10}\,=&(11,& 660,& 7392,& 21120,& 14080,& 1024,&\ 0,& \cdots)
\end{array}$$}
\end{example}

\section{The main theorem}

Let $[0]=\varnothing$, and $[n]=\{1,2,\dotsc,n\}$ for a positive
integer $n$. For every pair $(A,B)$ such that $A$ is an $i$-subset of
$[2i]$, $B$ is a $j$-subset of $[2j]$, and $i+j=n$, represent each
element of $A$ by a naught ($\sfo$) in a $2\times i$ rectangle of
cells numbered from left to right and from top to bottom, and each
element of $B$ similarly by a cross ($\sfx$) in a $2\times j$
rectangle. Finally, join the rectangles in a $2\times n$ rectangle
$R$. Note that we consider also the cases with $i=0$ or $j=0$, where
the respective symbol does not appear.

\begin{definition}
  A $2\times n$ rectangle, where exactly $n$ of the $2n$ cells are
  marked with one of two symbols, $\sfo$ and $\sfx$, with the
  restriction that columns with both symbols do not exist, is called a
  \emph{configuration} (or \emph{$n$-configuration}). The columns with
  no marked cells are \emph{empty columns} and the columns with two
  marked cells are \emph{towers}. Both are called \emph{even columns}
  and the columns with exactly one marked cell are called
  \emph{odd}. We say that a pair of consecutive columns with cells
  marked $\sfx$ and $\sfo$, respectively, is a \emph{descent}.  An
  \emph{ordered configuration $C$ of type $(i,j)$} is the
  concatenation of an $i$-configuration with no cells marked with an
  $\sfx$ with a $j$-configuration with no cells marked with an $\sfo$,
  where $i$ and $j$ are nonnegative integers.  The $i$-configuration
  is the \emph{$\sfo$-region} of $C$ and the $j$-configuration
  is the \emph{$\sfx$-region}.  Finally, the set of ordered
  $n$-configurations is denoted by $\mathcal{O}_n$ and the set of
  $n$-configurations without towers is denoted by $\mathcal{NT}_n$.
\end{definition}

Note that the \emph{ordered} configurations are exactly the
configurations that represent the pairs $(A,B)$ as defined above. By
definition, the number of towers and the number of empty columns in
each of the two original subrectangles are equal. Since there are four
types of odd columns, $|\mathcal{NT}_n|=4^n$ and \eqref{mainId} states
that $|\mathcal{O}_n|=|\mathcal{NT}_n|$.

In this article we define (recursively) a bijection
$\varphi:\mathcal{O}_n\to\mathcal{NT}_n$ that leaves the ordered
configurations without towers invariant.  More precisely, we prove
that \emph{if $R$ is an ordered configuration with $k$ towers, then
$\varphi(R)$ is a configuration without towers with
exactly $k$ descents}.

The main idea behind the proof is simple: suppose that $k=1$, so that
we have only one tower and one empty column or one empty column and
one tower, in positions $\ell$ and $m$, say, respectively ($\ell<m$),
necessarily both in the $\sfo$-region or both in the $\sfx$-region, and
possibly some odd columns between them, also necessarily with the symbol of
the region. We want to transform $R$ into $\varphi(R)$ where there is
exactly one descent, in a way that will allow us to retrieve
$R$.

The columns with position $p\in\{\ell,\ell+1,\dotsc,m\}$ form the
\emph{coding region}. We assume that the cells outside this region
will not be changed. Note that we must encode, first, the symbol of
the tower/region; second, whether the tower precedes the empty column
or the empty column precedes the tower; third, the values of $\ell$
and $m$; and last, the position, above or below, of the marked cell in
each odd column of the coding region. For the first two requirements,
in first analysis we follow the scheme below (see rules (a)--(c)
of Definition~\ref{defpeq}) for replacing the pair tower/empty column
by the descent
\begin{equation}\label{defsimple}
\varphi:\
\begin{array}{|c|c|} \hline \sfo & \gr{} \\ \hline \sfo & \gr{} \\
\hline \end{array} \mapsto
\begin{array}{|c|c|} \hline \gr{} & \gr{} \\ \hline \sfx & \sfo \\
\hline \end{array} \,;\
\begin{array}{|c|c|} \hline \gr{} & \sfo \\ \hline \gr{} & \sfo \\
\hline \end{array} \mapsto
\begin{array}{|c|c|} \hline \gr{} & \sfo{} \\ \hline \sfx & \gr{} \\
\hline \end{array} \,;\
\begin{array}{|c|c|} \hline \sfx & \gr{} \\ \hline \sfx & \gr{} \\
\hline \end{array} \mapsto
\begin{array}{|c|c|} \hline \sfx{} & \gr{} \\ \hline \gr{} & \sfo \\
\hline \end{array} \,;\
\begin{array}{|c|c|} \hline \gr{} & \sfx \\ \hline \gr{} & \sfx \\
\hline \end{array} \mapsto
\begin{array}{|c|c|} \hline \sfx{} & \sfo \\ \hline \gr{} & \gr{} \\
\hline \end{array}\,.
\end{equation}

Then, in the coding region, after encoding, before the cross of the
descent there should only be crosses, and after the naught only
naughts. But note that in the $\sfo$-region there might also be
naughts \emph{after} the coding region, and that in the $\sfx$-region
there might also be crosses \emph{before} it. Hence, we must define
two procedures, $\phi_\sfo$ and $\phi_\sfx$, where the descent will
occupy the last cells of the coding region if the original cells are
naughts, and the first ones if they are crosses. This meets the third
requirement.  Finally, in both cases, we could simply keep the
positions of the odd cells in their columns in the coding region,
except that this might change our encoding of the descent. In this
case we should reverse these positions (see rule 1(f) and 1(g) of
Definition~\ref{defpeq}).

It is easy to see that these rules, formalized below, are sufficient
for encoding the cases where the towers and the empty columns can be
organized in consecutive pairs tower/empty column or empty
column/tower.

But we may have, for instance,
{\footnotesize$\begin{array}{|c|c|c|c|c||}
    \hline \sfo & \sfo & \sfo & \gr{} & \gr{} \\
    \hline \sfo & \sfo & \gr{} & \gr{} & \gr{} \\
    \hline \end{array}\,$}.  There is a beautiful solution for
encoding these configurations, where we first look only at the even
columns and apply recursively the previous procedure.  Consider, for a
$k$-configuration $C$, the $2k$-configuration formed only of odd
columns $D$, where each column of $C$ of form $\frac{X}{Y}$ is
``expanded'' in $D$ so as to obtain $\frac{X}{X}\frac{Y}{Y}$.  Let us
say that $D$ is ``compressed'' in $C$.  Then, $C$ is a configuration
without towers \emph{if and only if} in $D$ the even columns, if any,
occur in consecutive pairs tower/empty column or empty column/tower.
This means that we may apply recursively the previous procedure to any
configuration $R$. First, consider only the even columns
of $R$, forming $S$, say. $S$ is compressed in $S'$. Suppose that now
we may apply the previous procedure to $S'$, being its even columns
already organized in consecutive pairs tower/empty column or empty
column/tower, and that, by doing it, we obtain $T'$.  Now, expand the
columns of $T'$ in $T$ as before and replace every odd column of $R$
by the corresponding column of $T$. Finally, use the former procedure
throughout the new configuration, coding zone by coding zone.  For
instance,
\begin{align*}
&\begin{array}{|c|c|c|c||}
    \hline \sfo & \sfo & \gr{} & \gr{}\\
    \hline \sfo & \sfo & \gr{} & \gr{}\\
    \hline \end{array}
\mapsto\begin{array}{|c|c||}
    \hline \sfo & \gr{}\\
    \hline \sfo & \gr{} \\
    \hline \end{array}
\buildrel{\mathrm{by}\eqref{defsimple}}\over\mapsto
\begin{array}{|c|c|}
    \hline \gr{}& \gr{}\\
    \hline \sfx & \sfo \\
    \hline \end{array}
\mapsto\begin{array}{|c|c|c|c|}
    \hline \gr{} & \sfx & \gr{} & \sfo\\
    \hline \gr{} & \sfx & \gr{} & \sfo\\
    \hline \end{array}\\
    &\begin{array}{|c|c|c|c|c||}
    \hline \sfo & \sfo & \sfo & \gr{} & \gr{} \\
    \hline \sfo & \sfo & \gr{} & \gr{} & \gr{} \\
    \hline \end{array}
\mapsto\begin{array}{|c|c|c|c|c|}
    \hline \gr{} & \sfx & \sfo & \gr{} & \sfo \\
    \hline \gr{} & \sfx & \gr{}& \gr{} & \sfo \\
    \hline \end{array}
\buildrel{\mathrm{by}\eqref{defsimple}}\over\mapsto
    \begin{array}{|c|c|c|c|c|}
    \hline \sfx & \sfo & \sfo & \gr{} & \sfo \\
    \hline \gr{}&\gr{} & \gr{}& \sfx & \gr{}\\
    \hline \end{array}
\end{align*}



% The idea is to delete all the odd columns and then, since both rows
% (of even length) of the remaining configuration are equal, to delete
% one of them and reorganize the rest in a configuration with half the
% length.  Suppose that now we may apply the previous procedure
% (otherwise, we proceed recursively). Then, we obtain a configuration
% without towers, in which we ``double'' each column of form
% $\displaystyle\frac{A}{B}$ so that to obtain
% $\displaystyle\frac{A}{A}\frac{B}{B}$. Note that in this way we obtain
% exactly the configurations formed by consecutive pairs tower/empty
% column and empty column/tower, that we use to replace the former even
% columns. Now, we are able to use the former procedure in all the
% configuration again.
% \medskip

We formalize all these concepts in the following definitions.

\begin{definition}\label{induction}
  Given an $n$-configuration $R$ with $k$ towers, let $R'$ be the
  $2k$-configuration obtained from $R$ by removing all the odd
  columns. For a $2k$-configuration $S$ without odd columns, if we
  delete one of the two equal rows of $S$ and then rearrange the
  remaining $2k$ cells by placing, for every $1\leq i\leq k$, cell
  $2i$ under cell $2i-1$, we obtain a $k$-configuration $S_\downarrow$
  called the \emph{compression of $S$}.  The \emph{depth of $R$},
  $d(R)$, is defined recursively by $d(R)=0$ if $R$ has no towers, and
  by $d(R)=d\big(R'_\downarrow\big)+1$ otherwise.  In the opposite
  direction, given a $k$-configuration $T$, we form a string of $2k$
  cells by reading the cells of $T$ top-to-bottom, left-to-right. Then
  we form a $2k$-configuration, called the \emph{expansion of $T$} and
  denoted $T^\uparrow$, by taking this string as its first and its
  second row.
%In the opposite
%  direction, given a $k$-configuration $T$, by doubling each cell of
%  $T$ column by column, downwards and from left to right, we obtain
%  the \emph{expansion of $T$}, denoted $T^\uparrow$.

For example, for the $11$-configuration $R$ above,
$R'=\text{\footnotesize$\begin{array}{|c|c|c|c||c|c|c|c|} \hline
  \gr{1}&\sfo&\sfo&\gr{4}&\sfx&\sfx&\gr{3}&\gr{4}\\
  \hline
  \gr{}&\sfo&\sfo&\gr{}&\sfx&\sfx&\gr{}&\gr{}\\
  \hline
\end{array}$}\,$,
$R'_\downarrow=\text{\footnotesize$\begin{array}{|c|c||c|c|}
  \hline
  \gr{1}&\sfo&\sfx&\gr{3}\\
  \hline
  \sfo&\gr{4}&\sfx&\gr{4}\\
  \hline
\end{array}$}$
and
$\left(R'_\downarrow\right)'_\downarrow=\text{\footnotesize$\begin{array}{||c|}
  \hline\sfx\\\hline\gr{}\\\hline\end{array}$}\,$.
On the other side,
$\text{\footnotesize$\begin{array}{||c|c|}
    \hline
    \sfx&\gr{}\\
    \hline
    \gr{}&\sfo\\
    \hline
  \end{array}\;$}^\uparrow\!=
\text{\footnotesize$\begin{array}{||c|c|c|c|}
  \hline
  \sfx&\gr{}&\gr{}&\sfo\\
  \hline
  \sfx&\gr{}&\gr{}&\sfo\\
  \hline
\end{array}$}\;$.
Note that all these three last operations, when applied to an ordered
configuration, still give an ordered configuration.
Note also that we have $d(R)=1$ exactly in the cases where, as before,
the towers and the empty columns can be organized in consecutive pairs
tower/empty column or empty column/tower. On the other hand, for example,
$d\,\bigg(\,\text{\footnotesize$\begin{array}{|c|c|c|c|c|}
    \hline\sfo&\sfo&\sfo&\gr{}&\gr{}\\
    \hline\sfo&\sfo&\gr{}&\gr{}&\gr{}\\
    \hline\end{array}$}\,\bigg)=
d\,\bigg(\,\text{\footnotesize$\begin{array}{|c|c|}
    \hline\sfo&\gr{}\\\hline\sfo&\gr{}\\\hline\end{array}$}\,\bigg)+1=2$.
\end{definition}
\begin{definition}\label{defpeq}
  Let $R$ be an $n$-configuration where \emph{the internal columns},
  all but the first and the last columns, if they exist, are odd
  and marked with the same symbol, either $\sfo$ or $\sfx$.
  Use the following rules  to define, in each column of
  $\phi_\sfo(R)$ and $\phi_\sfx(R)$, the position and symbol of the
  marked cell, where
  we denote the $i$th-column of an $n$-configuration $R$ by
  $(R)_i\,$. Note that if an internal column is marked with $\sfx$ we
  do not define $\phi_\sfo(R)$, and if an internal column is marked
  with $\sfo$ we do not define $\phi_\sfx(R)$.

\begin{enumerate}
\item[(a)] Let $\phi_\sfo(R) := R$ and $\phi_\sfx(R) := R$.
\item[(b)] Replace both $(\phi_\sfo(R))_1$ and $(\phi_\sfx(R))_1$ by
  \bbs if the tower of $R$ is \dwc, or by \tbs if the tower of $R$ is
  \dbs.
\item[(c)] Replace both $(\phi_\sfo(R))_n$ and $(\phi_\sfx(R))_n$ by
  \bwc if the last column of $R$ is empty, or by \twc if the last
  column of $R$ is a tower.
\item[(d)] For $1 < i < n$, replace the $\sfo$ in $(\phi_\sfo(R))_i$
  by an $\sfx$ in the same position.
\item[(e)] For $1 < i < n$, replace the $\sfx$ in $(\phi_\sfx(R))_i$
  by an $\sfo$ in the same position.
\item[(f)] If $(\phi_\sfo(R))_{n-1} \neq (\phi_\sfo(R))_1$, reverse
  the position of the marked cell in $(\phi_\sfo(R))_i$ (from top to
  bottom and from bottom to top), for each $i \in \{ 1, \ldots, n-1
  \}$.
\item[(g)] If $(\phi_\sfx(R))_2 \neq (\phi_\sfx(R))_n$, reverse the
  position of the marked cell in $(\phi_\sfx(R))_i$ (from top to
  bottom and from bottom to top), for each $i \in \{ 2, \ldots, n \}$.
\end{enumerate}

It is important to note that if $R$ is formed by a tower and an empty column, in either order, then
both $\phi_\sfo(R)$ and $\phi_\sfx(R)$ are $\varphi(R)$ as defined in
\eqref{defsimple}, namely
$$
\varphi:\
\begin{array}{|c|c|} \hline \sfo & \gr{} \\ \hline \sfo & \gr{} \\ \hline \end{array} \mapsto
\begin{array}{|c|c|} \hline \gr{} & \gr{} \\ \hline \sfx & \sfo \\ \hline \end{array} \,;\
\begin{array}{|c|c|} \hline \gr{} & \sfo \\ \hline \gr{} & \sfo \\ \hline \end{array} \mapsto
\begin{array}{|c|c|} \hline \gr{} & \sfo{} \\ \hline \sfx & \gr{} \\ \hline \end{array} \,;\
\begin{array}{|c|c|} \hline \sfx & \gr{} \\ \hline \sfx & \gr{} \\ \hline \end{array} \mapsto
\begin{array}{|c|c|} \hline \sfx{} & \gr{} \\ \hline \gr{} & \sfo \\ \hline \end{array} \,;\
\begin{array}{|c|c|} \hline \gr{} & \sfx \\ \hline \gr{} & \sfx \\ \hline \end{array} \mapsto
\begin{array}{|c|c|} \hline \sfx{} & \sfo \\ \hline \gr{} & \gr{} \\ \hline \end{array}\,.
$$
\end{definition}

\begin{definition}\label{definv}
  Suppose that $T$ is a configuration without towers. Remember that a
  pair of consecutive (odd) columns marked with $\sfx$ and $\sfo$, in
  this order, is a descent; the number of descents is
  $\inv T$. Hence, $T$ is ordered exactly when $\inv T=0$. Let $T^*$
  be the $(2\,\inv T)$-configuration formed by the consecutive
  descents.  For example,
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
 \hline\gr{}&\sfo&\sfx&\sfx&\gr{}&\sfx&\sfo&\gr{}&\sfx&\sfx&\gr{}&\gr{}&\sfx\\
 \hline\sfo&\gr{}&\gr{}&\gr{}&\sfx&\gr{}&\gr{}&\sfo&\gr{}&\gr{}&\sfo&\sfo&
 \gr{}\\
   \hline\end{array}\:\raisebox{18pt}{$\scriptstyle*$}\!=\,
  \begin{array}{|c|c|c|c|}
    \hline\sfx&\sfo&\sfx&\gr{}\\
    \hline\gr{}&\gr{}&\gr{}&\sfo\\
    \hline\end{array}\,.$$
Given a descent of $T$, the
     \emph{$\sfo$-interval} of the descent is the subrectangle that
     contains the descent and all consecutive columns marked with
     $\sfx$ on the \emph{left-hand side}, and the \emph{$\sfx$-interval}
     of the descent is the subrectangle that contains the descent and
     all consecutive columns marked with $\sfo$ on the \emph{right-hand
       side}. In the former example, the $\sfo$-interval of the first descent
     is  $\text{\footnotesize$\begin{array}{|c|c|c|c|c|}
         \hline\sfx&\sfx&\gr{}&\sfx&\sfo\\
         \hline\gr{}&\gr{}&\sfx&\gr{}&\gr{}\\
         \hline\end{array}\,$}$
     whereas the $\sfx$-interval is
     $\text{\footnotesize$\begin{array}{|c|c|c|}
         \hline\sfx&\sfo&\gr{}\\
         \hline\gr{}&\gr{}&\sfo\\
         \hline\end{array}\,$}$\,.
Note that if we apply $\phi_\sfo$, for example, to a suitable
configuration $R$ and obtain $T$, then $\inv(T)=1$, the (two) even
columns of $R$ are encoded in $T^*$ according to \eqref{defsimple},
and their position in $R$, as well as the odd columns of $R$, follow
from rules (d) and (f). In other words, we may invert $\phi_\sfo$ and
$\phi_\sfx$. For example,
 $\phi_\sfo^{-1}\bigg(\text{\footnotesize$\begin{array}{|c|c|c|c|c|}
         \hline\sfx&\sfx&\gr{}&\sfx&\sfo\\
         \hline\gr{}&\gr{}&\sfx&\gr{}&\gr{}\\
         \hline\end{array}\,$}\bigg)=
\text{\footnotesize$\begin{array}{|c|c|c|c|c|}
         \hline\gr{}&\sfo&\gr{}&\sfo&\sfx\\
         \hline\gr{}&\gr{}&\sfo&\gr{}&\sfx\\
         \hline\end{array}\,$}\,$ and
$\phi_\sfx^{-1}\bigg(\text{\footnotesize$\begin{array}{|c|c|c|}
         \hline\sfx&\sfo&\gr{}\\
         \hline\gr{}&\gr{}&\sfo\\
         \hline\end{array}\,$}\bigg)=
\text{\footnotesize$\begin{array}{|c|c|c|}
         \hline\gr{}&\gr{}&\sfx\\
         \hline\gr{}&\sfx&\sfx\\
         \hline\end{array}\,$}\,$.
\end{definition}


\begin{theorem}\label{theo}
  For every natural number $n$ there is a bijection
  $\varphi=\varphi_n:\mathcal{O}_n\to\mathcal{T}_n$ that maps the
  ordered configurations with $k$ towers, where $0\leq 2k\leq n$, to
  the configurations without towers with exactly $k$ descents.
\end{theorem}
\begin{proof} \hfill \\
\textit{Definition of $\varphi$.} Let $R\in\mathcal{O}_n$ be
    of type $t=(i,j)$. If $R$ has no towers (i.e., $d(R)=0$), we
    define $\varphi(R)=R$.

    If $d(R) \geq 1$, we first consider a configuration $T$ defined as
    follows. If $d(R)=1$, then $T=R$. Otherwise, we consider $\varphi
    (R'_\downarrow)$, which, having no towers, has depth zero. Note
    that $d(R'_\downarrow)<d(R)$ and, if $S=(\varphi
    (R'_\downarrow))^\uparrow$ and $T$ is the configuration obtained
    from $R$ by replacing each even column by the corresponding even
    column of $S$, then $d(T)=d(S)=1$.  Finally $\varphi (R)$ is
    obtained by applying  $\phi_\sfo$ to each segment
    tower-empty column or empty column-tower of $T$, according to
    Definition~\ref{defpeq}, in the first $i$ columns, and by applying
     $\phi_\sfx$ likewise in the last $j$ columns. See
    Example~\ref{example1}.



\textit{Bijectivity of $\varphi$.}  Given a configuration $U$ without
towers, we show that there exists a unique ordered configuration $R$
such that $U=\varphi(R)$ as defined above.  The proof proceeds by
induction on $\inv(U)$.  Note that if $\inv(U)=0$ then $U$ is ordered
(and without towers), and so $U=\varphi(U)$; on the other hand, if $R$
has any tower than $\inv\big(\varphi(R)\big)\neq0$, by the previous
definition.

Suppose that $\inv(U)\geq1$ and let $V$ be obtained from $U^*$ by
 using $\varphi^{-1}$ (as defined in \eqref{defsimple})
in each descent.  Consider $\tilde{U}=V_\downarrow$ and note that
$\inv\,\tilde{U}<\inv\,U$, and so, by induction,
$\tilde{U}=\varphi(\tilde{R})$ for a unique ordered configuration
$\tilde{R}$ of type $(\ell,m)$.  Now, note that if $U=\varphi(R)$ for
some ordered configuration $R$ then $R'_\downarrow=\tilde{R}$ and
$V=S$ as defined above, since $\varphi(V)=U^*$. Thus we may
recover $T$ by considering the $\sfo$-intervals of the first $\ell$
descents of $U$ and by replacing it by its image by
$\phi_\sfo^{-1}$, and similarly by considering the $\sfx$-intervals of
the remaining $m$ descents and by replacing it by its image by
$\phi_\sfx^{-1}$.  Finally, $R$ is obtained from $T$ by replacing the
even columns by the corresponding even columns of $R'$.
\end{proof}

\begin{example} \label{example1} Let again
  $R=\text{\footnotesize$\begin{array}{|c|c|c|c|c||c|c|c|c|c|c|}
      \hline
      \gr{}&\sfo&\sfo&\sfo&\gr{}&\gr{}&\sfx&\sfx&\sfx&\gr{}&\gr{}\\
      \hline
      \gr{}&\gr{}&\sfo&\sfo&\gr{}&\sfx&\sfx&\gr{}&\sfx&\gr{}&\gr{}\\
      \hline
    \end{array}$}\,.$ Then, as before,
  $R'_\downarrow=\text{\footnotesize$\begin{array}{|c|c||c|c|}
      \hline
      \gr{}&\sfo&\sfx&\gr{}\\
      \hline
      \sfo&\gr{}&\sfx&\gr{}\\
      \hline
\end{array}$}$ and so
$\varphi(R'_\downarrow)=\text{\footnotesize$\begin{array}{|c|c|c|c|}
  \hline
  \gr{}&\sfo&\sfx&\gr{}\\
  \hline
  \sfo&\gr{}&\gr{}&\sfo\\
  \hline
\end{array}$}$ and
$S=\text{\footnotesize
$\begin{array}{|c|c|c|c|c|c|c|c|}
  \hline
  \gr{}&\sfo&\sfo&\gr{}&\sfx&\gr{}&\gr{}&\sfo\\
  \hline
  \gr{}&\sfo&\sfo&\gr{}&\sfx&\gr{}&\gr{}&\sfo\\
  \hline
\end{array}$}$. Now, $T=\text{\footnotesize
$\,\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\gr{}&\sfo&\sfo&\sfo&\gr{}&\gr{}&\sfx&\sfx&\gr{}&\gr{}&\sfo\\
\hline
\gr{}&\gr{}&\sfo&\sfo&\gr{}&\sfx&\sfx&\gr{}&\gr{}&\gr{}&\sfo\\
\hline
\end{array}\,$}$ and
$$\varphi(R)=\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline\sfx&\gr{}&\sfo&\gr{}&\gr{}&\gr{}&\sfx&\gr{}&\sfo&\gr{}&\sfo\\
\hline\gr{}&\sfx&\gr{}&\sfx&\sfo&\sfx&\gr{}&\sfo&\gr{}&\sfx&\gr{}\\
\hline\end{array}\,.$$
\smallskip


Let now
$U=\text{\footnotesize$
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\gr{}&\sfx&\sfx&\sfo&\gr{}&\gr{}&\sfx&\gr{}&\sfo&\sfx&\sfx&\sfx&\gr{}\\
\hline
\sfo&\gr{}&\gr{}&\gr{}&\sfo&\sfo&\gr{}&\sfx&\gr{}&\gr{}&\gr{}&\gr{}&\sfx\\
\hline
\end{array}$}\,$.
Then
$U^*=\text{\footnotesize$\begin{array}{|c|c|c|c|}
    \hline
    \sfx&\sfo&\gr{}&\sfo\\
    \hline
    \gr{}&\gr{}&\sfx&\gr{}\\
    \hline
\end{array}$}$
encodes
$V=\text{\footnotesize$\begin{array}{|c|c|c|c||}
\hline
\gr{}&\sfx&\gr{}&\sfo\\
\hline
\gr{}&\sfx&\gr{}&\sfo\\
\hline
\end{array}$}$
 since
$\tilde{U}=\text{\footnotesize$\begin{array}{|c|c|}
\hline\gr{}&\gr{}\\\hline\sfx&\sfo\\\hline
\end{array}$}$
encodes
$\text{\footnotesize$\begin{array}{|c|c||}
\hline\sfo&\gr{}\\\hline\sfo&\gr{}\\\hline
\end{array}$}$ (note the double bars),
which contains no descents. Hence, we have
\begin{align*}
&\varphi^{-1}\bigg(\;\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\gr{}&\sfx&\sfx&\sfo&\gr{}&\gr{}&\sfx&\gr{}&\sfo&\sfx&\sfx&\sfx&\gr{}\\
\hline
\sfo&\gr{}&\gr{}&\gr{}&\sfo&\sfo&\gr{}&\sfx&\gr{}&\gr{}&\gr{}&\gr{}&\sfx\\
\hline
\end{array}\;\bigg)=\\[2.5pt]
&\hphantom{\varphi^{-1}\bigg(}\;\begin{array}{|c|c|c|c|c|c|c|c|c||c|c|c|c|}
\hline
\gr{}&\sfo&\sfo&\sfo&\gr{}&\gr{}&\gr{}&\sfo&\gr{}&\sfx&\sfx&\sfx&\gr{}\\
\hline
\sfo&\sfo&\gr{}&\sfo&\sfo&\sfo&\gr{}&\gr{}&\gr{}&\gr{}&\gr{}&\gr{}&\sfx\\
\hline
\end{array}
\end{align*}
\end{example}

The algorithm behind the proof has been implemented in
\emph{Mathematica} \cite{algoritmo}.

\section{Consequences}

As pointed out before, we obtain directly \eqref{mainId} from
Theorem~\ref{theo}.
\begin{corollary}\label{mainIddesd}
  For every non-negative integer number $n$,
\begin{equation}
\sum_{\substack{i+j=n\\i,j\geq0}}\binom{2i}{i}\binom{2j}{j}\;=\;4^n.\ {}_\square
\tag{\ref{mainId}}
\end{equation}
\end{corollary}

\begin{corollary}\label{mainResdesd}
For every integer numbers $n$ and $k$, if $0\leq 2k<n$ then
\begin{align}
\sum_{p=0}^n \sum_{i=0}^k \binom{p}{i} \binom{p-i}{i} \binom{n-p}{k-i}
\binom{n-p-k+i}{k-i}&=4^k \binom{n+1}{2k+1}\tag{\ref{mainRes}}\\
\intertext{and for every integer $i$ with $\,0\leq i\leq k$\,,}
\label{sstatement}
\sum_{p=0}^n \binom{p}{i} \binom{p-i}{i} \binom{n-p}{k-i}
\binom{n-p-k+i}{k-i} &= \binom{2i}{i}\binom{2k-2i}{k-i}\binom{n+1}{2k+1}\,.
\end{align}
\end{corollary}
\begin{proof}
  By considering all the possible positions of the $i$ white towers
  and of the corresponding $i$ empty columns within the $p$ columns of
  the white region, where $2i\leq p\leq n$, and proceeding similarly
  for the black region, we obtain that the number of ordered
  configurations with $k$ towers is
\begin{align*}
T_k(n)&=\sum_{p=0}^n \sum_{i=0}^k 2^{p-2i}\binom{p}{i}
\binom{p-i}{i}\, 2^{n-p-2(k-i)}\binom{n-p}{k-i} \binom{n-p-k+i}{k-i}\\
&=2^{n-2 k}\sum_{p=0}^n \sum_{i=0}^k \binom{p}{i,i,2p-2i}
 \binom{n-p}{k-i,k-i,n-p-2k+2i}\;.
\end{align*}
On the other hand, the number of configurations without towers and
with exactly $k$ descents is
$$2^n \binom{n+1}{2k+1},$$
since we may mark in each column either the top cell or the bottom
one, and since the marked cells may be characterized by a subset of
$[n+1]$, either the set $S \subseteq [n]$ of positions of the first
cell marked with $\sfx$, the first cell marked with $\sfo$ on its
right-hand side, and so on, if the last column of the configuration is
marked with $\sfx$, or the set $S\cup\{n+1\}$ if the last column of
the configuration is marked with $\sfo$. This number equals $T_k(n)$
by Theorem~\ref{theo}, which proves combinatorially \eqref{mainRes}.

For proving \eqref{sstatement}, note that
$U=\varphi(R)$ if and only if $U^*=\varphi(R')$, and that when $R$
runs through the set of ordered configurations with a given number $i$
of $\sfo$-towers (and $k-i$ $\sfx$-towers) then $R'_\downarrow$ runs
through all $\binom{2i}{i}\binom{2k-2i}{k-i}$ ordered configurations
of type $(i,k-i)$.
\end{proof}

It is perhaps worth noting that Corollary~\ref{mainResdesd} may be
thought of as a refinement of Corollary~\ref{mainIddesd}, in the
precise sense that, since an $n$-configuration can have at most
$\left\lfloor n/2\right\rfloor$ towers,
$\sum_{i+j=n}\binom{2i}{i}\binom{2j}{j}=\sum_{k=0}^{\left\lfloor
    n/2\right\rfloor} T_k(n)$.  In particular,
$\sum_{k=0}^{\left\lfloor n/2\right\rfloor}\binom{n+1}{2k+1}=2^n$. In
fact, the expression on the left-hand side counts the number of
subsets of $\{1,2,\dotsc,n+1\}$ of odd size, and, by Pascal's formula,
$\binom{n+1}{2k+1}=\binom{n}{2k+1}+\binom{n}{2k}$.



\section{Acknowledgments}
We thank the referee for his/her very valuable suggestions, namely
the inclusion of Equation~\eqref{sstatement}.  The work of both authors
was supported in part by the European Regional Development Fund
through the program COMPETE --- Operational Program Factors of
Competitiveness (``Programa Operacional Factores de Competitividade'')
and by the Portuguese Government through FCT --- Funda\c{c}\~ao para a
Ci\^encia e a Tecnologia, under the projects PEst-C/MAT/UI0144/2011
and PEst-C/MAT/UI4106/2011.

\begin{thebibliography}{9}
\bibitem{VdA} V.~De Angelis, Pairings and signed permutations,
  \textit{Amer.\ Math.\ Monthly} \textbf{113} (2006) 642--644.
\bibitem{ChX} G.~Chang and C.~Xu, Generalization and probabilistic
  proof of a combinatorial identity, \textit{Amer.\ Math.\ Monthly}
  \textbf{118} (2011) 175--177.
\bibitem{DGO} R.~Duarte and A.~Guedes de Oliveira,
  A short proof of a famous combinatorial identity, 2013.  Preprint available
  at \url{http://arxiv.org/abs/1307.6693}.
\bibitem{algoritmo} A.~Guedes de Oliveira,
  \url{http://www.fc.up.pt/pessoas/agoliv/OCvsCwT/OCvsCwT.nb}.
\bibitem{RS} R.~Stanley, \textit{Enumerative Combinatorics}, Vol.\ 1,
  Cambridge Studies in Advanced Mathematics, \textbf{49}, Cambridge
  University Press, 1997.
\bibitem{MSa} M.~Sved, Counting and recounting, \textit{Math.\
    Intelligencer} \textbf{5} (1983) 21--26.
\bibitem{MS} M.~Sved, Counting and recounting: the aftermath,
  \textit{Math.\ Intelligencer} \textbf{6} (1984) 44--45.
\bibitem{oeis} N.~J.~A.~Sloane, \textit{The On-Line Encyclopedia of
    Integer Sequences} (2013), available electronically at
  {\url{http://oeis.org}}.
\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 05A19;
Secondary 05A10.

\noindent \emph{Keywords:} combinatorial identity, binomial coefficient,
combinatorial proof.


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A051288},
\seqnum{A085841},
\seqnum{A089627},
\seqnum{A105070}, and
\seqnum{A229032}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  September 11 2013;
revised version received  June 6 2014; August 7 2014.
Published in {\it Journal of Integer Sequences}, August 12 2014.

\bigskip
\hrule
\bigskip

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


\end{document}