cp's OEIS Frontend

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

%I A131178 #85 Aug 02 2023 18:16:31
%S A131178 1,2,5,16,64,308,1730,11104,80176,643232,5676560,54650176,569980384,
%T A131178 6401959328,77042282000,988949446144,13488013248256,194780492544512,
%U A131178 2969094574403840,47640794742439936,802644553810683904,14166772337295285248,261410917571703825920
%N A131178 Non-plane increasing unary binary (0-1-2) trees where the nodes of outdegree 1 come in 2 colors.
%C A131178 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 A131178 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 A131178 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 A131178 Vincenzo Librandi, <a href="/A131178/b131178.txt">Table of n, a(n) for n = 1..100</a>
%H A131178 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 A131178 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 A131178 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 A131178 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 A131178 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 A131178 From _Peter Bala_, Sep 01 2011: (Start)
%F A131178 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 A131178 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 A131178 (End)
%F A131178 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 A131178 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 A131178 a(n) ~ n! * 2^((n+3)/2) / log(3+2*sqrt(2))^(n+1). - _Vaclav Kotesovec_, Oct 08 2013
%F A131178 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 A131178 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 A131178 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 A131178 a(3) = 5: Denoting the two types of node of outdegree 1 by the letters a or b, the 5 possible trees are
%e A131178 .
%e A131178 .  1a    1b    1a    1b      1
%e A131178 .  |     |     |     |      / \
%e A131178 .  2a    2b    2b    2a    2   3
%e A131178 .  |     |     |     |
%e A131178 .  3     3     3     3
%e A131178 - _Peter Bala_, Sep 01 2011
%p A131178 E:=  (2*(exp(sqrt(2)*x)-1)) / ((2+sqrt(2))-(2-sqrt(2))*exp(sqrt(2)*x)):
%p A131178 S:= map(simplify,series(E,x,101)):
%p A131178 seq(coeff(S,x,j)*j!, j=1..100); # _Robert Israel_, Nov 23 2016
%t A131178 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 A131178 (PARI) x='x+O('x^66); /* that many terms */
%o A131178 default(realprecision,1000); /* working with floats here */
%o A131178 egf=(2*(exp(sqrt(2)*x)-1)) / ((2+sqrt(2))-(2-sqrt(2))*exp(sqrt(2)*x));
%o A131178 round(Vec(serlaplace(egf))) /* show terms */
%o A131178 /* _Joerg Arndt_, Sep 01 2011 */
%o A131178 (PARI) /* the following program should be preferred. */
%o A131178 Vec( serlaplace( serreverse( intformal( 1/(1+2*x+1/2*x^2) + O(x^66) ) ) ) )
%o A131178 \\ _Joerg Arndt_, Mar 01 2014
%o A131178 (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 A131178 Cf. A000111, A000670, A008544, A008545, A029768, A080635, A278679
%K A131178 nonn,easy
%O A131178 1,2
%A A131178 _Wenjin Woan_, Oct 31 2007
%E A131178 Terms >= 80176 from _Peter Bala_, Sep 01 2011
%E A131178 Changed offset to 1 to agree with name and example. - _Michael Somos_, Nov 23 2016