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