A054872 -id:A054872 - cp's OEIS frontend

A007564 Shifts left when INVERT transform applied thrice.

1, 1, 4, 19, 100, 562, 3304, 20071, 124996, 793774, 5120632, 33463102, 221060008, 1473830308, 9904186192, 67015401391, 456192667396, 3122028222934, 21467769499864, 148246598341018, 1027656663676600, 7148588698592956, 49884553176689584

Offset: 0

N. J. A. Sloane

More generally, coefficients of (1+m*x-sqrt(m^2*x^2-(2*m+2)*x+1))/(2*m*x) are given by a(n) = Sum_{k=0..n} (m+1)^k*N(n,k) where N(n,k) = (1/n)*binomial(n,k)*binomial(n,k+1) are the Narayana numbers (A001263). - Benoit Cloitre, May 24 2003
If y = x*A(x) then 3*y^2 - (1+2*x)*y + x = 0 and x = y*(1-3*y)/(1-2*y). - Michael Somos, Sep 28 2003
The sequence 0,1,4,19,... with g.f. (1-4*x-sqrt(1-8*x+4*x^2))/(6*x) and has a(n) = Sum_{k=0..floor((n-1)/2)} binomial(n-1,2k)*C(k)*4^(n-1-2*k)*3^k. a(n+1) = Sum_{k=0..floor(n/2)} binomial(n,2*k)*C(k)*4^(n-2*k)*3^k counts Motzkin paths of length n in which the level steps have 4 colors and the up steps have 3. It is the binomial transform of A107264 and corresponds to the series reversion of x/(1+4*x+3*x^2). - Paul Barry, May 18 2005
The Hankel transform of this sequence is 3^binomial(n+1,2). - Philippe Deléham, Oct 29 2007
a(n) is the number of Schroder paths of semilength n in which there are no (2,0)-steps at level 0 and at a higher level they come in 2 colors. Example: a(2)=4 because we have UDUD, UUDD, UBD, and URD, where U=(1,1), D=(1,-1), while B (R) is a blue (red) (2,0)-step. - Emeric Deutsch, May 02 2011
a(n) is the number of Schroder paths of semilength n-1 in which the (2,0)-steps at level 0 come in 3 colors and those at a higher level come in 2 colors. Example: a(3)=19 because, denoting  U=(1,1), H=(1,0), and D=(1,-1), we have 3^2 = 9 paths of shape HH, 3 paths of shape HUD, 3 paths of shape UDH, 2 paths of shape UHD, and 1 path of each of the shapes UDUD and UUDD. - Emeric Deutsch, May 02 2011
From David Callan, Jun 21 2013: (Start)
a(n) = number of (left) planted binary trees with n edges in which each vertex has a designated favorite neighbor. Planted binary trees are counted by the Catalan numbers A000108.
Example: for n=2, there are 2 planted binary trees: edges LL and LR from the root (L=left, R=right). Each has just one vertex with 2 neighbors, and so a(2)=4.
Proof outline: each vertex has 1,2 or 3 neighbors. Let X (resp. Y) denote the number of vertices with 2 (resp. 3) neighbors. Then X + 2Y = n - 1 (split the non-root edges into pairs with a common parent vertex and singletons). Thus the number of choices for designating favorite neighbors is 2^X * 3^Y = 2^(n-1)(3/4)^Y. The distribution for Y is known because, under the rotation correspondence, a.k.a. the deBruijn-Morselt bijection, vertices with 2 children in an n-edge planted binary tree correspond to DDUs in a Dyck path, and DDUs have the Touchard distribution (A091894) with gf F(x,y) = (1-2x+2xy - sqrt(1-4x+4x^2-4x^2 y))/(2xy). The desired g.f., Sum_{n>=1} a(n)*x^n, is therefore 1/2*(F(2x,3/4)-1). (End)

			G.f. = 1 + x + 4*x^2 + 19*x^3 + 100*x^4 + 562*x^5 + 3304*x^6 + 20071*x^7 + 124996*x^8 + ...

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0 to 100 by T. D. Noe)
C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, Generating functions for generating trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
Paul Barry and Aoife Hennessy, A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations, J. Int. Seq. 14 (2011), Article 11.3.8.
Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15 (2012), Article 12.4.8.
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version]
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
Z. Chen and H. Pan, Identities involving weighted Catalan-Schroder and Motzkin Paths, arXiv:1608.02448 arXiv:1608.02448 [math.CO], 2016. Eq. (1.13) a=1, b=3.
C. Coker, A family of eigensequences, Discrete Math. 282 (2004), 249-250.
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.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 443
Huyile Liang, Jeffrey Remmel, and Sainan Zheng, Stieltjes moment sequences of polynomials, arXiv:1710.05795 [math.CO], 2017, see page 11.
N. J. A. Sloane, Transforms

Cf. A047891, A054872.

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

a[0]=1; a[1]=1; a[n_]/;n>=2 := a[n] = a[n-1] + 3 Sum[a[k-1]a[n-k],{k,n-1}] ; Table[a[n],{n,0,10}] (* David Callan, Aug 25 2009 *)
Table[Hypergeometric2F1[-n, 1 - n, 2, 3], {n, 0, 22}] (* Arkadiusz Wesolowski, Aug 13 2012 *)
Table[(2^n (LegendreP[n+1, 2] - LegendreP[n-1, 2]) + 2 KroneckerDelta[n])/(6n+3), {n, 0, 20}] (* Vladimir Reshetnikov, Nov 01 2015 *)
CoefficientList[Series[(1+2x-Sqrt[1-8x+4x^2])/(6x),{x,0,30}],x] (* Harvey P. Dale, Feb 07 2016 *)

{a(n) = if( n<1, n==0, sum( k=0, n, 3^k * binomial( n, k) * binomial( n, k+1)) / n)} /* Michael Somos, Sep 28 2003 */

{a(n) = if( n<0, 0, n++; polcoeff( serreverse( x * (1 - 3*x) / (1 - 2*x) + x * O(x^n)), n))} /* Michael Somos, Sep 28 2003 */

a(n) = (2^n*(pollegendre(n+1,2)-pollegendre(n-1,2)) + 2*(n==0))/(6*n+3); \\ Michel Marcus, Nov 02 2015

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

G.f.: (1+2*x-sqrt(1-8*x+4*x^2))/(6*x). - Emeric Deutsch, Nov 03 2001
a(0)=1; for n>=1, a(n) = Sum_{k=0..n} 3^k*N(n,k) where N(n,k) = (1/n)*binomial(n, k)*binomial(n, k+1) are the Narayana numbers (A001263). - Benoit Cloitre, May 24 2003
a(n) = Sum_{k=0..n} A088617(n, k)*3^k*(-2)^(n-k). - Philippe Deléham, Jan 21 2004
With offset 1: a(1) = 1, a(n) = -2*a(n-1) + 3*Sum_{i=1..n-1} a(i)*a(n-i). - Benoit Cloitre, Mar 16 2004
D-finite with recurrence a(n) = (4*(2n-1)*a(n-1) - 4*(n-2)*a(n-2)) / (n+1) for n>=2, a(0) = a(1) = 1. - Philippe Deléham, Aug 19 2005
From Paul Barry, Dec 15 2008: (Start)
G.f.: 1/(1-x/(1-3x/(1-x/(1-3x/(1-x/(1-3x/(1-x/(1-3x........ (continued fraction).
The g.f. of a(n+1) is 1/(1-4x-3x^2/(1-4x-3x^2/(1-4x-3x^2/(1-4x-3x^2.... (continued fraction). (End)
a(0) = 1, for n>=1, 3a(n) = A047891(n). - Aoife Hennessy (aoife.hennessy(AT)gmail.com), Dec 02 2009
a(n) = upper left term in M^n, M = the production matrix:
1, 1
3, 3, 3
1, 1, 1, 1
3, 3, 3, 3, 3
1, 1, 1, 1, 1, 1
...
- Gary W. Adamson, Jul 08 2011
G.f.: A(x)= (1+2*x-sqrt(1-8*x+4*x^2))/(6*x)= 1/G(0); G(k)= 1 + 2*x - 3*x/G(k+1); (continued fraction, 1-step ). - Sergei N. Gladkovskii, Jan 05 2012
a(n) ~ sqrt(6+4*sqrt(3))*(4+2*sqrt(3))^n/(6*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 07 2012
a(n) = 2^n/sqrt(3)*LegendreP(n,-1,2) for n >= 1, where LegendreP is the associated Legendre function of the first kind, in Maple's notation. - Robert Israel, Mar 24 2015

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

Original entry on oeis.org

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

A121576 Riordan array (2-2x-sqrt(1-8x+4x^2), (1-2x-sqrt(1-8x+4x^2))/2).

Original entry on oeis.org

1, 2, 1, 6, 5, 1, 24, 24, 8, 1, 114, 123, 51, 11, 1, 600, 672, 312, 87, 14, 1, 3372, 3858, 1914, 618, 132, 17, 1, 19824, 22992, 11904, 4218, 1068, 186, 20, 1, 120426, 140991, 75183, 28383, 8043, 1689, 249, 23, 1, 749976, 884112, 481704, 190347, 58398, 13929, 2508, 321, 26, 1

Offset: 0

Paul Barry, Aug 08 2006

Inverse of Riordan array (1/(1+2*x), x*(1-x)/(1+2*x)).
Row sums are A047891; first column is A054872. Signed version given by A121575.
Triangle T(n,k), 0 <= k <= n, read by rows, given by [2, 1, 3, 1, 3, 1, 3, 1, 3, ...] DELTA [1, 0, 0, 0, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Aug 09 2006

			Triangle begins
     1;
     2,    1;
     6,    5,    1;
    24,   24,    8,   1;
   114,  123,   51,  11,   1;
   600,  672,  312,  87,  14,  1;
  3372, 3858, 1914, 618, 132, 17, 1;
From _Paul Barry_, Apr 27 2009: (Start)
Production matrix is
  2, 1,
  2, 3, 1,
  2, 3, 3, 1,
  2, 3, 3, 3, 1,
  2, 3, 3, 3, 3, 1,
  2, 3, 3, 3, 3, 3, 1,
  2, 3, 3, 3, 3, 3, 3, 1
In general, the production matrix of the inverse of (1/(1-rx),x(1-x)/(1-rx)) is
  -r, 1,
  -r, 1 - r, 1,
  -r, 1 - r, 1 - r, 1,
  -r, 1 - r, 1 - r, 1 - r, 1,
  -r, 1 - r, 1 - r, 1 - r, 1 - r, 1,
  -r, 1 - r, 1 - r, 1 - r, 1 - r, 1 - r, 1,
  -r, 1 - r, 1 - r, 1 - r, 1 - r, 1 - r, 1 - r, 1 (End)

G. C. Greubel, Rows n=0..100 of triangle, flattened

[[(&+[ 2^j*Binomial(n,j)*Binomial(2*n-k-j, n)*(4-9*j+3*j^2-6*(j-1)*n + 2*n^2)/((n-j+2)*(n-j+1))/2: j in [0..(n-k)]]): k in [0..n]]: n in [0..10]]; // G. C. Greubel, Nov 02 2018

Flatten[Table[Sum[Binomial[n,i]Binomial[2n-k-i,n](4-9i+3i^2-6(i-1)n+2n^2)/((n-i+2)(n-i+1))2^i,{i,0,n-k}]/2,{n,0,8},{k,0,n}]]
(* Emanuele Munarini, May 18 2011 *)

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

for(n=0,10, for(k=0,n, print1(sum(j=0, n-k, 2^j*binomial(n,j) *binomial(2*n-k-j, n)*(4-9*j+3*j^2-6*(j-1)*n + 2*n^2)/((n-j+2)*(n-j+1)))/2, ", "))) \\ G. C. Greubel, Nov 02 2018

T(n,k) = [x^(n-k)](1-2*x-2*x^2)*(1+2*x)^n/(1-x)^(n+1) = (1/2)*Sum_{i=0..n-k} binomial(n,i) * binomial(2*n-k-i,n) * (4 - 9*i + 3*i^2 - 6*(i-1)*n + 2*n^2)/((n-i+2)*(n-i+1))*2^i. - Emanuele Munarini, May 18 2011

A121575 Riordan array (-sqrt(4x^2+8x+1)+2x+2, (sqrt(4x^2+8x+1)-2x-1)/2).

Original entry on oeis.org

1, -2, 1, 6, -5, 1, -24, 24, -8, 1, 114, -123, 51, -11, 1, -600, 672, -312, 87, -14, 1, 3372, -3858, 1914, -618, 132, -17, 1, -19824, 22992, -11904, 4218, -1068, 186, -20, 1, 120426, -140991, 75183, -28383, 8043, -1689, 249, -23, 1, -749976, 884112, -481704, 190347, -58398, 13929, -2508, 321, -26, 1

Offset: 0

Paul Barry, Aug 08 2006

First column is (-1)^n*A054872(n). Row sums are a signed version of A108524. Inverse of generalized Delannoy triangle A121574. Unsigned triangle is A121576.

Triangle T(n,k), 0 <= k <= n, read by rows, given by [ -2, -1, -3, -1, -3, -1, -3, -1, -3, ...] DELTA [1, 0, 0, 0, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Aug 09 2006

			Triangle begins
     1;
    -2,    1;
     6,   -5,    1;
   -24,   24,   -8,   1;
   114, -123,   51, -11,   1;
  -600,  672, -312,  87, -14, 1;

G. C. Greubel, Rows n=0..100 of triangle, flattened

T:=Flat(List([0..9],n->List([0..n],k->(-1)^(n-k)*Sum([0..n-k],i->Binomial(n,i)*Binomial(2*n-k-i,n)*(4-9*i+3*i^2-6*(i-1)*n+2*n^2)/((n-i+2)*(n-i+1))*2^i)/2))); # Muniru A Asiru, Nov 02 2018

[[(-1)^(n-k)*(&+[ 2^j*Binomial(n,j)*Binomial(2*n-k-j, n)*(4-9*j+3*j^2-6*(j-1)*n + 2*n^2)/((n-j+2)*(n-j+1))/2: j in [0..(n-k)]]): k in [0..n]]: n in [0..10]]; // G. C. Greubel, Nov 02 2018

Flatten[Table[(-1)^(n-k)*Sum[Binomial[n, i] Binomial[2*n-k-i, n]*(4-9*i + 3*i^2 -6*(i-1)*n + 2*n^2)/((n-i+2)*(n-i+1))*2^i, {i, 0, n-k}]/2, {n, 0, 10}, {k, 0, n}]] (* G. C. Greubel, Nov 02 2018 *)

for(n=0,10, for(k=0,n, print1((-1)^(n-k)*sum(j=0, n-k, 2^j*binomial(n,j) *binomial(2*n-k-j, n)*(4-9*j+3*j^2-6*(j-1)*n + 2*n^2)/((n-j+2)*(n-j+1)))/2, ", "))) \\ G. C. Greubel, Nov 02 2018

T(n,k) = (-1)^(n-k)*(1/2)*Sum_{i=0..n-k} binomial(n,i) * binomial(2*n-k-i,n)*(4 - 9*i + 3*i^2 - 6*(i-1)*n + 2*n^2)/((n-i+2)*(n-i+1))*2^i. - G. C. Greubel, Nov 02 2018

A352687 Triangle read by rows, a Narayana related triangle whose rows are refinements of twice the Catalan numbers (for n >= 2).

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 4, 1, 0, 1, 7, 12, 7, 1, 0, 1, 11, 30, 30, 11, 1, 0, 1, 16, 65, 100, 65, 16, 1, 0, 1, 22, 126, 280, 280, 126, 22, 1, 0, 1, 29, 224, 686, 980, 686, 224, 29, 1, 0, 1, 37, 372, 1512, 2940, 2940, 1512, 372, 37, 1

Offset: 0

Peter Luschny, Apr 26 2022

This is the second triangle in a sequence of Narayana triangles. The first is A090181, whose n-th row is a refinement of Catalan(n), whereas here the n-th row of T is a refinement of 2*Catalan(n-1). We can show that T(n, k) <= A090181(n, k) for all n, k. The third triangle in this sequence is A353279, where also a recurrence for the general case is given.
Here we give a recurrence for the row polynomials, which correspond to the recurrence of the classical Narayana polynomials combinatorially proved by Sulanke (see link).
The polynomials have only real zeros and form a Sturm sequence. This follows from the recurrence along the lines given in the Chen et al. paper.
Some interesting sequences turn out to be the evaluation of the polynomial sequence at a fixed point (see the cross-references), for example the reversion of the Jacobsthal numbers A001045 essentially is -(-2)^n*P(n, -1/2).
The polynomials can also be represented as the difference between generalized Narayana polynomials, see the formula section.

			Triangle starts:
[0] 1;
[1] 0, 1;
[2] 0, 1,  1;
[3] 0, 1,  2,   1;
[4] 0, 1,  4,   4,   1;
[5] 0, 1,  7,  12,   7,   1;
[6] 0, 1, 11,  30,  30,  11,   1;
[7] 0, 1, 16,  65, 100,  65,  16,   1;
[8] 0, 1, 22, 126, 280, 280, 126,  22,  1;
[9] 0, 1, 29, 224, 686, 980, 686, 224, 29, 1;

Xi Chen, Arthur Li Bo Yang, James Jing Yu Zhao, Recurrences for Callan's Generalization of Narayana Polynomials, J. Syst. Sci. Complex (2021).
Peter Luschny, Illustration of the polynomials.
Robert A. Sulanke, The Narayana distribution, J. Statist. Plann. Inference, 2002, 101: 311-326, formula 2.

Cf. A090181 and A001263 (Narayana), A353279 (case 3), A000108 (Catalan), A145596, A172392 (central terms), A000124 (subdiagonal, column 2), A115143.
Essentially twice the Catalan numbers: A284016 (also A068875, A002420).
Values of the polynomial sequence: A068875 (row sums): P(1), A154955: P(-1), A238113: P(2)/2, A125695 (also A152681): P(-2), A054872: P(3)/2, P(3)/6 probable A234939, A336729: P(-3)/6, A082298: P(4)/5, A238113: 2^n*P(1/2), A154825 and A091593: 2^n*P(-1/2).

T := (n, k) -> if n = k then 1 elif k = 0 then 0 else
binomial(n, k)^2*(k*(2*k^2 + (n + 1)*(n - 2*k))) / (n^2*(n - 1)*(n - k + 1)) fi:
seq(seq(T(n, k), k = 0..n), n = 0..10);
# Alternative:
gf := 1 - x + (1 + y)*(1 - x*(y - 1) - sqrt((x*y + x - 1)^2 - 4*x^2*y))/2:
serx := expand(series(gf, x, 16)): coeffy := n -> coeff(serx, x, n):
seq(seq(coeff(coeffy(n), y, k), k = 0..n), n = 0..10);
# Using polynomial recurrence:
P := proc(n, x) option remember; if n < 3 then [1, x, x + x^2] [n + 1] else
((2*n - 3)*(x + 1)*P(n - 1, x) - (n - 3)*(x - 1)^2*P(n - 2, x)) / n fi end:
Trow := n -> seq(coeff(P(n, x), x, k), k = 0..n): seq(Trow(n), n = 0..10);
# Represented by generalized Narayana polynomials:
N := (n, k, x) -> add(((k+1)/(n-k))*binomial(n-k,j-1)*binomial(n-k,j+k)*x^(j+k), j=0..n-2*k): seq(print(ifelse(n=0, 1, expand(N(n,0,x) - N(n,1,x)))), n=0..7);

H[0, ] := 1; H[1, x] := x;
H[n_, x_] := x*(x + 1)*Hypergeometric2F1[1 - n, 2 - n, 2, x];
Hrow[n_] := CoefficientList[H[n, x], x]; Table[Hrow[n], {n, 0, 9}] // TableForm

from math import comb as binomial
def T(n, k):
    if k == n: return 1
    if k == 0: return 0
    return ((binomial(n, k)**2 * (k * (2 * k**2 + (n + 1) * (n - 2 * k))))
           // (n**2 * (n - 1) * (n - k + 1)))
def Trow(n): return [T(n, k) for k in range(n + 1)]
for n in range(10): print(Trow(n))

# The recursion with cache is (much) faster:
from functools import cache
@cache
def T_row(n):
    if n < 3: return ([1], [0, 1], [0, 1, 1])[n]
    A = T_row(n - 2) + [0, 0]
    B = T_row(n - 1) + [1]
    for k in range(n - 1, 1, -1):
        B[k] = (((B[k] + B[k - 1]) * (2 * n - 3)
               - (A[k] - 2 * A[k - 1] + A[k - 2]) * (n - 3)) // n)
    return B
for n in range(10): print(T_row(n))

Explicit formula (additive form):
T(n, n) = 1, T(n > 0, 0) = 0 and otherwise T(n, k) = binomial(n, k)*binomial(n - 1, k - 1)/(n - k + 1) - 2*binomial(n - 1, k)*binomial(n - 1, k - 2)/(n - 1).
Multiplicative formula with the same boundary conditions:
T(n, k) = binomial(n, k)^2*(k*(2*k^2 + (n + 1)*(n - 2*k)))/(n^2*(n-1)*(n- k + 1)).
Bivariate generating function:
T(n, k) = [x^n] [y^k](1 - x + (1+y)*(1-x*(y-1) - sqrt((x*y+x-1)^2 - 4*x^2*y))/2).
Recursion based on polynomials:
T(n, k) = [x^k] (((2*n - 3)*(x + 1)*P(n - 1, x) - (n - 3)*(x - 1)^2*P(n - 2, x)) / n) with P(0, x) = 1, P(1, x) = x, and P(2, x) = x + x^2.
Recursion based on rows (see the second Python program):
T(n, k) = (((B(k) + B(k-1)) * (2*n - 3) - (A(k) - 2*A(k-1) + A(k-2))*(n-3))/n), where A(k) = T(n-2, k) and B(k) = T(n-1, k), for n >= 3.
Hypergeometric representation:
T(n, k) = [x^k] x*(x + 1)*hypergeom([1 - n, 2 - n], [2], x) for n >= 2.
Row sums:
Sum_{k=0..n} T(n, k) = (2/n)*binomial(2*(n - 1), n - 1) = A068875(n-1) for n >= 2.
A generalization of the Narayana polynomials is given by
N{n, k}(x) = Sum_{j=0..n-2*k}(((k + 1)/(n - k)) * binomial(n - k, j - 1) * binomial(n - k, j + k) * x^(j + k)).
N{n, 0}(x) are the classical Narayana polynomials A001263 and N{n, 1}(x) is a shifted version of A145596 based in (3, 2). Our polynomials are the difference P(n, x) = N{n, 0}(x) - N{n, 1}(x) for n >= 1.
Let RS(T, n) denote the row sum of the n-th row of T, then RS(T, n) - RS(A090181, n) = -4*binomial(2*n - 3, n - 3)/(n + 1) = A115143(n + 1) for n >= 3.

cp's OEIS Frontend

A007564 Shifts left when INVERT transform applied thrice.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

PARI

Formula

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

A121576 Riordan array (2-2*x-sqrt(1-8*x+4*x^2), (1-2*x-sqrt(1-8*x+4*x^2))/2).

Views

Author

Keywords

Comments

Examples

Links

Programs

Magma

Mathematica

Maxima

PARI

Formula

A121575 Riordan array (-sqrt(4*x^2+8*x+1)+2*x+2, (sqrt(4*x^2+8*x+1)-2*x-1)/2).

Views

Author

Keywords

Comments

Examples

Links

Programs

GAP

Magma

Mathematica

PARI

Formula

A352687 Triangle read by rows, a Narayana related triangle whose rows are refinements of twice the Catalan numbers (for n >= 2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Python

Formula

A121576 Riordan array (2-2x-sqrt(1-8x+4x^2), (1-2x-sqrt(1-8x+4x^2))/2).

A121575 Riordan array (-sqrt(4x^2+8x+1)+2x+2, (sqrt(4x^2+8x+1)-2x-1)/2).