login
Non-plane increasing unary binary (0-1-2) trees where the nodes of outdegree 1 come in 2 colors.
4

%I #85 Aug 02 2023 18:16:31

%S 1,2,5,16,64,308,1730,11104,80176,643232,5676560,54650176,569980384,

%T 6401959328,77042282000,988949446144,13488013248256,194780492544512,

%U 2969094574403840,47640794742439936,802644553810683904,14166772337295285248,261410917571703825920

%N Non-plane increasing unary binary (0-1-2) trees where the nodes of outdegree 1 come in 2 colors.

%C 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

%C 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

%C 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

%H Vincenzo Librandi, <a href="/A131178/b131178.txt">Table of n, a(n) for n = 1..100</a>

%H Jean-Luc Baril, Sergey Kirgizov, Vincent Vajnovszki, <a href="https://arxiv.org/abs/1611.07793">Patterns in treeshelves</a>, arXiv:1611.07793 [cs.DM], 2016.

%H F. Bergeron, Ph. Flajolet and B. Salvy, <a href="http://algo.inria.fr/flajolet/Publications/BeFlSa92.pdf">Varieties of Increasing Trees</a>, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.

%H Lapo Cioni, Luca Ferrari, and Corentin Henriet. <a href="https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-039">A direct bijection between two-stack sortable permutations and fighting fish</a>, Euro. Conf. Comb., Graph Theory Appl. (2023) No. 12, 283-289.

%H D. Dominici, <a href="http://arxiv.org/abs/math/0501052">Nested derivatives: A simple method for computing series expansions of inverse functions.</a> arXiv:math/0501052v2 [math.CA], 2005.

%F 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!+....

%F From _Peter Bala_, Sep 01 2011: (Start)

%F 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).

%F 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.

%F (End)

%F 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

%F 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

%F a(n) ~ n! * 2^((n+3)/2) / log(3+2*sqrt(2))^(n+1). - _Vaclav Kotesovec_, Oct 08 2013

%F 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

%F 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

%e G.f. = x + 2*x^2 + 5*x^3 + 16*x^4 + 64*x^5 + 308*x^6 + 1730*x^7 + 11104*x^8 + ...

%e a(3) = 5: Denoting the two types of node of outdegree 1 by the letters a or b, the 5 possible trees are

%e .

%e . 1a 1b 1a 1b 1

%e . | | | | / \

%e . 2a 2b 2b 2a 2 3

%e . | | | |

%e . 3 3 3 3

%e - _Peter Bala_, Sep 01 2011

%p E:= (2*(exp(sqrt(2)*x)-1)) / ((2+sqrt(2))-(2-sqrt(2))*exp(sqrt(2)*x)):

%p S:= map(simplify,series(E,x,101)):

%p seq(coeff(S,x,j)*j!, j=1..100); # _Robert Israel_, Nov 23 2016

%t 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 *)

%o (PARI) x='x+O('x^66); /* that many terms */

%o default(realprecision,1000); /* working with floats here */

%o egf=(2*(exp(sqrt(2)*x)-1)) / ((2+sqrt(2))-(2-sqrt(2))*exp(sqrt(2)*x));

%o round(Vec(serlaplace(egf))) /* show terms */

%o /* _Joerg Arndt_, Sep 01 2011 */

%o (PARI) /* the following program should be preferred. */

%o Vec( serlaplace( serreverse( intformal( 1/(1+2*x+1/2*x^2) + O(x^66) ) ) ) )

%o \\ _Joerg Arndt_, Mar 01 2014

%o (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))};

%Y Cf. A000111, A000670, A008544, A008545, A029768, A080635, A278679

%K nonn,easy

%O 1,2

%A _Wenjin Woan_, Oct 31 2007

%E Terms >= 80176 from _Peter Bala_, Sep 01 2011

%E Changed offset to 1 to agree with name and example. - _Michael Somos_, Nov 23 2016