A005159 -id:A005159 - cp's OEIS frontend

A354734 a(0) = a(1) = 1; a(n) = 3 * Sum_{k=0..n-2} a(k) * a(n-k-2).

1, 1, 3, 6, 21, 54, 189, 558, 1944, 6210, 21681, 72576, 254988, 878850, 3112101, 10935000, 39030660, 139001346, 499808232, 1797731496, 6506661798, 23583173328, 85847830965, 313063862436, 1145325387114, 4197826175634, 15424343762184, 56774049331356, 209400739623054

Offset: 0

Ilya Gutkovskiy, Jun 04 2022

nonn

Cf. A005159, A007477, A354733, A354735, A354736.

a[0] = a[1] = 1; a[n_] := a[n] = 3 Sum[a[k] a[n - k - 2], {k, 0, n - 2}]; Table[a[n], {n, 0, 28}]
nmax = 28; CoefficientList[Series[(1 - Sqrt[1 - 12 x^2 (1 + x)])/(6 x^2), {x, 0, nmax}], x]

G.f. A(x) satisfies: A(x) = 1 + x + 3 * (x * A(x))^2.
G.f.: (1 - sqrt(1 - 12 * x^2 * (1 + x))) / (6 * x^2).
a(n) ~ sqrt((2+3*r)*(1+r)) / (sqrt(Pi) * n^(3/2) * r^n), where r = 2*cos(arccos(1/8)/3)/3 - 1/3. - Vaclav Kotesovec, Jun 04 2022

A006849 Number of strongly self-dual planar maps with 2n edges.

Original entry on oeis.org

2, 9, 69, 567, 5112, 48114, 469179, 4691115, 47849940, 495893502, 5206886874, 55273052646, 592211326464, 6395881806180, 69555215111319, 761015877850035, 8371174661041500, 92523509359662150, 1027010953940099238

Offset: 1

N. J. A. Sloane

A planar map is called strongly self-dual if it is self-dual with respect to an orientation-preserving duality. - Valery A. Liskovets, May 27 2006

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

Gheorghe Coserea, Table of n, a(n) for n = 1..200
V. A. Liskovets, Enumeration of nonisomorphic planar maps, Selecta Math. Sovietica, 4 (No. 4, 1985), 303-323.

Cf. A005159, A000108, A005470.

With[{nn = 21}, CoefficientList[InverseSeries[Series[2*x/(12*x^2 + 12*x + 3), {x, 0, nn}]] + InverseSeries[Series[2*x/(12*x^2 + 1), {x, 0, nn}]], x]] (* Gheorghe Coserea, Aug 15 2015 *)
a[n_] := 3^n*CatalanNumber[n]/2 + If[OddQ[n], 3^((n-1)/2)*CatalanNumber[(n-1)/2]/2, 0]; Array[a, 20] (* Jean-François Alcover, Jan 17 2018 *)

C = n -> binomial(2*n, n) / (n + 1);
a(n) = if (n%2, ( 3^n*C(n) + 3^((n-1)/2)*C((n-1)/2) )/2, 3^n*C(n)/2);
apply(n -> a(n), vector(30, i, i)) \\ Gheorghe Coserea, Aug 04 2015

x='x + O('x^33); Vec(-1/2 + 1/(1 + (1 - 12*x)^(1/2)) + x/(1 + (1 - 12*x^2)^(1/2))) \\ Gheorghe Coserea, Aug 15 2015

a(2k) = 3^(2k)C(2k)/2=A005159(2k)/2 (4k edges, k>0) and a(2k-1) = (3^(2k-1)C(2k-1)+3^(k-1)C(k-1))/2 =(A005159(2k-1)+A005159(k-1))/2 (4k-2 edges, k>0) where C(n) = A000108(n) (Catalan numbers). - Valery A. Liskovets, May 27 2006

G.f.: -1/2 + 1/(1 + (1 - 12*x)^(1/2)) + x/(1 + (1 - 12*x^2)^(1/2)). - Gheorghe Coserea, Aug 15 2015

More terms from Valery A. Liskovets, May 27 2006

A103937 Number of unrooted n-edge maps in the plane (planar map with a distinguished outside face).

Original entry on oeis.org

1, 2, 6, 26, 150, 1032, 8074, 67086, 586752, 5317226, 49592424, 473357994, 4606116310, 45554761836, 456848968518, 4637014782748, 47563495004742, 492422043299964, 5140194991046122, 54053208147441474, 572191817441284272, 6093471300213162072, 65245904156725935906

Offset: 0

Valery A. Liskovets, Mar 17 2005

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

Andrew Howroyd, Table of n, a(n) for n = 0..500
V. A. Liskovets and T. R. Walsh, Counting unrooted maps on the plane, Advances in Applied Math., 36, No.4 (2006), 364-387.

Antidiagonal sums of A380240.

Cf. A005159, A006384.

a[n_] := (1/(2n)) (3^n Binomial[2n, n]/(n+1) + Sum[Boole[0Jean-François Alcover, Aug 28 2019 *)

a(n) = {if(n==0, 1, (3^n*binomial(2*n,n)/(n+1) + sumdiv(n, k, if(kAndrew Howroyd, Jan 22 2025

a(n)=(1/(2n))[3^n*binomial(2n, n)/(n+1) +sum_{0A000010, q(n)=0 if n is even and q(n)=3^((n-1)/2)binomial(n-1, (n-1)/2)/(n+1) if n is odd.

a(0)=1 prepended by Andrew Howroyd, Jan 21 2025

A122871 Expansion of (1 - 2x - sqrt(1 - 4x - 8x^2))/(6x^2).

Original entry on oeis.org

1, 2, 7, 26, 106, 452, 1999, 9074, 42046, 198044, 945430, 4564100, 22243060, 109285256, 540738943, 2692103714, 13475973238, 67784600108, 342439638418, 1736727343436, 8839203054604, 45132514680248, 231121351433158

Offset: 0

Paul Barry, Sep 16 2006

Series reversion of x/(1+2x+3x^2). Binomial transform is A107264. Counts colored Motzkin paths. Second binomial transform of 1,0,3,0,18,0,... or 3^n*binomial(n) (A005159) with interpolated zeros.

Hankel transform is 3^binomial(n+1,2). - Paul Barry, Oct 01 2009

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from Vincenzo Librandi)
Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
Serkan Demiriz, Adem Şahin, and Sezer Erdem, Some topological and geometric properties of novel generalized Motzkin sequence spaces, Rendiconti Circ. Mat. Palermo Ser. 2 (2025) Vol. 74, No. 136. See p. 4.
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.

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

x='x+O('x^50); Vec((1 - 2*x - sqrt(1 - 4*x - 8*x^2))/(6*x^2)) \\ G. C. Greubel, Mar 19 2017

def A122871_list(n):  # n>=1
    T = [0]*(n+1); R = [1]
    for m in (1..n-1):
        a,b,c = 1,0,0
        for k in range(m,-1,-1):
            r = a + 2*b + 3*c
            if k < m : T[k+2] = u;
            a,b,c = T[k-1],a,b
            u = r
        T[1] = u; R.append(u)
    return R
A122871_list(23)  # Peter Luschny, Nov 01 2012

E.g.f.: exp(2*x)*Bessel_I(1, sqrt(3)*2*x)/(sqrt(3)x).
a(n) = Sum_{k=0..floor(n/2)} binomial(n,2*k)*binomial(k)3^k*2^(n-2k).
G.f.: 1/(1-2x-3x^2/(1-2x-3x^2/(1-2x-3x^2/(1-2x-3x^2/(1-.... (continued fraction). - Paul Barry, Oct 01 2009
D-finite with recurrence: (n+2)*a(n) - 2*(2n+1)*a(n-1) + 8*(1-n)*a(n-2) = 0. - R. J. Mathar, Nov 14 2011
a(n) ~ 2*sqrt(9+5*sqrt(3))*(2+2*sqrt(3))^n/(3*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 19 2012

A316598 a(n) is the number of rooted quadrangulations of the projective plane with n vertices.

Original entry on oeis.org

5, 38, 331, 3098, 30330, 306276, 3163737, 33252050, 354312946, 3817498004, 41510761346, 454882507468, 5017662052868, 55664182358808, 620592559670979, 6949200032479746, 78117065527443654, 881170275583541004, 9970663315885385502, 113137928354523348300

Offset: 1

Gheorghe Coserea, Jul 08 2018

nonn

Gheorghe Coserea, Table of n, a(n) for n = 1..301
Stavros Garoufalidis, Marcos Marino, Universality and asymptotics of graph counting problems in nonorientable surfaces, arXiv:0812.1195 [math.CO], 2008-2009.
E. Krasko, A. Omelchenko, Enumeration of r-regular Maps on the Torus. Part I: Enumeration of Rooted and Sensed Maps, arXiv:1709.03225 [math.CO], 2017.
E. Krasko, A. Omelchenko, Enumeration of r-regular maps on the torus. Part I: Rooted maps on the torus, the projective plane and the Klein bottle. Sensed maps on the torus, Discrete Mathematics, Volume 342, Issue 2, February 2019, Pages 584-599.

Cf. A005159, A007137, A278120.

(-6*x + 3*Sqrt[1-12*x] - 2*Sqrt[-36*x + 6*Sqrt[1-12*x] + 3] + 3)/(6*x^2) + O[x]^20 // CoefficientList[#, x]& (* Jean-François Alcover, Feb 24 2019 *)

seq(N) = {
  my(x='x + O('x^(N+2)), c=(1-sqrt(1-12*x))/(6*x));
  Vec((1 - x - 3*x*c - sqrt(1 - 4*x - 4*x*c))/x);
};
seq(20)
\\ test: y='x*Ser(seq(300), 'x); 0 == 3*x^3*y^4 + (12*x^3 - 6*x^2)*y^3 + (18*x^3 + 24*x^2 + x)*y^2 + (12*x^3 + 66*x^2 + 8*x - 2)*y + (3*x^3 + 36*x^2 + 10*x)

G.f. A(x) = (1-x-3*x*c - sqrt(1-4*x-4*x*c))/x, where c=(1-sqrt(1-12*x))/(6*x). (see eqn. (117) in Garoufalidis link)
G.f. y=A(x) satisfies:
0 = 3*x^3*y^4 + 6*x^2*(2*x - 1)*y^3 + x*(18*x^2 + 24*x + 1)*y^2 + 2*(6*x^3 + 33*x^2 + 4*x - 1)*y + x*(3*x^2 + 36*x + 10).
0 = 13*x*(4*x + 1)*(12*x - 1)^3*y''''' + (36864*x^4 + 3840*x^3 + 8832*x^2 + 1556*x - 65)*(12*x - 1)^2*y'''' + 16*(248832*x^4 - 5184*x^3 + 29799*x^2 + 2418*x - 259)*(12*x - 1)*y''' + 72*(1382400*x^4 - 201600*x^3 + 144312*x^2 - 4157*x - 492)*y'' + 144*(276480*x^3 - 51840*x^2 + 31488*x - 979)*y' + 165888*y.
0 = x*(4*x + 1)*(48*x^2 - 6*x + 1)*(12*x - 1)^3*y'''' + 2*(10368*x^4 + 12*x^2 + 47*x - 2)*(12*x - 1)^2*y''' + 6*(86400*x^4 - 10800*x^3 + 2472*x^2 + 132*x - 19)*(12*x - 1)*y'' + (2488320*x^4 - 622080*x^3 + 186192*x^2 - 10728*x - 144)*y' + (10368*x - 648)*y.
a(n) ~ 2^(2*n + 1/2) * 3^(n + 1/2)/ (Gamma(3/4) * n^(5/4)) * (1 - sqrt(3) * Gamma(3/4) / (sqrt(2*Pi) * n^(1/4))). - Vaclav Kotesovec, Oct 04 2019

A345189 Number of rows with the value "false" in the Kleene truth tables of all bracketed formulae with n distinct propositions p1, ..., pn connected by the binary connective of implication.

Original entry on oeis.org

1, 1, 6, 41, 330, 2882, 26604, 255313, 2521986, 25473638, 261898548, 2731724778, 28836047844, 307477681188, 3306988334808, 35833139582529, 390803960909106, 4286644113507902, 47258491871201508, 523372307883323566, 5819831138546794860, 64954314678710555612, 727371707764232349672

Offset: 1

Michel Marcus, Jun 10 2021

nonn

G. C. Greubel, Table of n, a(n) for n = 1..925
Volkan Yildiz, Notes on algebraic structure of truth tables of bracketed formulae connected by implications, arXiv:2106.04728 [math.CO], 2021.

Cf. A005159 (unknown rows, shifted), A025226 (all rows), A345190 (true rows).

CoefficientList[Series[(-2 -Sqrt[1-12*x] +Sqrt[5 +24*x +4*Sqrt[1-12*x]])/6, {x, 0, 40}], x]//Rest (* G. C. Greubel, May 20 2022 *)

my(x='x+O('x^30)); Vec((-2-sqrt(1-12*x)+sqrt(5+24*x+4*sqrt(1-12*x)))/6)

def A345189_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (-2-sqrt(1-12*x)+sqrt(5+24*x+4*sqrt(1-12*x)))/6 ).list()
a=A345189_list(40); a[1:] # G. C. Greubel, May 20 2022

G.f.: (-2-sqrt(1-12*x)+sqrt(5+24*x+4*sqrt(1-12*x)))/6.

a(n) = 2*A005159(n-1) - A345190(n). - G. C. Greubel, May 20 2022

A345190 Number of rows with the value "true" in the Kleene truth tables of all bracketed formulae with n distinct propositions p1, ..., pn connected by the binary connective of implication.

Original entry on oeis.org

1, 5, 30, 229, 1938, 17530, 165852, 1621133, 16242474, 165923854, 1721675460, 18095802306, 192256162740, 2061367432212, 22276538889912, 242387718986301, 2653259550491034, 29198054511893638, 322835545567447092, 3584671507685675894, 39955514234936341980, 446897274497509974508

Offset: 1

Michel Marcus, Jun 10 2021

nonn

G. C. Greubel, Table of n, a(n) for n = 1..925
Volkan Yildiz, Notes on algebraic structure of truth tables of bracketed formulae connected by implications, arXiv:2106.04728 [math.CO], 2021.

Cf. A005159 (unknown rows, shifted), A025226 (all rows), A345189 (false rows).

CoefficientList[Series[(4 -Sqrt[1-12*x] -Sqrt[5 +24*x +4*Sqrt[1-12*x]])/6, {x, 0, 40}], x]//Rest (* G. C. Greubel, May 20 2022 *)

my(x='x+O('x^30)); Vec((4-sqrt(1-12*x)-sqrt(5+24*x+4*sqrt(1-12*x)))/6)

def A345190_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (4-sqrt(1-12*x)-sqrt(5+24*x+4*sqrt(1-12*x)))/6 ).list()
a=A345190_list(40); a[1:] # G. C. Greubel, May 20 2022

G.f.: (4-sqrt(1-12*x)-sqrt(5+24*x+4*sqrt(1-12*x)))/6.

a(n) = 2*A005159(n-1) - A345189(n). - G. C. Greubel, May 20 2022

A376086 a(0) = 1; a(n) = Sum_{k=0..n-1} (3k+2) a(k) * a(n-k-1).

Original entry on oeis.org

1, 2, 14, 160, 2444, 45792, 1005480, 25169760, 705321200, 21841420384, 740194188032, 27243674154368, 1082259310732096, 46159435144505600, 2104195645965319680, 102113572703197079040, 5256795948307255075584, 286171738279517073904128, 16427146596936396844976640

Offset: 0

Ilya Gutkovskiy, Sep 09 2024

nonn

Cf. A000699, A005159, A088716, A215648, A375393, A376087.

a[0] = 1; a[n_] := a[n] = Sum[(3 k + 2) a[k] a[n - k - 1], {k, 0, n - 1}]; Table[a[n], {n, 0, 18}]
nmax = 18; A[] = 0; Do[A[x] = 1 + 2 x A[x]^2 + 3 x^2 A'[x] A[x] + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]

G.f. A(x) satisfies: A(x) = 1 + 2 * x * A(x)^2 + 3 * x^2 * A'(x) * A(x).

A101486 Square array T(n,k), read by antidiagonals: number of labeled trees, with increments of labels along edges constrained to -1,0,1, with n nodes that have no label greater than k.

Original entry on oeis.org

1, 1, 2, 1, 3, 9, 1, 3, 17, 54, 1, 3, 18, 119, 378, 1, 3, 18, 134, 932, 2916, 1, 3, 18, 135, 1111, 7838, 24057, 1, 3, 18, 135, 1133, 9833, 69275, 208494, 1, 3, 18, 135, 1134, 10176, 90959, 635279, 1876446, 1, 3, 18, 135, 1134, 10205, 95635, 868827, 5994584, 222646205

Offset: 0

Ralf Stephan, Jan 21 2005

Rows converge to A005159.

First row is A000168.

			1,2,9,54,378,2916,24057,208494,1876446,17399772,
1,3,17,119,932,7838,69275,635279,5994584,57872666,
1,3,18,134,1111,9833,90959,868827,8504314,84866778,
1,3,18,135,1133,10176,95635,928442,9236144,93646430,
1,3,18,135,1134,10205,96191,937361,9365984,95427597,
1,3,18,135,1134,10206,96227,938179,9381050,95673739,
1,3,18,135,1134,10206,96228,938222,9382179,95697199,
1,3,18,135,1134,10206,96228,938223,9382229,95698688,

M. Bousquet-Mélou, Limit laws for embedded trees, arXiv:math/0501266 [math.CO], 2005.

Cf. A000168, A005159, A101487.

nmax = 9;
b[t_] = 2/(1 + Sqrt[1 - 12t]) + O[t]^(nmax+1);
c[t_] = (1 + Sqrt[1 - 12t] - t (8 + Sqrt[2] Sqrt[(1 + Sqrt[1 - 12t] - 2 (7 + 4 Sqrt[1 - 12t]) t + 24t^2)/t^2]))/(4t) + O[t]^(nmax+1) // Simplify[#, t > 0]&;
a[n_, t_] := a[n, t] = b[t] (1 - c[t]^(n + 1)) (1 - c[t]^(n + 4))/((1 - c[t]^(n+2)) (1 - c[t]^(n+3))) + O[t]^(nmax+1) // Simplify[#, t > 0]&;
T[n_, k_] := SeriesCoefficient[a[n, t], {t, 0, k}];
Table[T[n - k, k], {n, 0, nmax}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 25 2018 *)

G.f. of k-th row: A(t)=B(t)*(1-C(t)^(k+1))*(1-C(t)^(k+4))/[(1-C(t)^(k+2))*(1-C(t)^(k+3))], with B(t) the g.f. of A005159 and C(t) the g.f. of A101487.

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

Original entry on oeis.org

1, 3, 18, 135, 1134, 10206, 96228, 938223, 9382230, 95698746, 991787004, 10413763542, 110546105292, 1184422556700, 12791763612360, 139110429284415, 1522031755700070, 16742349312700770, 185047018719324300, 2054021907784499730, 22887672686741568420, 255925794588110265060

Offset: 0

Manuel Kauers, Nov 18 2008

Apparently a duplicate of A005159. [R. J. Mathar, Dec 13 2008]

M. Bousquet-Mélou and M. Mishna, Walks with small steps in the quarter plane, arXiv:0810.4387 [math.CO], 2008-2009.

aux[i_Integer, j_Integer, n_Integer] := 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, -1 + j, -1 + n] + aux[1 + i, j, -1 + n] + aux[1 + i, 1 + j, -1 + n]]; Table[Sum[aux[0, k, 2 n], {k, 0, 2 n}], {n, 0, 25}]

cp's OEIS Frontend

A354734 a(0) = a(1) = 1; a(n) = 3 * Sum_{k=0..n-2} a(k) * a(n-k-2).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A006849 Number of strongly self-dual planar maps with 2n edges.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A103937 Number of unrooted n-edge maps in the plane (planar map with a distinguished outside face).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A122871 Expansion of (1 - 2*x - sqrt(1 - 4*x - 8*x^2))/(6*x^2).

Views

Author

Keywords

Comments

Links

Programs

Mathematica

PARI

Sage

Formula

A316598 a(n) is the number of rooted quadrangulations of the projective plane with n vertices.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A345189 Number of rows with the value "false" in the Kleene truth tables of all bracketed formulae with n distinct propositions p1, ..., pn connected by the binary connective of implication.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

SageMath

Formula

A345190 Number of rows with the value "true" in the Kleene truth tables of all bracketed formulae with n distinct propositions p1, ..., pn connected by the binary connective of implication.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

SageMath

Formula

A376086 a(0) = 1; a(n) = Sum_{k=0..n-1} (3*k+2) * a(k) * a(n-k-1).

Views

A122871 Expansion of (1 - 2x - sqrt(1 - 4x - 8x^2))/(6x^2).

A376086 a(0) = 1; a(n) = Sum_{k=0..n-1} (3k+2) a(k) * a(n-k-1).