Finch С-. R. Математические константы (2003), Finch St. R. Mathematical constants (CUP, 2003)(T)(618s).djvu:

Finch С-. R. Математические константы (2003)

Finch St. R. Mathematical constants (CUP, 2003)(T)(618s).djvu

Size 6.6Mb
Date Jun 22, 2005

Cites: The generating function for identity trees is [4,26]
= x+x7
A rooted identity tree is a rooted tree for which the identity map is the only automor-
automorphism that fixes the root...
Otter's Tree Enumeration Constants 305
5.6.4 Forests
Let /„ denote the number of non-isomorphic forests of order n; then the generating
function [26]
00
n=\
= x + 2x2 + 3x2 + 6x4 + \0x5 + 20x6 + 37x7 + 76.v8 + 153x9 + 329x10
satisfies
k=\ \d\k
and /o = 1 for the sake only of the latter formula...
The
generating function for 2-trees is [61]
00
n=0
= 1 +x+x2+2x3 + 5xA + \2x5 +39x6 + 136x7 + 529x8 + 2171*9 + • • •
oc
1
2kW(x2kJ x2kW(x4k)
W(x) + exp ( Y^ ^r{2xkW(x2k) + x2kW(x2kJ - x2kW(x4k))
1
where W(x) is the generating function for 2-trees with a distinguished and oriented
edge:
00
W(X) = J2 WnX"
n=0
= 1 + x + 3x2 + 10x3 + 39x4 + 160x5 + 702x6 + 3177x7+ 14830x8 + ¦ ¦ •
( xkW(xkJ
Further, w(x) has radius of convergence ^'=0.1770995223
E.6465426162...)"• and
= 0.0948154165...,
FF(x) = e~xW{xI W{x)...
The generating
function of leftist trees is [6,65,78,79]
n=0
= x + x2 + x3 + 2xA + Ax5 + Sx6 + llx1 + 38x8 + 87x9 + 203x10 +
I i oo oc
L(x) = x + -L(xJ +
m = \ m=l
where the auxiliary generating functions lm(x) satisfy
/ m-l \
= xL(x), lm+l(x) = Ux)[L(x)- Zk(x)\, m>2...
It can be shown [86-88] that this
process terminates, that is, x is a finite tree, with extinction probability 1 if p < 1/2
and 1 Ip — 1 if p > 1 /2...
Exact performance analyses of QF and QFW appear in [95-97], using random
graph theory and a variant of the Erdos-Renyi process...
Starting with Knuth's recursive formula for the Takeuchi numbers
n n-1
= Y"\("+k)-(n+k) k + Y"
1
k+\
and the somewhat related Bell numbers [5.7]
= 1, B2 = 2, B3=5, B4= 15, Bs =52,......
Define also xdj to be the smallest value of j for which \coj\ > r, for
any positive integer r...
Other occurrences of the interesting
constant p in the statistical literature are in [47-50]...
Holonomicity
A holonomic function (in the sense of Zeilberger [45,64,65]) is a solution f(z) of a
linear homogeneous differential equation
fn\z) + r1(z)/("-1)(z) + • ¦ ¦ + rn^(z)f'(z) + rn{z)f(z) = 0,
where each r*(z) is a rational function with rational coefficients...
A simple model for this phenomenon is a lattice gas, in which particles are placed
on the sites of a regular lattice and only adjacent particles interact...
Figure 5.14, for example, exhibits a graph of the mean density
for the hard hexagon case:
p(z) = z—(ln(/c(z)) =
dz
using the exact formulation given in [18]...
Constants Associated with Enumerating Discrete Structures
Needless to say, three-dimensional analogs of the models discussed here defy any
attempt at exact solution [44]...
The expected value of f(x, V) is, in the language of computer
science [1-3],
• the average number of comparisons required to find an existing random record x in
a data structure with n records,
• the average number of comparisons required to insert a new random record x into
a data structure with n records,
where it is presumed the data structure follows that of a binary search tree...
It can be proved here that T^ = c N + O(-/N), where [10]
ln(Ar) lnB)
-t^-t r-^ = 1.3531302722 .....
Noonan &
Zeilberger [10] improved the upper bound to A' ¦ 1.302128" for some constant A' > 0,
and obtained a non-rigorous estimate of the limit
S= lim s(n)' = 1.302......
A proof of
universality would encompass both site and bond cases on the square lattice, but this
has not yet been achieved...