Comment on “The Expectation Of Independent Domination Number

Over Random Binary Trees”

L.H. Clark and J.P. McSorley Department of Mathematics Southern Illinois University Carbondale Carbondale, IL 62901-4408

Lee [3] purportedly derives an asymptotic formula for the expected independent domination number of a uniformly random binary tree. We review the derivation in [3] of an asymptotic formula for the expectation using the notation therein, then we point out and correct several errors in the derivation.

The number of binary trees with 2n + 1 vertices is

y_{2n+1} = \frac{\binom{2n}{n}}{n + 1}

Let μ(2n + 1) denote the expected value of the independent domination number of a binary tree chosen uniformly at random. The ordinary generating function for {μ(2n + 1) y_{2n+1}} is M = M(x) = ∑_{n=0}^{∞} μ(2n + 1) y_{2n+1} x^{2n+1}. Then

M(x) = \frac{2x}{\sqrt{1 − 4x^{2}} (1 + \sqrt{1 − 4x^{2}}) (2 − \sqrt{1 − 4x^{2}})} ,

hence,

\begin{matrix}M_{∗}(u) := & ∑_{n=0}^{∞} μ(2n + 1) y_{2n+1} u^{n} \\ = & \frac{2}{\sqrt{1 − 4u} (1 + \sqrt{1 − 4u}) (2 − \sqrt{1 − 4u})} . \end{matrix}

Then

A(u) = \frac{2}{(1 + \sqrt{1 − 4u}) (2 − \sqrt{1 − 4u})}

has power series in u with radius of convergence ρ_{1} = 1/4 which converges absolutely at u = 1/4, and,

B(u) = ∑_{n=0}^{∞} b_{n} u^{n} = \frac{1}{\sqrt{1 − 4u}} = ∑_{n=0}^{∞} (−4)^{n} \binom{−\frac{1}{2}}{n} u^{n}

has radius of convergence ρ_{2} = 1/4, b_{n} > 0 for all n, and lim_{n→∞} b_{n−1}/b_{n} = 1/4. At this point the following result in [3] is used.

“ To determine the asymptotic behavior of μ(2n + 1)/(2n + 1), we need the following lemma, which is a slight modification of Theorem 2 in [1]; we omit the proof.

Lemma 5. Let A(u) = ∑_{n=0}^{∞} a_{n} u^{n} and B(u) = ∑_{n=0}^{∞} b_{n} u^{n} be power series with radii of convergence ρ_{1} ≥ ρ_{2}, respectively. Suppose that A(u) converges absolutely at u = ρ_{1}. Suppose that b_{n} > 0 for all n and that b_{n−1}/b_{n} approaches a limit b as n → ∞. If ∑_{n=0}^{∞} c_{n} u^{n} = A(u) B(u), then c_{n} ∼ A(b) b_{n}. ”

The author then applies Lemma 5 to M_{∗}(u) = A(u) B(u) with ρ_{1} = ρ_{2} = 1/4 to find an asymptotic formula for μ(2n + 1) y_{2n+1}, hence, for μ(2n + 1).

Unfortunately Lemma 5, as we will demonstrate, is false in general for any ρ_{1} = ρ_{2} > 0 : the condition “ρ_{1} ≥ ρ_{2}” must be replaced with “ρ_{1} > ρ_{2}” and the condition “A(b) ≠ 0” must be added in which case the conditions “ A(u) converges absolutely at u = ρ_{1} ” and “ b_{n} > 0 for all n ” may be omitted. See Bender [1; Theorem 2] for a correct statement and a very brief indication of a proof or see Odlyzko [4; Theorem 7.1] for a correct statement without proof. Consequently, the derivation in [3] of an asymptotic formula for μ(2n + 1) is not valid.

Counter-examples to Lemma 5 for any ρ_{1} = ρ_{2} = r > 0 are readily found.

Fix r > 0. Let

A(u) = ∑_{n=0}^{∞} \frac{u^{n}}{r^{n} (n + 1)^{2}} = B(u)

which have radius of convergence r. Then A(u) converges absolutely on the circle of convergence |u| = r and A(r) = ζ(2) = π^{2}/6. In addition, b_{n} = 1/r^{n} (n + 1)^{2} > 0 for all n and lim_{n→∞} b_{n−1}/b_{n} = r. Here

A(u) B(u) = ∑_{n=0}^{∞} \{\frac{1}{r^{n}} ∑_{k=0}^{n} \frac{1}{(k + 1)^{2}(n − k + 1)^{2}} \} u^{n} = ∑_{n=0}^{∞} c_{n} u^{n}.

Further

\begin{matrix}∑_{k=0}^{n} \frac{(n + 2)^{2}}{(k + 1)^{2}(n − k + 1)^{2}} = & ∑_{k=0}^{n} \{\frac{1}{k + 1} + \frac{1}{n − k + 1}\}^{2} \\ = & 2 ∑_{k=0}^{n} \frac{1}{(k + 1)^{2}} + 2 ∑_{k=0}^{n} \frac{1}{(k + 1) (n − k + 1)}. \end{matrix}

Now f(x) = 1/(x + 1)(n − x + 1) decreases on [0, n/2] and increases on [n/2, n]. For integer Δ ∈ [1, n/2],

\begin{matrix}∑_{k=0}^{n} & \frac{1}{(k + 1) (n − k + 1)} \\ = & 2 ∑_{k=0}^{Δ−1} \frac{1}{(k + 1) (n − k + 1)} + ∑_{k=Δ}^{n−Δ} \frac{1}{(k + 1) (n − k + 1)} \\ ≤ & \frac{2 Δ}{n + 1} + \frac{n − 2 Δ + 1}{(Δ + 1)(n − Δ + 1)}. \end{matrix}

Setting Δ = ⌈\sqrt{n} ⌉, for example, gives

0 ≤ ∑_{k=0}^{n} \frac{1}{(k + 1) (n − k + 1)} ≤ \frac{2 \sqrt{n} + 2}{n + 1}+\frac{n − 2 \sqrt{n} + 1}{(\sqrt{n} + 1)(n − \sqrt{n})} → 0 as n → ∞.

Consequently,

\begin{matrix}r^{n} (n + 2)^{2} c_{n} = & ∑_{k=0}^{n} \frac{(n + 2)^{2}}{(k + 1)^{2}(n − k + 1)^{2}} \\ = & 2 ∑_{k=0}^{n} \frac{1}{(k + 1)^{2}} + 2 ∑_{k=0}^{n} \frac{1}{(k + 1) (n − k + 1)} \\ → & \frac{π^{2}}{3} as n → ∞, \end{matrix}

which implies

r^{n} (n + 1)^{2} c_{n} = \frac{(n + 1)^{2}}{(n + 2)^{2}} r^{n} (n + 2)^{2} c_{n} → \frac{π^{2}}{3} as n → ∞,

i.e.,

c_{n} ∼ 2 A(r) b_{n} as n → ∞

and not

c_{n} ∼ A(r) b_{n} as n → ∞

as claimed in Lemma 5 in [3] (r = b here). Further counter-examples are given by

A(u) = ∑_{n=0}^{∞} \frac{u^{n}}{r^{n} (n + 1)^{s}} = B(u) (s − 1 ∈ ℙ).

We now give a correct derivation of an asymptotic formula for μ(2n+1). Darboux’s Theorem (cf. Odlyzko [4; Theorem 11.7]) evidently does not apply since A(u) in [3] is not analytic in a neighborhood of u = 1/4 for any branch of \sqrt{1 − 4u}. We use a transfer theorem of Flajolet and Odlyzko [2; Theorem 5] (cf. Odlyzko [4; Section 11.1] for definitions, notation and statement of Theorem 11.4).

Consider the closed domain Δ = Δ(1, π/8, 1) and the function L(u) = 1 of slow variation at ∞. Then

M_{∗}(\frac{u}{4}) = \frac{2}{\sqrt{1 − u} (1 + \sqrt{1 − u}) ( 2 − \sqrt{1 − u})}

is analytic on Δ − {1} where we take the principal branch of the square root. Consequently,

M_{∗}(\frac{u}{4}) ∼ \frac{1}{\sqrt{1 − u}} = (1 − u)^{−1/2} L(\frac{1}{1 − u})

uniformly as u → 1 on Δ − {1}. Then Theorem 11.4 (C) of [4] implies

\frac{μ(2n + 1) y_{2n+1}}{4^{n}} = [u^{n}] M_{∗}(\frac{u}{4}) ∼ \frac{n^{−1/2}}{Γ(1/2)} L(n) = \frac{n^{−1/2}}{\sqrt{π}} as n → ∞.

Stirling’s Formula implies

\binom{2n}{n} = \frac{n^{−1/2} 4^{n}}{\sqrt{π}} (1 + o(1)) as n → ∞,

hence,

μ(2n + 1) ∼ n + 1 ∼ \frac{2n + 1}{2} as n → ∞.

References

1. E.A. Bender, Asymptotic Methods in Enumeration, SIAM Rev. 16 (1974), 485-515.

2. P. Flajolet and A.M. Odlyzko, Singularity Analysis of Generating Functions, SIAM J. Discrete Math. 3 (1990), 216-240.

3. C. Lee, The Expectation of Independent Domination Number over Random Binary Trees, Ars Combinatoria 56 (2000), 201-209.

4. A.M. Odlyzko, Asymptotic Enumeration Methods, in : Handbook of Combinatorics V.2, (R.L. Graham, M. Grötshel and L. Lovász Eds.), Elsevier Science B.V., New York, NY, 1995, pps. 1063–1229.