A151374 -id:A151374 - cp's OEIS frontend

A052701 a(0) = 0; for n >= 1, a(n) = 2^(n-1)*C(n-1), where C(n) = A000108(n) Catalan numbers, n>0.

0, 1, 2, 8, 40, 224, 1344, 8448, 54912, 366080, 2489344, 17199104, 120393728, 852017152, 6085836800, 43818024960, 317680680960, 2317200261120, 16992801914880, 125210119372800, 926554883358720, 6882979133521920

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

A151374 shifted one place right. - Joerg Arndt, Mar 17 2011
The number of rooted Eulerian n-edge maps in the plane (planar with a distinguished outside face). - Valery A. Liskovets, Mar 17 2005
This is also the number of strings of length 2n-2 of two different types of balanced parentheses. For example, a(2) = 2, since the two possible strings of length 2 are [] and (), a(3) = 8, since the 8 possible strings of length 4 are (()), [()], ([]), [[]], ()(), [](), ()[], and [][]. - Jeffrey Shallit, Jun 03 2006
Row sums of number triangle A110506. - Paul Barry, Jul 24 2005
Also row sums of triangle in A085880. - Philippe Deléham, Aug 01 2005
Row sums of number triangle A114608. - Philippe Deléham, Oct 15 2008

V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Jean-Luc Baril, Sergey Kirgizov, and Mehdi Naima, A lattice on Dyck paths close to the Tamari lattice, arXiv:2309.00426 [math.CO], 2023.
M. Bousquet-Mélou, Limit laws for embedded trees, arXiv:math/0501266 [math.CO], 2005.
Marek Bożejko, Maciej Dołęga, Wiktor Ejsmont, and Światosław R. Gal, Reflection length with two parameters in the asymptotic representation theory of type B/C and applications, arXiv:2104.14530 [math.RT], 2021.
F. Chapoton and S. Giraudo, Enveloping operads and bicoloured noncrossing configurations, arXiv:1310.4521 [math.CO], 2013.
Ivan Geffner and Marc Noy, Counting Outerplanar Maps, Electronic Journal of Combinatorics, Vol. 24, No. 2 (2017), Article P2.3.
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 651.
V. A. Liskovets and T. R. Walsh, Counting unrooted maps on the plane, Advances in Applied Math., Vol. 36, No.4 (2006), pp. 364-387.
Vincent Pilaud and V. Pons, Permutrees, arXiv preprint arXiv:1606.09643 [math.CO], 2016-2017.
Index to sequences related to reversion of series.

Limit of array A102544.

Cf. A000108, A003645, A025225, A052714, A195699.

spec := [S,{B=Union(C,Z),S=Union(B,C),C=Prod(S,S)},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);

InverseSeries[Series[y-2*y^2, {y, 0, 24}], x] (* then A(x)=y(x) *) (* Len Smiley, Apr 07 2000 *)
Join[{0},Table[2^n CatalanNumber[n],{n,0,30}]] (* Harvey P. Dale, Aug 29 2015 *)

a(n)=if(n<1,0,2^(n-1)*(2*n-2)!/(n-1)!/n!)

a(n)=if(n<1,0,polcoeff(serreverse(x-2*x^2+x*O(x^n)),n))

a(n)=if(n<1,0,polcoeff(2*x/(1+sqrt(1-8*x+O(x^n))),n))

a(n) = A052714(n)/n!.
a(n) = A003645(n-2)*2, n>1.
a(n) = 8^(n-1)*GAMMA(n-1/2)/GAMMA(n+1)/Pi^(1/2), n>0.
D-finite with recurrence: a(1)=1, (-4+8*n)*a(n) - (n+1)*a(n+1) = 0.
G.f.: (1-sqrt(1-8*x))/4 = x*C(2*x) where C(x) is g.f. for Catalan numbers, A000108.
G.f. A(x) satisfies 2*A(x)^2-A(x)+x=0, A(0)=0 and A(x)=x+2*A(x)^2=x/(1-2*A(x)). Series reversion of x-2*x^2. - Michael Somos, Sep 06 2003
a(0)=0, a(1)=1; a(n) = 2*Sum_{i=1..n-1} a(i)*a(n-i). - Benoit Cloitre, Mar 16 2004
With a different offset, a(0)=1, a(n) = Sum_{k=0..n} Sum_{j=0..n} (j*C(2n-j-1, n-j)*C(j, k)*2^(n-j)/n), n>0. - Paul Barry, Jul 24 2005
The Hankel transform of a(n+1) = [1,2,8,40,224,1344,...] is 4^C(n+1,2). - Philippe Deléham, Nov 06 2007
G.f.: x + 4*x^2/(G(0)-4*x) where G(k) = k*(8*x+1) + 4*x + 2 - 2*x*(2*k+3)*(2*k+4)/G(k+1) ; (continued fraction ). - Sergei N. Gladkovskii, Apr 05 2013
a(n) ~ 8^(n-1)/(sqrt(Pi)*n^(3/2)). - Ilya Gutkovskiy, Dec 04 2016
From Amiram Eldar, Mar 06 2022: (Start)
Sum_{n>=1} 1/a(n) = 68/49 + 96*arcsin(sqrt(1/8))/(49*sqrt(7)).
Sum_{n>=1} (-1)^(n+1)/a(n) = 20/27 - 16*log(2)/81. (End)
a(n) = A025225(n)/2 for n>=1. - Alois P. Heinz, Feb 16 2025

Better description from Claude Lenormand (claude.lenormand(AT)free.fr), Mar 19 2001

Additional comments from Michael Somos, Feb 24 2002

A162326 Let a(0) = a(1) = 1, and na(n) = 2(-7+5n)a(n-1) + 9(2-n)a(n-2) for n >= 2.

Original entry on oeis.org

1, 1, 3, 13, 71, 441, 2955, 20805, 151695, 1135345, 8671763, 67320573, 529626839, 4213228969, 33833367963, 273892683573, 2232832964895, 18314495896545, 151037687326755, 1251606057754605, 10416531069771111, 87029307323766681

Offset: 0

Georg Muntingh, Jul 01 2009

nonn

Let y = y(x) be implicitly defined by g(x,y(x)) = 0, with dg/dy not identically zero. For n >= 1, the sequence a(n) is the number of terms in the expansion of the divided difference [x0,...,xn]y in terms of bivariate divided differences of g.
(1 + 3*x + 13*x^2 + 71*x^3 + ...) = (1 + 4*x + 20*x^2 + 116*x^3 + ...) * 1/(1 + x + 4*x^2 + 20*x^3 + 116*x^4 + ...); where A082298 = (1, 4, 20, 116, 740, ...). - Gary W. Adamson, Nov 17 2011
The shifted sequence 1,3,13,71,... is the binomial transform of A151374. - Georg Muntingh, Jul 19 2012
a(n+1) is the number of Schröder paths of semilength n in which the (2,0)-steps come in 3 colors and with no peaks at level 1. - José Luis Ramírez Ramírez, Mar 31 2013
Define an infinite triangle by T(n,0)=1 and the other cells by T(n,k) = Sum_{c=0..k-1} T(n,c) + Sum_{r=k..n-1} T(r,k), the sum of the cells to the left and above a cell. The column k=1 contains A000079, the column k=2 essentially A001792. Then T(n,n)=a(n) on the diagonal. - J. M. Bergot, May 22 2013

			Write [0...n]y for [x0,...,xn]y and [0...s,0...t]g for [x0,...,xs;y0,...,yt]g.
For n = 1 one finds 1 term, [01]y = -[01;1]g/[0;01]g.
For n = 2 one finds 3 terms, [012]y = -[012;2]g/[0;02]g + ([01;12]g[12;2]g)/([0;02]g[1;12]g) - ([0;012]g[01;1]g[12;2]g)/([0;02]g[0;01]g[1;12]g).

Vincenzo Librandi, Table of n, a(n) for n = 0..300
Georg Muntingh, Implicit Divided Differences, Little Schroeder Numbers, and Catalan Numbers, J. Integ. Seqs., Vol. 15 (2012), Article 12.6.5.
Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 98.

Cf. A172003, which is a generalization to bivariate implicit functions.
Cf. A003262, which is the analogous sequence for implicit derivatives, and A172004 for its generalization to bivariate implicit functions.
Cf. A082298, A000108, A151374.

m:=20; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!( (5-Sqrt((1-9*x)/(1-x)))/4 )); // G. C. Greubel, Feb 07 2019

a:=[1,3]; for n in [3..21] do Append(~a,(2*(-7+5*n)*a[n-1] + 9*(2-n)*a[n-2]) div n); end for ; [1] cat a; // Marius A. Burtea, Jan 20 2020

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

a(n):=if n=0 then 1 else sum(binomial(n,k)*2^(n-k-1)*binomial(2*n-2*k-2,n-k-1),k,0,n)/n; /* Vladimir Kruchinin, Mar 13 2016 */

a(n) = if(n<2, 1, (2*(-7+5*n)*a(n-1) + 9*(2-n)*a(n-2))/n);
vector(25, n, a(n-1)) \\ Altug Alkan, Oct 06 2015

my(x='x+O('x^20)); Vec((5-sqrt((1-9*x)/(1-x)))/4) \\ G. C. Greubel, Feb 07 2019

L = [1, 1]
for n in range(2,22):
    L.append( ((-14 + 10*n)*L[-1] + (18-9*n)*L[-2])//n )
print(L)
# Georg Muntingh, Jul 19 2012

((5-sqrt((1-9*x)/(1-x)))/4).series(x, 20).coefficients(x, sparse=False) # G. C. Greubel, Feb 07 2019

Let E = N x N \ {(0,0), (0,1)} be a set of pairs of natural numbers. The number of terms a(n) is the coefficient of x^n*y^{n-1} of the generating function 1 - log(1 - Sum_{(s,t) in E} x^s*y^{s+t-1}) = 1 + Sum_{q >= 1} (Sum_{(s,t) in E} x^s*y^{s+t-1})^q / q.
From Georg Muntingh, Jul 19 2012: (Start)
a(n) = 2F1(1/2,1-n;2;-8), where 2F1 is the Gauss hypergeometric series.
G.f.: (5 - sqrt( (1-9*x)/(1-x) ))/4.
Quadratic recurrence relation: a(n) = 1 + 2*Sum_{m=1..n-1} a(m)*a(n-m).
(End)
a(n) ~ 3^(2*n+1)/(16*sqrt(2*Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 20 2012
a(n) = Sum_{k=0..n} (binomial(n,k)*2^(n-k-1)*binomial(2*n-2*k-2,n-k-1))/n, n>0, a(0)=1. - Vladimir Kruchinin, Mar 13 2016
From Peter Bala, Jan 19 2020: (Start)
a(n+1) = Sum_{k = 0..n} 2^k*C(n,k)*Catalan(k).
a(n+1) = (2/Pi) * Integral_{x = -1..1} (1 + 8*x^2)^n*sqrt(1 - x^2) dx.
O.g.f.: 1 + x/(1 - x)*c(2*x/(1-x)), where c(x) is the o.g.f. for A000108. (End)
Conjecture: a(n) = t_n for n > 0 with a(0) = 1 where we start with vector v of fixed length m with elements v_i = 1, then set t = v and for i=1..m-1, for j=i+1..m apply [v_i, v_j] := [v_i + 2*v_j, 2*v_i + v_j] (here square brackets mean that instead of sequentially assigning v_i and then v_j, we reserve their values (for example, as A = v_i, B = v_j) and then assign them in any order) and t_{i+1} := v_{i+1} (after ending each cycle for j). It also looks like that if we change 2*v_i to z*v_i it gives us a(n+1) = Sum_{k=0..n} A090981(n, k)*2^(n-k) for n >= 0. - Mikhail Kurkov, Aug 14 2024

Edited by Georg Muntingh, Jan 22 2010

A085880 Triangle T(n,k) read by rows: multiply row n of Pascal's triangle (A007318) by the n-th Catalan number (A000108).

Original entry on oeis.org

1, 1, 1, 2, 4, 2, 5, 15, 15, 5, 14, 56, 84, 56, 14, 42, 210, 420, 420, 210, 42, 132, 792, 1980, 2640, 1980, 792, 132, 429, 3003, 9009, 15015, 15015, 9009, 3003, 429, 1430, 11440, 40040, 80080, 100100, 80080, 40040, 11440, 1430, 4862, 43758, 175032, 408408, 612612, 612612, 408408, 175032, 43758, 4862

Offset: 0

N. J. A. Sloane, Aug 17 2003

Coefficients of terms in the series reversion of (1-k*x-(k+1)*x^2)/(1+x). - Paul Barry, May 21 2005
Equals A131427 * A007318 as infinite lower triangular matrices. [Philippe Deléham, Sep 15 2008]
Sum_{k=0..n} T(n,k)*x^k = A168491(n), A000007(n), A000108(n), A151374(n), A005159(n), A151403(n), A156058(n), A156128(n), A156266(n), A156270(n), A156273(n), A156275(n) for x = -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 respectively. - Philippe Deléham, Nov 15 2013
Diagonal sums are A052709(n+1). - Philippe Deléham, Nov 15 2013

			Triangle starts:
[ 1]     1;
[ 2]     1,     1;
[ 3]     2,     4,      2;
[ 4]     5,    15,     15,      5;
[ 5]    14,    56,     84,     56,     14;
[ 6]    42,   210,    420,    420,    210,     42;
[ 7]   132,   792,   1980,   2640,   1980,    792,    132;
[ 8]   429,  3003,   9009,  15015,  15015,   9009,   3003,    429;
[ 9]  1430, 11440,  40040,  80080, 100100,  80080,  40040,  11440,  1430;
[10]  4862, 43758, 175032, 408408, 612612, 612612, 408408, 175032, 43758, 4862;
...

G. C. Greubel, Rows n = 0..100 of triangle, flattened
Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.

Flat(List([0..10], n-> List([0..n], k-> Binomial(n,k)*Binomial(2*n,n)/( n+1) ))); # G. C. Greubel, Feb 07 2020

[Binomial(n,k)*Catalan(n): k in [0..n], n in [0..10]]; // G. C. Greubel, Feb 07 2020

seq(seq(binomial(n, k)*binomial(2*n, n)/(n+1), k = 0..n), n = 0..10); # G. C. Greubel, Feb 07 2020

Table[Binomial[n, k]*CatalanNumber[n], {n,0,10}, {k,0,n}]//Flatten (* G. C. Greubel, Feb 07 2020 *)

tabl(nn) = {for (n=0, nn, c =  binomial(2*n,n)/(n+1); for (k=0, n, print1(c*binomial(n, k), ", ");); print(););} \\ Michel Marcus, Apr 09 2015

[[binomial(n,k)*catalan_number(n) for k in (0..n)] for n in (0..10)] # G. C. Greubel, Feb 07 2020

Triangle given by [1, 1, 1, 1, 1, 1, ...] DELTA [1, 1, 1, 1, 1, 1, ...] where DELTA is Deléham's operator defined in A084938.
Sum_{k>=0} T(n, k) = A151374(n) (row sums). - Philippe Deléham, Aug 11 2005
G.f.: (1-sqrt(1-4*(x+y)))/(2*(x+y)). - Vladimir Kruchinin, Apr 09 2015

A054993 Number of "long curves", i.e., topological types of smooth embeddings of the oriented real line into the oriented plane that coincide with the standard immersion x -> (x,0) in the neighborhood of -infinity and +infinity.

Original entry on oeis.org

1, 2, 8, 42, 260, 1796, 13396, 105706, 870772, 7420836, 65004584, 582521748, 5320936416, 49402687392, 465189744448, 4434492302426, 42731740126228, 415736458808868, 4079436831493480, 40338413922226212, 401652846850965808, 4024556509468827432, 40558226664529024000, 410887438338905738908, 4182776248940752113344, 42770152711524569532616, 439143340987014152920384, 4526179842103708969039296

Offset: 0

Sergei Duzhin, Nov 11 2000

Also the number of knot diagrams with n crossings and two outgoing strings.

V. I. Arnold, Topological Invariants of Plane Curves and Caustics, American Math. Soc., 1994.
S. M. Gusein-Zade, On the enumeration of curves from infinity to infinity, in: Singularities and Bifurcations, Adv. Sov. Math., v. 21 (1994), pp. 189-198.

Steven R. Finch, Knots, links and tangles, August 8, 2003. [Cached copy, with permission of the author]
S. M. Gusein-Zade and F. S. Duzhin, On the number of topological types of plane curves; (Russian) Uspekhi Mat. Nauk 53 (1998), no. 3(321), 197-198. English translation: Russian Mathematical Surveys 53 (1998) 626-627. Related program and data.
J. L. Jacobsen and P. Zinn-Justin, A Transfer Matrix approach to the Enumeration of Knots
J. L. Jacobsen and P. Zinn-Justin, A Transfer Matrix approach to the Enumeration of Colored Links, J. Knot Theory, 10 (2001), 1233-1267.
Christoph Lamm, The enumeration of doubly symmetric diagrams for strongly positive amphicheiral knots, arXiv:2410.06601 [math.GT], 2024. See p. 14.
P. Zinn-Justin and J.-B. Zuber, Knot theory and matrix integrals, arXiv:1006.1812 [math-ph], 2010.
Index entries for sequences related to knots

Cf. A008980, A008981, A008982, A008983, A008984, A008985.
A151374 enumerates the long curves having Gauss diagrams without intersections, cf. A118814.
Cf. A067647, A067648.
A column of the triangles in A067640 and A062038.

Extended to n = 22 by J. L. Jacobsen and Paul Zinn-Justin, Jan 30 2002

More terms from Paul Zinn-Justin, Dec 13 2016

A156058 a(n) = 5^n * Catalan(n).

Original entry on oeis.org

1, 5, 50, 625, 8750, 131250, 2062500, 33515625, 558593750, 9496093750, 164023437500, 2870410156250, 50784179687500, 906860351562500, 16323486328125000, 295863189697265625, 5395152282714843750, 98911125183105468750, 1822047042846679687500

Offset: 0

Philippe Deléham, Feb 03 2009

From Joerg Arndt, Oct 22 2012: (Start)
Number of strings of length 2*n of five different types of balanced parentheses.
The number of strings of length 2*n of t different types of balanced parentheses is given by t^n * A000108(n): there are n opening parentheses in the strings, giving t^n choices for the type (the closing parentheses are chosen to match). (End)
Number of Dyck paths of length 2n in which the step U=(1,1) come in 5 colors. [José Luis Ramírez Ramírez, Jan 31 2013]

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

Cf. A000108, A005159, A085880, A151374, A151403.

[5^n*Catalan(n): n in [0..20]]; // Vincenzo Librandi, Jul 19 2011

A156058_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
for w from 1 to n do a[w] := 5*(a[w-1]+add(a[j]*a[w-j-1],j=1..w-1)) od; convert(a,list)end: A156058_list(16); # Peter Luschny, May 19 2011
A156058 := proc(n)
    5^n*A000108(n) ;
end proc: # R. J. Mathar, Oct 06 2012

Table[5^n CatalanNumber[n],{n,0,20}]  (* Harvey P. Dale, Mar 13 2011 *)

a(n) = 5^n*A000108(n).
From Gary W. Adamson, Jul 18 2011: (Start)
a(n) is the upper left term in M^n, M = the infinite square production matrix:
  5, 5, 0, 0, 0, 0,...
  5, 5, 5, 0, 0, 0,...
  5, 5, 5, 5, 0, 0,...
  5, 5, 5, 5, 5, 0,...
  ... (End)
E.g.f.: KummerM(1/2, 2, 20*x). - Peter Luschny, Aug 26 2012
D-finite with recurrence (n+1)*a(n) -10*(2*n-1)*a(n-1)=0. - R. J. Mathar, Oct 06 2012
G.f.: c(5*x) with c(x) the o.g.f. of A000108 (Catalan). - Philippe Deléham, Nov 15 2013
a(n) = Sum_{k=0..n} A085880(n,k)*4^k. - Philippe Deléham, Nov 15 2013
G.f.: 1/(1 - 5*x/(1 - 5*x/(1 - 5*x/(1 - ...)))), a continued fraction. - Ilya Gutkovskiy, Apr 19 2017
Sum_{n>=0} 1/a(n) = 410/361 + 600*arctan(1/sqrt(19)) / (361*sqrt(19)). - Vaclav Kotesovec, Nov 23 2021
Sum_{n>=0} (-1)^n/a(n) = 130/147 - 200*arctanh(1/sqrt(21)) / (147*sqrt(21)). - Amiram Eldar, Jan 25 2022

A060656 a(n) = 2a(n-1)a(n-2)/a(n-3), with a(0)=a(1)=1.

Original entry on oeis.org

1, 1, 2, 4, 16, 64, 512, 4096, 65536, 1048576, 33554432, 1073741824, 68719476736, 4398046511104, 562949953421312, 72057594037927936, 18446744073709551616, 4722366482869645213696, 2417851639229258349412352

Offset: 0

Henry Bottomley, Apr 18 2001

a(n+1) is the Hankel transform of A135052. - Paul Barry, Nov 15 2007
a(n+1) is the Hankel transform of the aerated large Schroeder numbers. a(n) and a(n+1) both satisfy the trivial Somos-4 recurrence u(n)=4*u(n-2)^2/u(n-4). Associated with the elliptic curve y^2=1-6x^2+x^4 via Schroeder numbers. - Paul Barry, Dec 08 2009
Hankel transform of A089324. - Paul Barry, Mar 01 2010
a(n+1) is the number of n X n binary matrices that are symmetric about both diagonals (bisymmetric). For the derivation of this result, see the link below. - Dennis P. Walsh, Apr 03 2014
1 followed by {a(n-1)}A078495).%20-%20_Vladimir%20Shevelev">(n>=1) is the Somos-3 sequence: b(0)=b(1)=b(2)=1;for n>=3, b(n)=2*b(n-1)*b(n-2)/b(n-3) (cf. comment in A078495). - _Vladimir Shevelev, Apr 20 2016
If the Hankel transform is defined as in the link 'Sequence transformations' then a(n) is the Hankel transform of A151374. - Peter Luschny, Nov 30 2016

			a(6) = 2*64*16/4 = 512.
G.f. = 1 + x + 2*x^2 + 4*x^3 + 16*x^4 + 64*x^5 + 512*x^6 + 4096*x^7 + ...

Harry J. Smith, Table of n, a(n) for n = 0..100
Peter Luschny, Sequence transformations
Dennis P. Walsh, Notes on binary bisymmetric matrices

Cf. A002416, A002620, A016116, A038754, A089324, A135052, A262666, A078495, A151374.

A060656:=n->2^floor(n^2/4); seq(A060656(n), n=0..20); # Wesley Ivan Hurt, Apr 30 2014

a[ n_] := 2^Quotient[n^2, 4]; (* Michael Somos, Jan 24 2014 *)
nxt[{a_,b_,c_}]:={b,c,(2c*b)/a}; NestList[nxt,{1,1,2},20][[All,1]] (* Harvey P. Dale, Nov 26 2017 *)

{ for (n=0, 100, write("b060656.txt", n, " ", 2^(n^2\4)); ) } \\ Harry J. Smith, Jul 09 2009

{a(n) = 2^(n^2\4)}; /* Michael Somos, Jan 24 2014 */

a(n) = 2^floor( n^2/4 ) = a(n - 1) * 2^floor( n/2 ) = a(n - 2) * 2^(n - 1) = a(n - 1) * A016116(n) = 2^A002620(n).
0 = a(n) * a(n+3) + a(n+1) * ( -2*a(n+2) ) for all n in Z. - Michael Somos, Jan 24 2014
0 = a(n) * a(n+4) + a(n+2) * ( -4*a(n+2) ) for all n in Z. - Michael Somos, Jan 24 2014

A089022 Number of walks of length 2n on the 3-regular tree beginning and ending at some fixed vertex.

Original entry on oeis.org

1, 3, 15, 87, 543, 3543, 23823, 163719, 1143999, 8099511, 57959535, 418441191, 3043608351, 22280372247, 164008329423, 1213166815047, 9012417249663, 67208553680247, 502920171632943, 3775020828459687, 28415858155984863, 214444848602732247, 1622146752543427983

Offset: 0

Paul Boddington, Nov 11 2003

The generating function for the corresponding sequence for the m-regular tree is 2*(m-1)/(m-2+m*sqrt(1-4*(m-1)*x)). When m=2 this reduces to the usual generating function for the central binomial coefficients.

Hankel transform is A133460. - Philippe Deléham, Dec 01 2007

			a(2) = 15 because there are 3*3=9 walks whose second step is to return to the starting vertex and 3*2=6 walks whose second step is to move away from the starting vertex.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Libor Caha and Daniel Nagaj, The pair-flip model: a very entangled translationally invariant spin chain, arXiv:1805.07168 [quant-ph], 2018.
Pakawut Jiradilok and Supanat Kamtue, Transportation Distance between Probability Measures on the Infinite Regular Tree, arXiv:2107.09876 [math.CO], 2021.
Ed Pegg Jr., K-Cayley Trees

Column k=3 of A183135.

A000602 := x -> 2^x*binomial(2*x, x)-9^x+1/3*2^x*binomial(2*x, x) * hypergeom([1, 2*x+1], [x+1], 2/3); # Tobias Friedrich (tfried(AT)mpi-inf.mpg.de), Jun 12 2007

Table[2^n*Binomial[2*n,n]-3^(n-1)*Sum[(2/3)^k*Binomial[n+k,n],{k,0,n-1}],{n,0,20}] (* or *)
CoefficientList[Series[4/(1+3*Sqrt[1-8*x]), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 17 2012 *)

my(x='x+O('x^30)); Vec(4/(1+3*sqrt(1-8*x))) \\ Joerg Arndt, May 10 2013

G.f.: 4/(1+3*sqrt(1-8*x)).
a(n) = 2^n * binomial(2*n,n) - 3^(n-1) * Sum_{j=0..n-1} (2/3)^j*binomial(n+j,n). - Tobias Friedrich (tfried(AT)mpi-inf.mpg.de), Jun 12 2007
a(n) = Sum_{k=0..n} A039599(n,k)*2^(n-k). - Philippe Deléham, Aug 25 2007
From Paul Barry, Sep 04 2009: (Start)
G.f.: 1/(1-3x/(1-2x/(1-2x/(1-2x/(1-2x/(1-... (continued fraction);
G.f.: (1-2*x*c(x))/(1-3*x-2*x*c(x)), where c(x) is the g.f. of A000108. (End)
a(n) = A126087(2n). - Philippe Deléham, Nov 02 2011
D-finite with recurrence n*a(n) + (12-17*n)*a(n-1) + 36*(2n-3)*a(n-2) = 0. - R. J. Mathar, Nov 14 2011
a(n) ~ 6*8^n/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 17 2012
From Karol A. Penson, Sep 06 2014: (Start)
a(n) is the (2*n)-th moment of a positive function W(x) = (3/Pi)*sqrt(8-x^2)/(9-x^2), on the segment x = (0,2*sqrt(2)): a(n) = Integral_{x=0..2*sqrt(2)} x^(2*n)*W(x) dx;
a(n) is the special value of hypergeometric function 2F1, in Maple notation: a(n)=2*8^n*GAMMA(n+1/2)*hypergeom([1,n+1/2],[n+2],8/9)/(3*sqrt(Pi)*(n+1)!). (End)
a(n) = A151374(n)*hypergeom([1,n+1/2],[n+2],8/9)*(2/3). - Peter Luschny, Sep 06 2014

A151281 Number of walks within N^2 (the first quadrant of Z^2) starting at (0,0) and consisting of n steps taken from {(-1, 0), (1, 0), (1, 1)}.

Original entry on oeis.org

1, 2, 6, 16, 48, 136, 408, 1184, 3552, 10432, 31296, 92544, 277632, 824448, 2473344, 7365120, 22095360, 65920000, 197760000, 590790656, 1772371968, 5299916800, 15899750400, 47578857472, 142736572416, 427357700096, 1282073100288, 3840133464064, 11520400392192, 34517383151616, 103552149454848

Offset: 0

Manuel Kauers, Nov 18 2008

From Paul Barry, Jan 26 2009: (Start)
Image of 2^n under A155761. Binomial transform is A129637. Hankel transform is 2^C(n+1,2).
In general, the g.f. of the reversion of x*(1+c*x)/(1+a*x+b*x^2) is given by the continued fraction x/(1 -(a-c)*x -(b-a*c+c^2)*x^2/(1 -(a-2*c)*x -(b-a*c+c^2)*x^2/(1 -(a-2*c)*x -(b-a*c+c^2)*x^2/(1 - .... (End)
a(n) is the number of nondeterministic Dyck meanders of length n. See A368164 or the de Panafieu-Wallner article for the definiton of nondeterministc walks. A nondeterministic meander contains at least one classical meander, i.e., a walk never crossing the x-axis. - Michael Wallner, Dec 18 2023

Robert Israel, Table of n, a(n) for n = 0..2000
Paul Barry, A Note on a One-Parameter Family of Catalan-Like Numbers, JIS 12 (2009) 09.5.4
A. Bostan, Computer Algebra for Lattice Path Combinatorics, Seminaire de Combinatoire Ph. Flajolet, March 28 2013.
A. Bostan and M. Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 [math.CO], 2008-2009.
Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, and Jean-Marie Maillard, Stieltjes moment sequences for pattern-avoiding permutations, arXiv:2001.00393 [math.CO], 2020.
M. Bousquet-Mélou and M. Mishna, 2008. Walks with small steps in the quarter plane, ArXiv 0810.4387.
Elie De Panafieu, Mohamed Lamine Lamali, and Michael Wallner, Combinatorics of nondeterministic walks of the Dyck and Motzkin type, arXiv:1812.06650 [math.CO], 2018.
Élie de Panafieu and Michael Wallner, Combinatorics of nondeterministic walks, arXiv:2311.03234 [math.CO], 2023.

Cf. A000108, A120730, A129637, A151374, A155761.

Cf. A368164 (nondeterministic Dyck bridges), A368234 (nondeterministic Dyck excursions).

[n le 3 select Factorial(n) else (3*n*Self(n-1) + 8*(n-3)*Self(n-2) - 24*(n-3)*Self(n-3))/n: n in [1..41]]; // G. C. Greubel, Nov 09 2022

N:= 1000: # to get terms up to a(N)
S:= series((sqrt(1-8*x^2)+4*x-1)/(4*x*(1-3*x)),x,N+1):
seq(coeff(S,x,j),j=0..N); # Robert Israel, Feb 18 2013

aux[i_, j_, n_] := Which[Min[i, j, n]<0 || Max[i, j]>n, 0, n==0, KroneckerDelta[i, j, n], True, aux[i, j, n]= aux[-1+i, -1+j, -1+n] +aux[-1+i, j, -1+n] +aux[1+i, j, -1+n]]; Table[Sum[aux[i,j,n], {i,0,n}, {j,0,n}], {n,0,25}]
a[n_]:= a[n]= If[n<3, (n+1)!, (3*(n+1)*a[n-1] +8*(n-2)*a[n-2] -24*(n-2)*a[n-3])/(n+1)]; Table[a[n], {n, 0, 30}] (* G. C. Greubel, Nov 09 2022 *)

def a(n): # a = A151281
    if (n==0): return 1
    elif (n%2==1): return 3*a(n-1) - 2^((n-1)/2)*catalan_number((n-1)/2)
    else: return 3*a(n-1)
[a(n) for n in (0..40)] # G. C. Greubel, Nov 09 2022

From Paul Barry, Jan 26 2009: (Start)
G.f.: 1/(1 -2*x -2*x^2/(1 -2*x^2/(1 -2*x^2/(1 -2*x^2/(1 -2*x^2/(1 - .... (continued fraction).
G.f.: c(2*x^2)/(1-2*x*c(2*x^2)) = (sqrt(1-8*x^2) + 4*x - 1)/(4*x*(1-3*x)).
a(n) = Sum_{k=0..n} ((k+1)/(n+k+1))*C(n, (n-k)/2)*(1 +(-1)^(n-k))*2^((n-k)/2)*2^k.
Reversion of x*(1 + 2*x)/(1 + 4*x + 6*x^2). (End)
From Philippe Deléham, Feb 01 2009: (Start)
a(n) = Sum_{k=0..n} A120730(n,k)*2^k.
a(2*n+2) = 3*a(2*n+1), a(2*n+1) = 3*a(2*n) - 2^n*A000108(n).
a(2*n+1) = 3*a(2*n) - A151374(n). (End)
(n+1)*a(n) = 3*(n+1)*a(n-1) + 8*(n-2)*a(n-2) - 24*(n-2)*a(n-3). - R. J. Mathar, Nov 26 2012
a(n) ~ 3^n/2. - Vaclav Kotesovec, Feb 13 2014

A369215 Expansion of (1/x) * Series_Reversion( x * ((1-x)^3-x) ).

Original entry on oeis.org

1, 4, 29, 261, 2627, 28315, 319648, 3731037, 44663058, 545312504, 6764556591, 85015779095, 1080185111768, 13852183882612, 179058158369828, 2330621446075640, 30519758687849439, 401806204894374041, 5315243189757111099, 70613088335938995385, 941714812929017751855

Offset: 0

Seiichi Manyama, Jan 16 2024

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..868
Index entries for reversions of series

Cf. A369114, A369161.
Cf. A151374, A249924, A369216.
Cf. A365764, A379171, A379172.
Cf. A049140.

CoefficientList[InverseSeries[Series[x((1-x)^3-x),{x,0,21}],x]/x,x] (* Stefano Spezia, Mar 31 2025 *)

my(N=30, x='x+O('x^N)); Vec(serreverse(x*((1-x)^3-x))/x)

a(n) = sum(k=0, n, binomial(n+k, k)*binomial(4*n+2*k+2, n-k))/(n+1);

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

A290605 Square array A(n,k), n>=0, k>=0, read by antidiagonals, where column k is the expansion of 2/(1 + sqrt(1 - 4kx)).

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 8, 5, 0, 1, 4, 18, 40, 14, 0, 1, 5, 32, 135, 224, 42, 0, 1, 6, 50, 320, 1134, 1344, 132, 0, 1, 7, 72, 625, 3584, 10206, 8448, 429, 0, 1, 8, 98, 1080, 8750, 43008, 96228, 54912, 1430, 0, 1, 9, 128, 1715, 18144, 131250, 540672, 938223, 366080, 4862, 0

Offset: 0

Ilya Gutkovskiy, Aug 07 2017

Number of 2n-length strings of balanced parentheses of at most k different types. Also number of binary trees with n inner nodes of at most k different dimensions. - Alois P. Heinz, Oct 28 2019

			G.f. of column k: A(x) = 1 + k*x + 2*k^2*x^2 + 5*k^3*x^3 + 14*k^4*x^4 + 42*k^5*x^5 + 132*k^6*x^6 + ...
Square array begins:
  1,   1,     1,      1,      1,       1,  ...
  0,   1,     2,      3,      4,       5,  ...
  0,   2,     8,     18,     32,      50,  ...
  0,   5,    40,    135,    320,     625,  ...
  0,  14,   224,   1134,   3584,    8750,  ...
  0,  42,  1344,  10206,  43008,  131250,  ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns k=0-10 give:  A000007, A000108, A151374, A005159, A151403, A156058, A156128, A156266, A156270, A156273, A156275.
Rows n=0-2 give: A000012, A001477, A001105.
Main diagonal gives A291699.
Cf. A000108, A253180, A256061.

ctln:= proc(n) option remember; binomial(2*n, n)/(n+1) end:
A:= proc(n, k) option remember; k^n*ctln(n) end:
seq(seq(A(n, d-n), n=0..d), d=0..10);  # Alois P. Heinz, Oct 28 2019

Table[Function[k, SeriesCoefficient[2/(1 + Sqrt[1 - 4 k x]), {x, 0, n}]][j - n], {j, 0, 10}, {n, 0, j}] // Flatten
Table[Function[k, SeriesCoefficient[1/(1 + ContinuedFractionK[-k x, 1, {i, 1, n}]), {x, 0, n}]][j - n], {j, 0, 10}, {n, 0, j}] // Flatten

A(n,k) = k^n*(2*n)!/(n!*(n + 1)!).
A(n,k) = k^n*A000108(n).
G.f. of column k: 2/(1 + sqrt(1 - 4*k*x)).
G.f. of column k: 1/(1 - k*x/(1 - k*x/(1 - k*x/(1 - k*x/(1 - k*x/(1 - ...)))))), a continued fraction.
E.g.f. of column k: (BesselI(0,2*k*x) - BesselI(1,2*k*x))*exp(2*k*x).
If g.f. = 2/(1 + sqrt(1 - 4*k*x)), then a(n) ~ k^n*4^n/(sqrt(Pi)*n^(3/2)).
A(n,k) = Sum_{i=0..k} binomial(k,i) * A256061(n,k-i). - Alois P. Heinz, Oct 28 2019
For fixed k >= 1, Sum_{n>=0} 1/A(n,k) = 2*k*(8*k + 1) / (4*k - 1)^2 + 24 * k^2 * arcsin(1/(2*sqrt(k))) / (4*k - 1)^(5/2). - Vaclav Kotesovec, Nov 23 2021
For fixed k >= 1, Sum_{n>=0} (-1)^n / A(n,k) = 2*k*(8*k - 1) / (4*k + 1)^2 - 24 * k^2 * log((1 + sqrt(4*k + 1))/(2*sqrt(k))) / (4*k + 1)^(5/2). - Vaclav Kotesovec, Nov 24 2021

cp's OEIS Frontend

A052701 a(0) = 0; for n >= 1, a(n) = 2^(n-1)*C(n-1), where C(n) = A000108(n) Catalan numbers, n>0.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

Extensions

A162326 Let a(0) = a(1) = 1, and n*a(n) = 2*(-7+5*n)*a(n-1) + 9*(2-n)*a(n-2) for n >= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Magma

Mathematica

Maxima

PARI

PARI

Python

Sage

Formula

Extensions

A085880 Triangle T(n,k) read by rows: multiply row n of Pascal's triangle (A007318) by the n-th Catalan number (A000108).

Views

Author

Keywords

Comments

Examples

Links

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A054993 Number of "long curves", i.e., topological types of smooth embeddings of the oriented real line into the oriented plane that coincide with the standard immersion x -> (x,0) in the neighborhood of -infinity and +infinity.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A156058 a(n) = 5^n * Catalan(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A060656 a(n) = 2*a(n-1)*a(n-2)/a(n-3), with a(0)=a(1)=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A162326 Let a(0) = a(1) = 1, and na(n) = 2(-7+5n)a(n-1) + 9(2-n)a(n-2) for n >= 2.

A060656 a(n) = 2a(n-1)a(n-2)/a(n-3), with a(0)=a(1)=1.

A290605 Square array A(n,k), n>=0, k>=0, read by antidiagonals, where column k is the expansion of 2/(1 + sqrt(1 - 4kx)).