A047891 Number of planar rooted trees with n nodes and tricolored end nodes.

1, 3, 12, 57, 300, 1686, 9912, 60213, 374988, 2381322, 15361896, 100389306, 663180024, 4421490924, 29712558576, 201046204173, 1368578002188, 9366084668802, 64403308499592, 444739795023054, 3082969991029800

Offset: 1

Author

Louis Shapiro

Keywords

• nonn
• eigen
• easy

Comments

Essentially the same as A025231.

Also number of lattice paths from (0,0) to (n-1,n-1), with steps (1,0),(0,1) and (1,1), that never rise above the line y=x and the steps (1,1) are colored red or blue. - Emeric Deutsch, May 28 2003

The Hankel transform (see A001906 for definition) of this sequence forms A049656(n+1) = [1, 3, 27, 729, 59049, 14348907, ...]. - Philippe Deléham, Aug 29 2006

With a(0)=0, this is the series reversion of x(1-x)/(1+2x). - Paul Barry, Oct 18 2009

Row sums of the Riordan matrix A121576. - Emanuele Munarini, May 18 2011

Examples

			G.f. = x + 3*x^2 + 12*x^3 + 57*x^4 + 300*x^5 + 1686*x^6 + 9912*x^7 + ...
		

References

• Lin Yang and S.-L. Yang, The parametric Pascal rhombus. Fib. Q., 57:4 (2019), 337-346.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..200
• Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
• Paul Barry, Generalized Catalan Numbers Associated with a Family of Pascal-like Triangles, J. Int. Seq., Vol. 22 (2019), Article 19.5.8.
• Paul Barry and A. Hennessy, A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations, J. Int. Seq. 14 (2011), Article 11.3.8.
• Veronica Bitonti, Bishal Deb, and Alan D. Sokal, Thron-type continued fractions (T-fractions) for some classes of increasing trees, arXiv:2412.10214 [math.CO], 2024. See p. 58.
• Zhi Chen and Hao Pan, Identities involving weighted Catalan-Schroder and Motzkin Paths, arXiv:1608.02448 [math.CO] (2016), eq. (1.13), a=3, b=1.
• Shishuo Fu and Yaling Wang, Bijective recurrences concerning two Schröder triangles, arXiv:1908.03912 [math.CO], 2019.
• Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
• Luis Verde-Star, A Matrix Approach to Generalized Delannoy and Schröder Arrays, J. Int. Seq., Vol. 24 (2021), Article 21.4.1.
• Eric Weisstein's MathWorld, Legendre Polynomial.
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A006318, A121576, A054872.

Programs

Magma

Q:=Rationals(); R:=PowerSeriesRing(Q, 40); Coefficients(R!((1-2*x-Sqrt(1-8*x+4*x^2))/(2*x))); // G. C. Greubel, Feb 10 2018

Maple

A047891_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
for w from 1 to n do a[w] := 3*a[w-1]+add(a[j]*a[w-j-1], j=1..w-1) od; convert(a,list)end: A047891_list(20); # Peter Luschny, May 19 2011

Mathematica

CoefficientList[Series[(1-2x-Sqrt[1-8x+4x^2])/(2x),{x,0,100}],x] (* Emanuele Munarini, May 18 2011 *)
a[ n_] := SeriesCoefficient[(1 - 2 x - Sqrt[1 - 8 x + 4 x^2]) / 2, {x, 0, n}]; (* Michael Somos, Apr 10 2014 *)
Table[2^(n-1) (LegendreP[n, 2] - LegendreP[n-2, 2])/(2n-1), {n, 1, 20}] (* Vladimir Reshetnikov, Nov 01 2015 *)
Table[3 Hypergeometric2F1[1-n, 2-n, 2, 3] - 2 KroneckerDelta[n-1], {n, 1, 20}] (* Vladimir Reshetnikov, Nov 01 2015 *)

Maxima

makelist(sum(binomial(n,k)*binomial(2*n-k+1,n+1)*(2*n^2-6*(k-1)*n+3*k^2-9*k+4)/((n-k+2)*(n-k+1))*2^k,k,0,n)/2,n,0,24); /* Emanuele Munarini, May 18 2011 */

PARI

a(n)=if(n<2,n==1,n--;sum(k=0,n,3^k*binomial(n,k)*binomial(n,k-1))/n)

PARI

x='x+O('x^100); Vec((1-2*x-sqrt(1-8*x+4*x^2))/2) \\ Altug Alkan, Nov 02 2015

Formula

G.f.: (1 - 2*x - sqrt(1 - 8*x + 4*x^2))/2.

For n>0, a(n+1) = (1/n)*Sum_{k=0..n} 3^k*C(n, k)*C(n, k-1) - Benoit Cloitre, May 10 2003

a(1)=1, a(n) = 2*a(n-1) + Sum_{i=1..(n-1)} a(i)*a(n-i). - Benoit Cloitre, Mar 16 2004

The Hankel transform (see A001906 for definition) of this sequence form A049656(n+1)= [1, 3, 27, 729, 59049, 14348907, ...]. - Philippe Deléham, Aug 29 2006

2*a(n) = A054872(n+1). - Philippe Deléham, Aug 17 2007

From Paul Barry, Feb 01 2009: (Start)

G.f.: x/(1-2x-x/(1-2x-x/(1-2x-x/(1-2x-x/(1-... (continued fraction);

a(n+1) = Sum_{k=0..n} C(n+k,2k)*2^(n-k)*A000108(k). (End)

G.f.: x/(1-3x/(1-x/(1-3x/(1-x/(1-3x/(1-x/(1-3x/(1-... (continued fraction). - Paul Barry, Oct 18 2009

a(1) = 1, for n>=1, a(n+1) = 3*A007564(n). - Aoife Hennessy (aoife.hennessy(AT)gmail.com), Dec 02 2009

From Emanuele Munarini, May 18 2011: (Start)

a(n+1) = (Sum_{k=0..n} binomial(n,k)*binomial(2*n-k+1,n+1)*(2*n^2-6*(k-1)*n+3*k^2-9*k+4)/((n-k+2)*(n-k+1))*2^k)/2.

D-finite with recurrence: (n+2)*(n+3)*a(n+3) - 6*(n+2)^2*a(n+2) - 12*(n)^2*a(n+1) + 8*n*(n-1)*a(n) = 0. (End)

G.f.: A(x) = (1-2*x-sqrt(4*x^2-8*x+1))/2 = 1 - G(0); G(k)= 1 + 2*x - 3*x/G(k+1); (continued fraction, 1-step). - Sergei N. Gladkovskii, Jan 05 2012

G.f.: x/W(0), where W(k)= k+1 - 2*x*(k+1) - x*(k+1)*(k+2)/W(k+1); (continued fraction). - Sergei N. Gladkovskii, Aug 16 2013

From Vladimir Reshetnikov, Nov 01 2015: (Start)

a(n) = 2^(n-1)*(LegendreP_n(2) - LegendreP_{n-2}(2))/(2n-1).

a(n) = 3*hypergeom([1-n,2-n], [2], 3) - 2*0^(n-1). (End)

a(n) = 2^(n-1)*hypergeom([1-n, n], [2], -1/2). - Peter Luschny, Nov 25 2020

a(n) ~ 3^(1/4) * (1 + sqrt(3))^(2*n - 1) / (2*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jul 31 2021

D-finite with recurrence n*a(n) +4*(-2*n+3)*a(n-1) +4*(n-3)*a(n-2)=0. - R. J. Mathar, Aug 01 2022

Extensions

More terms from Christian G. Bower, Dec 11 1999