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

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

Size 6.6Mb
Date Jun 22, 2005

Hence the phrase
"random binary tree" is sometimes ambiguous in the literature: The sample space has
Bn elements for the former person but Bw")/(« + 1) elements for the latter! We cannot
hope here to survey the role of trees in computer algorithms, only to provide a few
constants...
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...
In particular, when q = 2,
we have ce = 7.3719688014 ...,co = 7.3719494907..., and
A n(n+\)
where r = 0.7759021363 ...,A = 0.8008134543 ..., and
Q = Y\ A - yk ) = 0.2887880950.....
We assume that the
program is memoryless in the sense that previously computed results are not available at
any time in the future...
lattices (as opposed to the simple cubic lattice), but we will not discuss these or other
generalizations [9]...
Hughes [3,20] examined the conditional mean time to return to the origin
(conditional upon return eventually occurring)...
Let H be the first positive value
of Sj, called the first ladder height of the process; then the moments of H when /x = 0
are [46]
= 4=...
For small d, we have bounds [1,25,31]
exp(Cn]/2) ifd = 2,
exp (Cn2W+V in(«)) if 3 < </ < 4,
which do not come close to proving the existence of A...
An important challenge, therefore, is to better understand the
nature of such exponents and ratios, and certainly to prove their existence in low
dimensions...
Zeilberger, The Goulden-Jackson cluster method: Extensions, applica-
applications and implementations, J...
This may appear
to be hopelessly idealized, as rigid molecules could not possibly satisfy such strict
symmetry requirements...
Elaborate numerical computations [7,44,45] have shown that, in the limit as n —*¦
oo,
zc = 3.7962 .....
Now, over all integers x, define the recursive function
f(x,V) =
0
if V = 0
@ is the empty vector),
\+f(x, Vi) ifx < v\, otherwise {v\ is the first vector component),
l+f(x,VR) i
Clearly 0 < f(x, V) < k always and the ordering of v\, vi, ..., Vk is crucial
in determining the value of /(x, V), For example, /G, C, 9, 5, 1, 7)) = 4 and
/D, C, 9, 5, 1,7)) = 3...
This is a hint that search/insertion algorithms on digital search trees
are, on average, more efficient than on binary search trees...
There is double randomness here as with binary search trees [5.13], but note that x
depends on M more intricately than before...
Consider
the integer time series Xq,X\, ..., X^ defined recursively by
1 if « = 0,
Xn = { I l+X,-! with probability 2~x"-i...
The best-known es-
estimate, obtained via series expansion analysis by differential approximants [11], is
a = 4.062570 A more precise asymptotic expression for A(n) is
A(n)
0.316915.....
For example, the permutation re = B, 7, 4, 1,
6, 3, 9, 5, 8) has longest increasing subsequences B, 4, 6, 9) and A, 3, 5, 8); hence
?o =4...
Johansson, Discrete orthogonal polynomial ensembles and the Plancherel measure,
Annals of Math...
Here is an in-
inequality [4] valid for all k > 3:
3 2* / 2k \~]
-y < rc(k) < lnB) • In ( — j ~ lnB) - 2k...
Therefore x(^) occurs when evaluating a second
derivative with respect to u>, specifically, when computing the variance of P (defined
momentarily)...
A more difficult analysis allows us to compute the corresponding two moments of
P and also to see more vividly the significance of magnetic susceptibility and critical
exponents...
Let un denote the
number of ways of coloring the vertices of the square lattice with three colors so that
no two adjacent vertices are colored alike...