On a class of linked diagrams. II: Asymptotics
type: Item
instance of: scholarly article
title: On a class of linked diagrams. II: Asymptotics
zbMATH Open document ID: 0395.05003
DOI: 10.1016/0012-365X(78)90162-0
author: C. J. Everett
author: Paul R. Stein
published in: Discrete Mathematics
publication date: 1978-01-01T00:00:00Z
review text: 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\). Unfortuna…
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A16
Mathematics Subject Classification ID: 41A60
zbMATH DE Number: 3613044
zbMATH Keywords: class of linked diagrams
zbMATH Keywords: asymptotics
zbMATH Keywords: complete pairings
zbMATH Keywords: combinatorial model
MaRDI profile type: Publication
cites work: Asymptotic Methods in Enumeration
cites work: Proportions of Irreducible Diagrams
cites work: On a class of linked diagrams. I: Enumeration
description: scientific article; zbMATH DE number 3613044