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