A025231 -id:A025231 - cp's OEIS frontend

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

Louis Shapiro

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

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

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

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

Cf. A006318, A121576, A054872.

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

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

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

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 */

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

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

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

More terms from Christian G. Bower, Dec 11 1999

A103970 Expansion of (1 - sqrt(1 - 4x - 12x^2))/(2*x).

Original entry on oeis.org

1, 4, 8, 32, 128, 576, 2688, 13056, 65024, 330752, 1710080, 8962048, 47497216, 254132224, 1370849280, 7447117824, 40707293184, 223731253248, 1235630948352, 6853893292032, 38166664839168, 213288826699776, 1195775593807872, 6723691157127168, 37908469021409280, 214260335517892608, 1213784937073737728, 6890689428042285056

Offset: 0

Paul Barry, Feb 23 2005

Image of c(x), the g.f. of the Catalan numbers A000108 under the mapping g(x) -> (1+3x)g(x(1+3x)). In general, the image of the Catalan numbers under the mapping g(x) -> (1+i*x)g(x(1+i*x)) is given by a(n) = Sum_{k=0..n} i^(n-k)*C(k)*C(k+1,n-k).
Hankel transform is 4^C(n+1,2)*A128018(n). [Paul Barry, Nov 20 2009]
By following L. Comtet [Analyse Combinatoire Tomes 1 et 2, PUF, Paris 1970], we also obtain (n+1)*C(n) - 2*a*(2*n-1)*C(n-1) + 4*(n-2)*(a^2-b)*C(n-2) = 0. In the present case, we also have the asymptotic result: a(n) ~ sqrt(4/3)*2^(n-1)*3^(n+1)/sqrt(Pi*n^3) for large n. - Richard Choulet, Dec 17 2009

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Cf. A025227, A025229, A103971, A103972.

Cf. A000108, A025228, A025230, A025231, A025232. [Richard Choulet, Dec 17 2009]

R:=PowerSeriesRing(Rationals(), 35); Coefficients(R!( (1-Sqrt(1-4*x-12*x^2))/(2*x) )); // G. C. Greubel, Mar 16 2019

n:=30:a(0):=1:a(1):=4: k:=1: for k from 1 to n do a(k+1):=sum('a(p)*a(k-p)','p'=0..k):od:seq(a(k),k=0..n); # Richard Choulet, Dec 17 2009
taylor(((1-(1-4*z-12*z^2)^0.5)/(2*z)),z=0,32); # Richard Choulet, Dec 17 2009

CoefficientList[Series[(1 - Sqrt[1-4x-12x^2])/(2x), {x, 0, 33}], x] (* Vincenzo Librandi, Aug 18 2017 *)

my(x='x+O('x^35)); Vec((1-sqrt(1-4*x-12*x^2))/(2*x)) \\ G. C. Greubel, Mar 16 2019

((1-sqrt(1-4*x-12*x^2))/(2*x)).series(x, 35).coefficients(x, sparse=False) # G. C. Greubel, Mar 16 2019

G.f.: (1 - sqrt(1-4*x*(1+3*x)))/(2*x).
a(n) = Sum_{k=0..n} 3^(n-k)*C(k)*C(k+1, n-k).
D-finite with recurrence: (n+1)*a(n) = 2*(2*n-1)*a(n-1) + 12*(n-2)*a(n-2). - Richard Choulet, Dec 17 2009

A103971 Expansion of (1 - sqrt(1 - 4x - 16x^2))/(2*x).

Original entry on oeis.org

1, 5, 10, 45, 190, 930, 4660, 24445, 131190, 719830, 4013260, 22684370, 129661740, 748252580, 4353379560, 25508284445, 150392391590, 891549228430, 5310994644060, 31775749689670, 190860711108740, 1150473009844380

Offset: 0

Paul Barry, Feb 23 2005

Image of c(x), the g.f. of the Catalan numbers A000108 under the mapping g(x) -> (1+4x)g(x(1+4x)). In general, the image of the Catalan numbers under the mapping g(x)->(1+i*x)g(x(1+i*x)) is given by a(n) = Sum_{k=0..n} i^(n-k)C(k)C(k+1,n-k).

More generally, the sequence C for which C(0)=a, C(1)=b and C(n+1) = sum(C(k)*C(n-k),k=0..n) has the following g.f. f: f(z) = (1-sqrt(1-4*z*(a-(a^2-b)*z)))/(2*z). We obtain: C(n)=(sum(-1)^(p-1)*2^{n-p}a^{n-2*p-1}*(a^2-b)^p*((2*n-2*p-1)*...*5*3*1/(p!*(n-2*p+1)!)),p=0..floor((n+1)/2)). By following Comtet [Analyse Combinatoire Tomes 1 et 2, PUF, Paris 1970], we obtain also: (n+1)*C(n) - 2*a*(2*n-1)*C(n-1) + 4*(n-2)*(a^2-b)*C(n-2) = 0. - Richard Choulet, Dec 17 2009

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cf. A000108, A025227, A025228, A025229, A025230, A025231, A025232. - Richard Choulet, Dec 17 2009

n:=30:a(0):=1:a(1):=5: for k from 1 to n do a(k+1):=sum('a(p)*a(k-p)','p'=0..k):od:seq(a(k),k=0..n); # Richard Choulet, Dec 17 2009

CoefficientList[Series[(1-Sqrt[1-4x-16x^2])/(2x),{x,0,30}],x] (* Harvey P. Dale, Apr 02 2012 *)

G.f.: (1-sqrt(1-4*x*(1+4*x)))/(2*x).
a(n) = Sum_{k=0..n} 4^(n-k)*C(k)*C(k+1, n-k).
Another recurrence formula: (n+1)*a(n) = 2*(2*n-1)*a(n-1) + 16*(n-2)*a(n-2). - Richard Choulet, Dec 17 2009
a(n) ~ sqrt(10 + 2*sqrt(5))*(2 + 2*sqrt(5))^n/(2*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 17 2012
Equivalently, a(n) ~ 5^(1/4) * 2^(2*n) * phi^(n + 1/2) / (sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 08 2021

A103972 Expansion of (1-sqrt(1-4x-20x^2))/(2*x).

Original entry on oeis.org

1, 6, 12, 60, 264, 1392, 7392, 41424, 236640, 1384512, 8224896, 49554816, 301884672, 1856878080, 11514915840, 71915838720, 451938731520, 2855705994240, 18132621772800, 115637702461440, 740356410961920, 4756888756101120, 30662391191715840, 198229520200704000, 1285001080928845824

Offset: 0

Paul Barry, Feb 23 2005

Image of c(x), the g.f. of the Catalan numbers A000108 under the mapping g(x)->(1+5x)g(x(1+5x)). In general, the image of the Catalan numbers under the mapping g(x)->(1+i*x)g(x(1+i*x)) is given by a(n)=sum{k=0..n, i^(n-k)C(k)C(k+1,n-k)}.

More generally, the sequence C for which C(0)=a, C(1)=b and C(n+1)=sum(C(k)*C(n-k),k=0..n) has the following G.f f: f(z)= (1-sqrt(1-4*z*(a-(a^2-b)*z)))/(2*z). We obtain: C(n)=(sum(-1)^(p-1)*2^{n-p}a^{n-2*p-1}*(a^2-b)^p*((2*n-2*p-1)*...*5*3*1/(p!*(n-2*p+1)!)),p=0..floor((n+1)/2)). By following L. Comtet [Analyse Combinatoire Tomes 1 et 2, PUF, Paris 1970], we obtain also: (n+1)*C(n)-2*a*(2*n-1)*C(n-1)+4*(n-2)*(a^2-b)*C(n-2)=0. - Richard Choulet, Dec 17 2009

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cf. A000108, A025227, A025228, A025229, A025230, A025231, A025232. [From Richard Choulet, Dec 17 2009]

n:=30:a(0):=1:a(1):=6 :for k from 1 to n do a(k+1):=sum('a(p)*a(k-p)','p'=0..k):od:seq(a(k),k=0..n); # Richard Choulet, Dec 17 2009

CoefficientList[Series[(1-Sqrt[1-4*x-20*x^2])/(2*x), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 17 2012 *)

x='x+O('x^66); Vec((1-sqrt(1-4*x-20*x^2))/(2*x)) \\ Joerg Arndt, May 13 2013

G.f.: (1-sqrt(1-4*x*(1+5*x)))/(2*x).
a(n) = Sum_{k=0..n} 5^(n-k)*C(k)*C(k+1, n-k).
Another recurrence formula: (n+1)*a(n)=2*(2n-1)*a(n-1)+20*(n-2)*a(n-2). - Richard Choulet, Dec 17 2009
a(n) ~ sqrt(12+2*sqrt(6))*(2+2*sqrt(6))^n/(2*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 17 2012

A379103 Expansion of (1-3x-sqrt(9x^2-14*x+1))/4.

Original entry on oeis.org

0, 1, 5, 35, 295, 2765, 27705, 290535, 3148995, 34995065, 396602605, 4566227435, 53259218495, 627982592965, 7473163652705, 89640387354735, 1082664905352795, 13155505626756465, 160709002086562005, 1972595405313408435, 24315686632846439895, 300886761671728853565, 3736205372071338170505, 46540791299676591116535

Offset: 0

Nathaniel Johnston, Dec 15 2024

Problem A6 on the 2024 William Lowell Putnam Mathematical Competition was to compute the Hankel transform of this sequence, which is A110147.

Given constants X and Y, let A(x) = (1 - x*(X - Y) - sqrt(1 - 2*x*(X + Y) + x^2*(X - Y)^2))/(2*Y) = x*(1) + x^2*(X) + x^3*X*(X + Y) + x^4*X*(X^2 + 3*X*Y + Y^2) + ... where the coefficients of A(x) is the Narayana triangle A090181. A(x) satisfies 0 = x - A(x)*(1 - x*(X-Y)) + A(x)^2*Y. The Hankel transform of the coefficients 1, X, X*(X + Y), ... is the sequence 1, (X*Y), (X*Y)^2, ... while the Hankel transform of X, X*(X + Y), X*(X^2 + 3*X*Y + Y^2), ... is the sequence X, X^3*Y, X^6*Y^3, X^10*Y^6, .... In the case of this sequence, X = 5 and Y = 2. - Michael Somos, Apr 26 2025

			G.f. = x + 5*x^2 + 35*x^3 + 295*x^4 + 2765*x^5 + 27705*x^6 + ... - _Michael Somos_, Apr 26 2025

Nathaniel Johnston, Determinant involving (1 - 3x - sqrt(1 - 14x + 9x^2))/4, YouTube video, 2024.
Nathaniel Johnston, Putnam 2024 A6 solution, 2024.

Cf. A025231, A047891, A082298, A110147.

a = 3;b = 2;c(1) = 1;last_val = 16;for j = 2:last_val
c(j) = a*c(j-1) + b*sum(c(1:j-1).*fliplr(c(1:j-1)));
end

a[ n_] := SeriesCoefficient[ (1 - 3*x - Sqrt[1 - 14*x + 9*x^2])/4, {x, 0, n}]; (* Michael Somos, Apr 26 2025 *)
a[ n_] := With[{X = 5, Y = 2}, SeriesCoefficient[ Nest[x/(1 - (X-Y)*x - Y*#)&, O[x], n], {x, 0, n}]]; (* Michael Somos, Apr 28 2025 *)
a[ n_] := With[{X = 5, Y = 2}, SeriesCoefficient[ Nest[x/(1 - X*x/(1 - Y*#))&, O[x], Ceiling[n/2]], {x, 0, n}]]; (* Michael Somos, Apr 28 2025 *)

my(x='x+O('x^33)); concat([0],Vec((1-3*x-sqrt(9*x^2-14*x+1))/4)) \\ Joerg Arndt, Dec 15 2024

a(n) = my(A = O(x)); for(k=1, n, A = x + 3*x*A + 2*A^2); polcoeff(A, n); /* Michael Somos, Apr 26 2025 */

a(n) = my(A = O(x), X = 5, Y = 2); for(k = 1, n, A = x/(1 - (X-Y)*x - Y*A)); polcoeff(A, n); /* Michael Somos, Apr 28 2025 */

a(n) = my(A = O(x), X = 5, Y = 2); for(k = 1, (n+1)\2, A = x/(1 - X*x/(1 - Y*A))); polcoeff(A, n); /* Michael Somos, Apr 28 2025 */

a(0) = 0, a(1) = 1, a(n) = 3*a(n-1) + 2*Sum_{k=0..n} a(k)*a(n-k) for n >= 2.
G.f.: (1-3*x-sqrt(9*x^2-14*x+1))/4.
G.f.: x/(1-5*x/(1-2*x/(1-5*x/(1-2*x/(1-5*x/(...)))))). - Thomas Scheuerle, Feb 28 2025
a(n) = (1/4)*(-1)^(n+1) * Sum_{k=0..n} binomial(1/2,k) * binomial(1/2,n-k) * (7+2*sqrt(10))^k * (7-2*sqrt(10))^(n-k) for n >= 2. - Ehren Metcalfe, Feb 26 2025
a(n) ~ 5^(1/4) * (7 + 2*sqrt(10))^(n - 1/2) / (2^(7/4) * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 27 2025
The g.f. A(x) satisfies 0 = x - (1 - 3*x)*A(x) + 2*A(x)^2 and A(x) = x + 3*x*A(x) + 2*A(x)^2. - Michael Somos, Apr 26 2025

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Maxima

PARI

PARI

Formula

Extensions

A103970 Expansion of (1 - sqrt(1 - 4*x - 12*x^2))/(2*x).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A103971 Expansion of (1 - sqrt(1 - 4*x - 16*x^2))/(2*x).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A103972 Expansion of (1-sqrt(1-4*x-20*x^2))/(2*x).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A379103 Expansion of (1-3*x-sqrt(9*x^2-14*x+1))/4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

Mathematica

PARI

PARI

PARI

PARI

Formula

A103970 Expansion of (1 - sqrt(1 - 4x - 12x^2))/(2*x).

A103971 Expansion of (1 - sqrt(1 - 4x - 16x^2))/(2*x).

A103972 Expansion of (1-sqrt(1-4x-20x^2))/(2*x).

A379103 Expansion of (1-3x-sqrt(9x^2-14*x+1))/4.