|
|
A131178
|
|
Non-plane increasing unary binary (0-1-2) trees where the nodes of outdegree 1 come in 2 colors.
|
|
4
|
|
|
1, 2, 5, 16, 64, 308, 1730, 11104, 80176, 643232, 5676560, 54650176, 569980384, 6401959328, 77042282000, 988949446144, 13488013248256, 194780492544512, 2969094574403840, 47640794742439936, 802644553810683904, 14166772337295285248, 261410917571703825920
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
A labeled tree of size n is a rooted tree on n nodes that are labeled by distinct integers from the set {1,...,n}. An increasing tree is a labeled 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 labeled 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, Sep 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, Sep 01 2011
Number of plane increasing 0-1-2 trees, where the nodes of outdegree 1 come in 2 colors, avoiding pattern T213. See A278679 for more definitions and examples. - Sergey Kirgizov, Dec 24 2016
|
|
LINKS
|
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
|
|
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!+....
The generating function A(x) satisfies the autonomous differential equation A' = 1+2*A+1/2*A^2 with A(0) = 0. 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)
G.f.: 1/Q(0), where Q(k) = 1 - 2*x*(2*k+1) - m*x^2*(k+1)*(2*k+1)/( 1 - 2*x*(2*k+2) - m*x^2*(k+1)*(2*k+3)/Q(k+1) ) and m=1; (continued fraction). - Sergei N. Gladkovskii, Sep 24 2013
G.f.: 1/Q(0), where Q(k) = 1 - 2*x*(k+1) - 1/2*x^2*(k+1)*(k+2)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 02 2013
a(n) ~ n! * 2^((n+3)/2) / log(3+2*sqrt(2))^(n+1). - Vaclav Kotesovec, Oct 08 2013
G.f.: conjecture: T(0)/(1-2*x) -1, where T(k) = 1 - x^2*(k+1)*(k+2)/(x^2*(k+1)*(k+2) - 2*(1-2*x*(k+1))*(1-2*x*(k+2))/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 19 2013
E.g.f.: x/(T(0)-x), where T(k) = 4*k + 1 + x^2/(8*k+6 + x^2/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 30 2013
|
|
EXAMPLE
|
G.f. = x + 2*x^2 + 5*x^3 + 16*x^4 + 64*x^5 + 308*x^6 + 1730*x^7 + 11104*x^8 + ...
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
|
|
MAPLE
|
E:= (2*(exp(sqrt(2)*x)-1)) / ((2+sqrt(2))-(2-sqrt(2))*exp(sqrt(2)*x)):
S:= map(simplify, series(E, x, 101)):
|
|
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] (* 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 */
(PARI) /* the following program should be preferred. */
Vec( serlaplace( serreverse( intformal( 1/(1+2*x+1/2*x^2) + O(x^66) ) ) ) )
(PARI) {a(n) = if( n<1, 0, n! * polcoeff( 2 / (-2 + quadgen(8) * (-1 + 2 / (1 - exp(-quadgen(8) * x + x * O(x^n))))), n))};
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Changed offset to 1 to agree with name and example. - Michael Somos, Nov 23 2016
|
|
STATUS
|
approved
|
|
|
|