\documentclass[12pt,reqno,epsfig]{article}
\usepackage{epsfig,amsfonts}
\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,amssymb,amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\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}}}
\def\diagram#1{\def\normalbaselines{\baselineskip=0pt
\lineskip=10pt\lineskiplimit=1pt} \matrix{#1}}
\def\binom#1#2{\left ( {{#1} \atop {#2}} \right )}
\def\eqalign#1{\null\,\vcenter{\openup\jot\moth
\ialign{\strut\hfill$\displaystyle{##}$&
$\displaystyle{{}##}$\hfill\crcr #1\crcr}}\,}
%\newcommand {\qed} {\null \hfill \rule {2.5mm}{2.5mm}}
\newcommand {\R} {\ensuremath{\mathbb{R}}}
\newcommand {\N} {\ensuremath{\mathbb{N}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf Handshakes Across a (Round) Table}
\vskip 1cm
\large
Tomislav Do\v{s}li\'c \\
Faculty of Civil Engineering\\
University of Zagreb \\
Ka\v{c}i\'ceva 26 \\
10000 Zagreb \\
Croatia\\
\href{mailto:doslic@grad.hr}{\tt doslic@grad.hr} \\
\end{center}
\vskip .2 in
\begin{abstract}
We establish an explicit formula for the
number of chord diagrams on $2n$ points with $k$ short chords
and compute the expected number of short chords in a chord
diagram.
\end{abstract}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section]
\section{Introduction}
The chord diagrams made of $n$ non-intersecting chords joining $2n$ points
on a circle are among better known of some $170$ combinatorial
representations of Catalan numbers: they appear, as entry (n), in the
fourteenth place in the famous Exercise 6.19 of Stanley's {\em Enumerative
Combinatorics 2} \cite{stanley2}. In popular literature they are often
described as handshakes of $2n$ people seated around a circular table.
The fact that extending one's hand for a handshake does not really mean
{\em extending\/} it, i.e., increasing its length, is usually quietly
ignored. Hence, the description is highly unrealistic for all but the smallest
values of $n$, and even for those there is a serious danger of dipping
your cravat in a soup-bowl while bending over the table to shake hands with
the diametrally opposite person. We all know from experience that the most
sensible thing to do in such situation is to shake hands with your neighbors,
and to politely nod to the rest. It is immediately clear that
there are exactly two ways to have $n$ handshakes involving only the
nearest neighbors. Moreover, in any possible arrangement of $n$ handshakes
there are always at least two (lucky) pairs who do it in the most
comfortable way, and a moment's reflection will suffice to convince you that
there are exactly $n$ configurations in which exactly $2$ pairs of neighbors
are involved. It is, therefore, legitimate to look at how many ways there
are to have $n$ (non-crossing) handshakes so that $k$ of them are among
neighbors. Further, if we assume that only the handshakes among neighbors
are feasible, it would be interesting to know how many feasible handshakes
there are in a randomly chosen arrangement. In other words, how many out of
$C_n$ chord diagrams have exactly $k$ short chords for a given $2 \leq k
\leq n$, and how many short chords should we expect in an average chord
diagram? (A chord is short if it connects two neighboring points on the cycle.)
\section{Explicit formulas}
We answer the above questions by revisiting a classical bijection among
chord diagrams and Dyck paths. A Dyck path is a lattice path from $(0,0)$ to
$(2n,0)$ with steps $(1,1)$ and $(1,-1)$ never falling below the $x$-axis.
It is well known that Dyck paths on $2n$ steps are counted by the Catalan
numbers (\seqnum{A000108} of \cite{sloane}); indeed, they appear as
incarnation (j) in the above-mentioned
exercise in \cite{stanley2}. It is also well known that the number of Dyck
paths on $2n$ steps with exactly $k$ peaks is given by the Narayana number
$N(n,k) = \frac{1}{n}\binom{n}{k}\binom{n}{k-1}$. (See Exercise 6.36 of
\cite{stanley2} for more on Narayana numbers, as well as the references and
links in \cite{sloane}, \seqnum{A001263}.)
Let us denote the number of all chord diagrams with $n$ chords with exactly
$k$ short chords by $K(n,k)$. From the introductory section we know that
$K(n,2)=n$ and $K(n,n)=2$.
\begin{proposition}
$$K(n,k) = N(n,k) - N(n-1,k) + N(n-1,k-1).$$
\end{proposition}
\begin{proof}
We consider the bijection between the chord diagrams and Dyck paths
implicit in the solution of Exercise 6.19 (n) \cite[p.\ 261]{stanley2}.
It has been rediscovered several times, the earliest reference being from 1931.
The bijection in the case $n=3$ is illustrated in Fig.\ 1.
\begin{figure}[h] \centerline {
\epsfig{file=fig1.eps,height=4.5cm,width=16cm,silent=}}
\caption{Bijection between chord diagrams and Dyck paths.}
\end{figure}
Let us consider a chord diagram of $n$ chords connecting $2n$ points on a
circle. The points are labelled by numbers $1,2, \ldots , 2n$ so that the
labels increase by one in the clockwise direction. Hence each short chord
either connects points $m$ and $m+1$ for some $1 \leq m \leq 2n-1$, or
connects the points labelled by $2n$ and $1$. We start from point $1$, and travel
along the circle in the clockwise direction. Along the way we construct a Dyck
path by starting from the empty path and adding a step whenever we encounter a
chord. For the first encounter with a given chord we add a $(1,1)$ step,
for the second encounter we add a $(1,-1)$ step to the already constructed
path. It is clear that so constructed path is indeed a Dyck path. Furthermore,
each short chord connecting two consecutively labelled points gives rise to a
consecutive pair of $(1,1)$ and $(1,-1)$ steps, thus yielding a
peak in the Dyck path. On the other hand, between the two steps corresponding
to a short chord connecting $2n$ and $1$ there are $2n-2$ steps. Those steps
form a valid Dyck path, and hence the resulting Dyck path is elevated. The
number of such paths with $k-1$ peaks is given by $N(n-1,k-1)$. Hence, the
number of chord diagrams with $k$ short cords that contain the chord $(2n,1)$ is
given by $N(n-1,k-1)$. The number of chord diagrams with $k$ short chords that
do not contain the chord $(2n,1)$ is equal to the number of non-elevated
Dyck paths on $2n$ steps with $k$ peaks, and there are $N(n,k)-N(n-1,k)$
such paths. Since each chord diagram either contains the chord $(2n,1)$ or
not, our result follows by adding the two expressions above.
\end{proof}
By a straightforward manipulation we obtain the following compact
explicit formula for the number of chord diagrams with exactly $k$ short
chords.
\begin{theorem}
$$ K(n,k) = 2 \frac{n}{k} N(n-1,k-1).$$
\end{theorem}
The number triangle $K(n,k)$ appears as sequence \seqnum{A108838} in
\cite{sloane}, along with a couple of combinatorial interpretations in
terms of Dyck paths and parallelogram polyominoes. Besides providing
another combinatorial meaning of \seqnum{A108838}, the present note allows
one to easily compute the expected number of short chords in a chord
diagram (and hence the expected number of the refining parameters in
Dyck paths and parallelogram polyominoes).
Let $E(K(n))$ denote the expected number of short chords in a chord
diagram on $n$ chords. By substituting our explicit formula for $K(n,k)$ into
$\sum_{k=2}^n k K(n,k)$ we obtain the total number of short chords as
$\sum_{k=2}^n
N(n-1,k-1) = 2n C_{n-1}$, and the expected number of short chords
is obtained by dividing the result by the total number of diagrams.
\begin{corollary}
$$E(K(n)) = 2n \frac{C_{n-1}}{C_n}.$$
\end{corollary}
\begin{proof}
$$E(K(n)) = \frac{\sum_{k=2}^n k K(n,k)}{\sum_{k=2}^n K(n,k)}
= 2n \frac{\sum_{k=2}^n N(n-1,k-1)}{C_n}
= 2n \frac{C_{n-1}}{C_n}.$$
\end{proof}
By taking into account the asymptotic behavior of the quotient $C_{n-1}/C_n
\longrightarrow \frac{1}{4}$,
one obtains $E(K(n)) \longrightarrow \frac{n}{2}$. Hence, for large $n$,
one can expect that about half of all chords in a chord diagram will be short.
In other words, about half of all non-crossing handshakes of $2n$ people are
feasible.
\section{Acknowledgements}
Partial support of the Ministry of Science, Education and Sport of the
Republic of Croatia (Grants No. 037-0000000-2779 and 177-0000000-0884) and
hospitality of the Department of Mathematics of the Free University Berlin
are gratefully acknowledged.
\begin{thebibliography}{10}
\bibitem{sloane}
N. J. A. Sloane,
\newblock {\em On-Line Encyclopedia of Integer Sequences},
\newblock available electronically at \href{http://www.research.att.com/$\sim$njas/sequences/index.html}{\tt http://www.research.att.com/$\sim$njas/sequences/index.html}.
\bibitem{stanley2}
R. P. Stanley,
\newblock {\em Enumerative Combinatorics}, Vol. 2,
\newblock Cambridge University Press, Cambridge, 1999.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary: 05A10, 05A19
\noindent \emph{Keywords: }
chord diagram, Catalan numbers, Narayana numbers, Dyck path.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A000108},
\seqnum{A001263}, and
\seqnum{A108838}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received December 15 2009;
revised version received February 16 2010.
Published in {\it Journal of Integer Sequences}, February 22 2010.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}