|
| |
|
|
A131178
|
|
Non-plane increasing unary binary (0-1-2) trees where the nodes of outdegree 1 come in 2 colors.
|
|
0
| |
|
|
1, 2, 5, 16, 64, 308, 1730, 11104, 80176, 643232, 5676560, 54650176, 569980384, 6401959328, 77042282000, 988949446144, 13488013248256, 194780492544512, 2969094574403840, 47640794742439936, 802644553810683904, 14166772337295285248, 261410917571703825920, 5033382489699061571584, 100954321277297505243136
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| A labelled tree of size n is a rooted tree on n nodes that are labelled by distinct integers from the set {1,...,n}. An increasing tree is a labelled tree such that the sequence of labels along any branch starting at the root is increasing. Thus the root of an increasing tree will be labelled 1. In unary binary trees (sometimes called 0-1-2 trees) the outdegree of a node is either 0, 1 or 2. Here we are counting non-plane (where the subtrees stemming from a node are not ordered between themselves) increasing unary binary trees where the nodes of outdegree 1 come in two colors. An example is given below. [Peter Bala, Sept 01 2011]
The number of plane increasing 0-1-2 trees on n nodes, where the nodes of outdegree 1 come in two colors, is equal to n!. Other examples of sequences counting increasing trees include A000111, A000670, A008544, A008545, A029768 and A080635. [Peter Bala, Sept 01 2011]
|
|
|
LINKS
| F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1922, pp. 24-48.
D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA]
|
|
|
FORMULA
| E.g.f.: A(x) = (2*(exp(sqrt(2)*x)-1)) / ((2+sqrt(2))-(2-sqrt(2))*exp(sqrt(2)*x)) = x+2*x^2/2!+5*x^3/3!+16*x^4/4!+64*x^5/5!+....
From Peter Bala, Sept 01 2011: (Start)
The generating function A(x) satisfies the autonomous differential equation A' = 1+2*A+1/2*A^2 with A(0) = 1. It follows that the inverse function A(x)^-1 may be expressed as an integral A(x)^-1 = int {t = 0..x} 1/(1+2*t+1/2*t^2).
Applying [Dominici, Theorem 4.1] to invert the integral gives the following method for calculating the terms of the sequence: let f(x) = 1+2*x+1/2*x^2. Let D be the operator f(x)*d/dx. Then a(n) = D^n(f(x)) evaluated at x = 0. Compare with A000111(n+1) = D^n(1+x+x^2/2!) evaluated at x = 0
(End)
|
|
|
EXAMPLE
| a(3) = 5: Denoting the two types of node of outdegree 1 by the letters a or b, the 5 possible trees are
...................................
...1a....1b....1a....1b........1...
...|.....|.....|.....|......../.\..
...2a....2b....2b....2a......2...3.
...|.....|.....|.....|.............
...3.....3.....3.....3.............
[Peter Bala, Sept 01 2011]
|
|
|
MATHEMATICA
| max = 25; f[x_] := (2*(Exp[Sqrt[2]*x] - 1))/((2 + Sqrt[2]) - (2 - Sqrt[2])*Exp[Sqrt[2]*x]); Drop[ Simplify[ CoefficientList[ Series[f[x], {x, 0, max}], x]*Range[0, max]!], 1] (* From Jean-François Alcover, Oct 05 2011 *)
|
|
|
PROG
| (PARI) x='x+O('x^66); /* that many terms */
default(realprecision, 1000); /* working with floats here */
egf=(2*(exp(sqrt(2)*x)-1)) / ((2+sqrt(2))-(2-sqrt(2))*exp(sqrt(2)*x));
round(Vec(serlaplace(egf))) /* show terms */
/* Joerg Arndt, Sep 01 2011 */
|
|
|
CROSSREFS
| A000111, A000670, A008544, A008545, A029768, A080635.
Sequence in context: A178119 A185998 A127083 * A003149 A027046 A000522
Adjacent sequences: A131175 A131176 A131177 * A131179 A131180 A131181
|
|
|
KEYWORD
| nonn,easy
|
|
|
AUTHOR
| Wenjin Woan (wjwoan(AT)hotmail.com), Oct 31 2007
|
|
|
EXTENSIONS
| Terms >=80176 from Peter Bala, Sept 01 2011.
|
| |
|
|
