| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1517.1 | | ALLVAX::JROTH | I know he moves along the piers | Wed Nov 06 1991 11:18 | 7 |
| Sure does... look in Knuth for example.
(2n)!
f(n) = ----------
(n+1)! n!
- Jim
|
| 1517.2 | Next question... | BROKE::RAM | Ram Srinivasan @NUO, Nashua | Thu Nov 07 1991 18:08 | 26 |
|
OK, we have
f(2n+1) = (4n+2)!
--------------
(2n+2)! (2n+1)!
s(2n+1) = (2n)!
----------
(n+1)! (n)!
Here f(2n+1) represents the number of different binary trees that
may be constructed with (2n + 1) nodes, and s(2n+1) represents the
number of different strictly binary trees that may be constructed
with (2n + 1) nodes.
(A strictly binary tree is one in which every nonleaf node has
nonempty left and right subtrees. A strictly binary tree having
(2n+1) nodes will have (n+1) leaves and n nonleaf nodes.)
What is Lim s(n)/f(n) ?
n -> inf
(My hunch is it will be 0)
|
| 1517.3 | Stirling's formula! | HERON::BLOMBERG | Trapped inside the universe | Fri Nov 08 1991 03:59 | 4 |
|
It's a piece of cake using Stirling's formula for approximating n!.
The quotient seems to converge to zero, but you better check for
yourself.
|
| 1517.4 | | ELIS::GARSON | V+F = E+2 | Mon Nov 11 1991 04:38 | 28 |
| re .2
Let a(n) = s(2n+1)/f(2n+1)
(2n)! (2n+2)! (2n+1)!
so a(n) = ---------------------
(n+1)! n! (4n+2)!
Consider a(n+1)/a(n)
This is, after cancelling all the factorials from a(n),
(2n+2)(2n+1) (2n+4)(2n+3) (2n+3)(2n+2)
--------------------------------------
(n+2) (n+1) (4n+6)(4n+5)(4n+4)(4n+3)
It is obvious (EFTR) that this converges to 2^6/4^4 as n->oo i.e. converges
to 1/4
It is a theorem (if memory serves) that
If lim a(n+1)/a(n) exists, call it r, and |r| < 1 THEN
n->oo
lim a(n) exists and is 0.
n->oo
This confirms the result in .-1 (which used Stirling's approximation).
|