On a class of linked diagrams. I: Enumeration (Q1252855)

This article is concerned with the enumeration of a class of combinatorial structures first encountered by \textit{J. Touchard} [Can. J. Math. 4, 2--25 (1952; Zbl 0047.01801)] and later considered briefly by \textit{D. J. Kleitman} [Stud. Appl. Math. 49, 297--299 (1970; Zbl 0198.03802)]. The structures are defined as follows: Take \(2n\) points on a line, and construct a complete pairing of these points, the paired points being connected by arcs. Each of the \(n\) arcs connects two distinct points, and no point is incident on more than one arc. The points are taken as labelled in the natural order. Clearly, the total number of distinct arrangements is \((2n - 1)!!\equiv (2n-1)(2n-3)\ldots 3.1\). If a complete pairing on \(2n\) points contains a complete subpairing on \(2j <2n\) consecutive points, the original complete pairing is called reducible; in the contrary case, it is irreducible. Let \(S_n\) be the number of irreducible complete pairings on \(2n\) points. By direct combinatorial arguments, it is shown that \[ S_{n+1} = \sum \frac{\alpha!}{\alpha_1!\cdots \alpha_n!} \prod_{j=1}^n [(2j-1)S_j]^\alpha j \tag{1} \] \[ \text{with}\quad \sum_{i=1}^n i\alpha_i=n,\quad \sum_{i=1}^n \alpha_i=\alpha \text{ for nonnegative }\alpha_i. \tag{2} \] J. Riordan (private communication) pointed out to the author that (1) can be written in the simpler form: \[ S_n = (n-1) \sum_{j=1}^{n-1} S_j S_{n-j}, \quad S_1=1; \tag{3} \] recently, a direct combinatorial proof of (3) has been given by \textit{N. Nijenhuis} and \textit{H. S. Wilf} [The enumeration of connected graphs and linked diagrams, Univ. Pennsylvania preprint (1978); J. Comb. Theory, Ser. A 27, 356--359 (1979; Zbl 0421.05038)]. The second part of the paper under review deals with the ``symmetry-reduced'' case in which complete pairings which are mirror images of each other are identified. Again, a direct combinatorial construction is employed. The results, equations 5.3 and 5.5, contain a common misprint; in both cases, the terms \(\frac{S_{n-n}}{2}\) should be \(\frac{S_{n-m}}{2}\). A table of values for both the labeled and unlabeled cases through \(n=20\) is included. The limit theorem \(\lim_{n\to\infty}\frac{S_n}{(2n-1)!!} = e^{-1}\) was first given in [2]; a detailed proof by \textit{C. J. Everett} and the author may be found in the paper reviewed below [Zbl 0395.05003]. Further asymptotic results on generalizations of equations (3) are given in the paper of the author and \textit{C. J. Everett} in [J. Comb. Inf. Syst. Sci. 3, 1--10 (1978; Zbl 0393.65050).