On a class of linked diagrams. II: Asymptotics (Q1252856)

In the present paper, it is proved that, given quadratic recurrence rule: \[ S_1\equiv 1;\quad S_n = (n-1)\sum_{j=1}^{n-1} S_j S_{n-j},\quad n\ge 2, \tag{1} \] the following asymptotic result holds: \[\lim_{n\to\infty} \frac{S_n}{(2n-1)!!} = e^{-1}. \tag{2} \] Here \(S_n\) may be interpreted combinatorially as the number of irreducible complete pairings on \(2n\) points (cf. the paper reviewed above Zbl 0395.05002). Some years ago, \textit{D. J. Kleitman} [Stud. Appl. Math. 49, 297--299 (1970; Zbl 0198.03802)] sketched a proof of (2), omitting details; the only feature that the present proof and Kleitman's have in common is the essential use made of the combinatorial model. In this paper the reducible pairings are split into two classes, one class containing \(D_n-n+1\) elements, with \(D_n = \sum_{j=1}^{n-1} S_{n-j}\binom{2n-j}{j}\), and the remaining class containing \(E_n\) elements, where \(E_n\) is not known explicitly. Since the total number of pairings is \((2n-1)!!\), one has \[ (2n-1)!! - S_n = D_n + E_n - n + 1.\tag{3} \] On dividing (3) by \(S_n\), it is clear that (2) will follow if \[ \lim_{n\to\infty} D_n/S_n = e - 1, \tag{4} \] \[ \lim_{n\to\infty} E_n/S_n = 0. \tag{5} \] (5) is proved by crudely estimating \(E_n\), using the combinatorial model. The bulk of the work is in proving (4); for details, we refer to the original paper. Actually, it appears that a subclass of the pairings enumerated by \(D_n\) is what really gives the asymptotic limit. It has in fact been shown that, with \[D_n^* = \sum_{j=1}^{[(2n-1)/3]} S_{n-j}\binom{2n - 2j - 1}{j}, \] one has \[ \lim D_n^*/S_n = e - 1.\] The relatively complicated proof of this fact is omitted from the paper. The authors have generalized the problem in their paper in [J. Comb. Inf. Syst. Sci. 3, 1--10 (1978; Zbl 0393.65050)], where they consider recurrences of the form \(S_{n+1} = (n+b) \sum_{j=1}^n S_j S_{n+1-j},\) \(S_1\equiv 1\), \(b\ge 0\) a real parameter; this reduces to (1) when \(b=0\). Unfortunately there are no known combinatorial interpretations of these new quantities even for integer \(b>0\), and this precludes obtaining detailed results like (2).