A069724 -id:A069724 - cp's OEIS frontend

A069720 a(n) = 2^(n-1)binomial(2n-1, n).

1, 6, 40, 280, 2016, 14784, 109824, 823680, 6223360, 47297536, 361181184, 2769055744, 21300428800, 164317593600, 1270722723840, 9848101109760, 76467608616960, 594748067020800, 4632774416793600, 36135640450990080, 282202144474398720, 2206307674981662720, 17266755717247795200

Offset: 1

Valery A. Liskovets, Apr 07 2002

Number of rooted unicursal planar maps with n edges (unicursal means that exactly two nodes are of odd valency; there is an Eulerian path).

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Harlan J. Brothers, Pascal's Prism: Supplementary Material.
Valery A. Liskovets and Timothy R. S. Walsh, Enumeration of Eulerian and unicursal planar maps, Discr. Math., 282 (2004), 209-221.
Sheng-Liang Yang, Yan-Ni Dong, and Tian-Xiao He, Some matrix identities on colored Motzkin paths, Discrete Mathematics 340.12 (2017): 3081-3091.

First superdiagonal of number array A082137.

Cf. A000079, A001700, A003584, A069723, A069724, A082143.

a069720 n = (a000079 $ n - 1) * (a001700 $ n - 1)
-- Reinhard Zumkeller, Jan 15 2015

[2^(n-2)*Binomial(2*n, n): n in [1..25]]; // Vincenzo Librandi, Apr 14 2018

Z:=(1-sqrt(1-2*z))*4^(n-1)/sqrt(1-2*z): Zser:=series(Z, z=0, 32): seq(coeff(Zser, z, n), n=1..20); # Zerinvary Lajos, Jan 01 2007

Table[2^(n-1) Binomial[2n-1,n],{n,20}] (* Harvey P. Dale, Jan 20 2013 *)

a(n) = binomial(2*n-1,n)<<(n-1) \\ Charles R Greathouse IV, Feb 06 2017

def A069720(n): return 2^(n-2)*binomial(2*n, n)
print([A069720(n) for n in range(1,31)]) # G. C. Greubel, Jan 18 2025

a(n) = 2^(n-2)*binomial(2*n, n).
G.f.: (1-sqrt(1-8*x))/(4*x*sqrt(1-8*x)) = 2/(sqrt(1-8*x)*(1-sqrt(1-8*x))) - 1/(2*x). - Paul Barry, Sep 06 2004
D-finite with recurrence: n*a(n) - 4*(2*n-1)*a(n-1) = 0. - R. J. Mathar, Apr 01 2012
E.g.f.: a(n) = n! * [x^n] (exp(4*x)*BesselI(0, 4*x) - 1)/4. - Peter Luschny, Aug 25 2012
From Reinhard Zumkeller, Jan 15 2015: (Start)
a(n) = A000079(n-1) * A001700(n-1); for n > 1:
a(n) = 2*A082143(n-1). (End)
From Amiram Eldar, Jan 16 2024: (Start)
Sum_{n>=1} 1/a(n) = 4/7 + 32*arcsin(1/(2*sqrt(2)))/(7*sqrt(7)).
Sum_{n>=1} (-1)^(n+1)/a(n) = 4/9 + 16*log(2)/27. (End)
a(n) = ((2*n)!/4) * [x^n] (BesselI(0, 2*sqrt(2*x)) - 1). - G. C. Greubel, Jan 18 2025

A003645 a(n) = 2^n * C(n+1), where C(n) = A000108(n) Catalan numbers.

Original entry on oeis.org

1, 4, 20, 112, 672, 4224, 27456, 183040, 1244672, 8599552, 60196864, 426008576, 3042918400, 21909012480, 158840340480, 1158600130560, 8496400957440, 62605059686400, 463277441679360, 3441489566760960, 25654740406763520, 191852841302753280, 1438896309770649600

Offset: 0

N. J. A. Sloane

Number of nonisomorphic unrooted unicursal planar maps with n+2 edges and exactly one vertex of valency 1 (unicursal means that exactly two vertices are of odd valency). - Valery A. Liskovets, Apr 07 2002
Total number of vertices in rooted Eulerian planar maps with n+1 edges.
Half the number of ways to dog-ear every page of an (n+1)-page book. - R. H. Hardin, Jun 21 2002
Convolution of A052701(n+1) with itself.
Number of Motzkin lattice paths with weights: 1 for up step, 4 for level step and 4 for down step. - Wenjin Woan, Oct 24 2004
The number of rooted bipartite n-edge maps in the plane (planar with a distinguished outside face). - Valery A. Liskovets, Mar 17 2005
Also the number of paths of length 2n+1 in a binary tree between two vertices that are one step away from each other. - David Koslicki (koslicki(AT)math.psu.edu), Nov 02 2010
2*a(n) for n > 1 is the number of increasing strict binary trees with 2n-1 nodes that simultaneously avoid 213 and 231 in the classical sense. For more information about increasing strict binary trees with an associated permutation, see A245894. - Manda Riehl, Aug 22 2014

L. M. Koganov, V. A. Liskovets, T. R. S. Walsh, Total vertex enumeration in rooted planar maps, Ars Combin. 54 (2000), 149-160.
V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.

A. Claesson, S. Kitaev and A. de Mier, An involution on bicubic maps and beta(0,1)-trees, arXiv preprint arXiv:1210.3219 [math.CO], 2012. - From _N. J. A. Sloane_, Jan 01 2013
S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, 2017.
Samuele Giraudo, Pluriassociative algebras II: The polydendriform operad and related operads, arXiv:1603.01394 [math.CO], 2016.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 652.
Anatol N. Kirillov, Notes on Schubert, Grothendieck and key polynomials, SIGMA, Symmetry Integrability Geom. Methods Appl. 12, Paper 034, 56 p. (2016).
Huyile Liang, Jeffrey Remmel, and Sainan Zheng, Stieltjes moment sequences of polynomials, arXiv:1710.05795 [math.CO], 2017, see page 13.
V. A. Liskovets and T. R. S. Walsh, Enumeration of Eulerian and unicursal planar maps, Discr. Math., Vol. 282, No. 1-3 (2004), pp. 209-221.
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.
Amya Luo, Pattern Avoidance in Nonnesting Permutations, Undergraduate Thesis, Dartmouth College (2024). See p. 11.
Youngja Park and SeungKyung Park, Enumeration of generalized lattice paths by string types, peaks, and ascents, Discrete Mathematics, Vol. 339, No. 11 (2016), pp. 2652-2659.
M. Z. Spivey and L. L. Steil, The k-Binomial Transforms and the Hankel Transform, J. Integ. Seq., Vol. 9 (2006), Article 06.1.1.

Cf. A069724, A069725, A090375.
Third row of array A102539.
Column of array A073165.
Cf. A000108, A052701, A195699.

[2^n*Binomial(2*n+3, n+1)/(2*n+3) : n in [0..30]]; // Wesley Ivan Hurt, Aug 23 2014

A003645:=n->2^n*binomial(2*n+3, n+1)/(2*n+3): seq(A003645(n), n=0..30); # Wesley Ivan Hurt, Aug 23 2014

Table[2^n CatalanNumber[n+1],{n,0,20}] (* Harvey P. Dale, May 07 2013 *)

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

a(n) = A052701(n+2)/2.
2*a(n) matches the odd-indexed terms of A090375.
a(n) = 2^n * binomial(2n+3, n+1) / (2n+3). - Len Smiley, Feb 24 2006
G.f.: (1-4x-sqrt(1-8x))/(8x^2) = C(2x)^2, where C(x) is the g.f. for Catalan numbers, A000108.
From Gary W. Adamson, Jul 12 2011: (Start)
Let M = the following production matrix:
  2, 2, 0, 0, 0, ...
  2, 2, 2, 0, 0, ...
  2, 2, 2, 2, 0, ...
  2, 2, 2, 2, 2, ...
  ...
a(n) = sum of top row terms in M^n. Example: top row of M^3 = (40, 40, 24, 8, 0, 0, 0, ...), sum = 112 = a(3). (End)
D-finite with recurrence (n+2)*a(n) - 4*(2n+1)*a(n-1) = 0. - R. J. Mathar, Apr 01 2012
E.g.f.: a(n) = n!* [x^n] exp(4*x)*BesselI(1, 4*x)/(2*x). - Peter Luschny, Aug 25 2012
Expansion of square of continued fraction 1/(1 - 2*x/(1 - 2*x/(1 - 2*x/(1 - ...)))). - Ilya Gutkovskiy, Apr 19 2017
From Amiram Eldar, Mar 06 2022: (Start)
Sum_{n>=0} 1/a(n) = 38/49 + 192*arcsin(sqrt(1/8))/(49*sqrt(7)).
Sum_{n>=0} (-1)^n/a(n) = 14/27 + 32*log(2)/81. (End)
a(n) = Product_{1 <= i <= j <= n} (i + j + 2)/(i + j - 1). Cf. A001700. - Peter Bala, Feb 22 2023

A069727 Number of nonisomorphic unrooted Eulerian planar maps with n edges (Eulerian means that all vertices are of even valency; there is an Eulerian cycle).

Original entry on oeis.org

1, 1, 2, 4, 12, 34, 154, 675, 3534, 18985, 108070, 632109, 3807254, 23411290, 146734695, 934382820, 6034524474, 39457153432, 260855420489, 1741645762265, 11732357675908, 79673115468562, 545036528857605, 3753642607424647, 26010818244754788, 181266500331748878

Offset: 0

Valery A. Liskovets, Apr 07 2002

By duality, also the number of unrooted (sensed) bipartite maps with n edges. - Andrew Howroyd, Mar 29 2021

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000
M. Deryagina, On the enumeration of hypermaps which are self-equivalent with respect to reversing the colors of vertices, Preprint 2016.
V. A. Liskovets and T. R. S. Walsh, Enumeration of Eulerian and unicursal planar maps, Discr. Math., 282 (2004), 209-221.

Cf. A000257 (rooted), A069720, A069724, A103939 (with distinguished face), A103940 (with distinguished vertex).

a[n_] := (1/(2n)) * (3*2^(n-1) * Binomial[2n, n]/((n+1)*(n+2)) + Sum[ EulerPhi[n/k] * d[n/k] * 2^(k-2) * Binomial[2k, k], {k, Most[ Divisors[n]]}]) + q[n]; a[0] = 1; q[n_?EvenQ] := 2^((n-4)/2)*Binomial[ n, n/2]/(n+2); q[n_?OddQ] := 2^((n-1)/2)*Binomial[(n-1), (n-1)/2]/(n+1); d[n_] := 4-Mod[n, 2]; Table[ a[n], {n, 0, 20}] (* Jean-François Alcover, Dec 19 2011, after Valery A. Liskovets *)

a(n) = {if(n==0, 1, sumdiv(n, d, if(dAndrew Howroyd, Mar 29 2021

a(n) = (1/(2n))*(3*2^(n-1)*binomial(2n, n)/((n+1)(n+2)) + Sum_{k=1..n-1, k|n} phi(n/k)*d(n/k)*2^(k-2)*binomial(2k, k)) + q(n) where phi is the Euler function A000010, q(n) = 2^((n-4)/2)*binomial(n, n/2)/(n+2) if n is even, q(n) = 2^((n-1)/2)*binomial(n-1, (n-1)/2)/(n+1) if n is odd, d(n)=4, if n is even and d(n)=3 if n is odd. - Valery A. Liskovets, Mar 17 2005

a(n) ~ 3 * 2^(3*n-2) / (sqrt(Pi) * n^(7/2)). - Vaclav Kotesovec, Aug 28 2019

A069731 Number of unicursal planar maps with n edges rooted at a vertex of odd valency (unicursal means that exactly two vertices are of odd valency; there is an Eulerian path).

Original entry on oeis.org

1, 5, 28, 168, 1056, 6864, 45760, 311168, 2149888, 15049216, 106502144, 760729600, 5477253120, 39710085120, 289650032640, 2124100239360, 15651264921600, 115819360419840, 860372391690240

Offset: 1

Valery A. Liskovets, Apr 07 2002

V. A. Liskovets and T. R. S. Walsh, Enumeration of Eulerian and unicursal planar maps, Discr. Math., 282 (2004), 209-221.

Cf. A069724, A069720, A000108, A003645.

Cf. A000346, A001006, A136576.

Z:=-(1-4*z-sqrt(1-4*z))/sqrt(1-4*z)/64: Zser:=series(Z, z=0, 32): seq(coeff(Zser*2^(n+1), z, n), n=3..24); # Zerinvary Lajos, Jan 01 2007

Table[2^(n-2) CatalanNumber[n+1], {n, 1, 19}] (* Jean-François Alcover, Aug 28 2019 *)

a(n) = 2^(n-2)*C_(n+1), where C_n stands for the Catalan numbers (A000108).
a(n) = A003645(n+2)/4.
D-finite with recurrence: 4*(2*n+1)*a(n-1) - (n+2)*a(n) = 0, a(1) = 1. - Georg Fischer, May 23 2021
From Peter Bala, Apr 29 2024: (Start)
a(n) = Sum_{k = 0..n} binomial(n, 2*k)*Catalan(k)*4^(n-k-1).
O.g.f.: A(x) = (1 - 4*x - 8*x^2 - sqrt(1 - 8*x))/(32*x^2).
A(x) = series reversion of x*c(-x)/(1 + 4*x), where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108 and c(-x)/(1 + 4*x) is the g.f. of (-1)^n*A000346(n). (End)

A069732 Number of nonisomorphic unrooted unicursal planar maps with n edges and no vertices of valency 1 (unicursal means that exactly two vertices are of odd valency; there is an Eulerian path).

Original entry on oeis.org

0, 0, 2, 7, 40, 239, 1549, 10396, 71467, 498598, 3520015, 25087426, 180249182, 1304148015, 9494015372, 69492950976, 511147940104, 3776180492129, 28007532925171, 208474866181148

Offset: 1

Valery A. Liskovets, Apr 07 2002

V. A. Liskovets and T. R. S. Walsh, Enumeration of Eulerian and unicursal planar maps, Discr. Math., 282 (2004), 209-221.

Cf. A069724, A003645, A069725, A005470.

A003645[n_] := 2^n CatalanNumber[n + 1];
A069724[n_] := 1/(2 n) DivisorSum[n, If[OddQ[n/#], EulerPhi[n/#] 2^(# - 2) Binomial[2 #, #], 0] &] + If[OddQ[n], 2^((n - 3)/2) Binomial[n - 1, (n - 1)/2], 2^((n - 6)/2) Binomial[n, n/2]];
A069725[n_] := If[n <= 2, 1, With[{m = Floor[(n + 1)/2]}, 1/n 2^(n - 3) Binomial[2 n - 2, n - 1] + 2^(m - 3) Binomial[2 m - 2, m - 1]]];
a[n_] := If[n == 1, 0, A069724[n] - A003645[n - 2] - A069725[n]];
Array[a, 20] (* Jean-François Alcover, Aug 28 2019 *)

a(n) = A069724(n) - A003645(n) - A069725(n).

A069730 Number of nonisomorphic unrooted unicursal planar maps with n edges.

Original entry on oeis.org

1, 2, 4, 13, 50, 248, 1407, 8600, 55154, 365292, 2473956, 17053468, 119191992, 842688120, 6015275094, 43292026736, 313788095994, 2288506113056, 16781638172458, 123656774440396, 915123392599456

Offset: 0

Valery A. Liskovets, Apr 07 2002

Unicursal (in a broad sense) means that no more than two vertices are of odd valency (that is, maps possessing an Eulerian path).

V. A. Liskovets and T. R. S. Walsh, Enumeration of Eulerian and unicursal planar maps, Discr. Math., 282 (2004), 209-221.

Cf. A069727, A069724.

A069724[n_] := 1/(2 n) DivisorSum[n, If[OddQ[n/#], EulerPhi[n/#] 2^(# - 2) Binomial[2 #, #], 0] &] + If[OddQ[n], 2^((n - 3)/2) Binomial[n - 1, (n - 1)/2], 2^((n - 6)/2) Binomial[n, n/2]];
A069727[n_] := (1/(2 n))*(3*2^(n - 1)*Binomial[2 n, n]/((n + 1)*(n + 2)) + Sum[EulerPhi[n/k]*d[n/k]*2^(k - 2)*Binomial[2 k, k], {k, Most[Divisors[n]]}]) + q[n]; A069727[0] = 1;
q[n_?EvenQ] := 2^((n - 4)/2)*Binomial[n, n/2]/(n + 2); q[n_?OddQ] := 2^((n - 1)/2)*Binomial[(n - 1), (n - 1)/2]/(n + 1);
d[n_] := 4 - Mod[n, 2];
a[n_] := A069727[n] + A069724[n];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Aug 28 2019 *)

a(n) = A069727(n) + A069724(n).

cp's OEIS Frontend

A069720 a(n) = 2^(n-1)*binomial(2*n-1, n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

SageMath

Formula

A003645 a(n) = 2^n * C(n+1), where C(n) = A000108(n) Catalan numbers.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A069727 Number of nonisomorphic unrooted Eulerian planar maps with n edges (Eulerian means that all vertices are of even valency; there is an Eulerian cycle).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A069731 Number of unicursal planar maps with n edges rooted at a vertex of odd valency (unicursal means that exactly two vertices are of odd valency; there is an Eulerian path).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A069732 Number of nonisomorphic unrooted unicursal planar maps with n edges and no vertices of valency 1 (unicursal means that exactly two vertices are of odd valency; there is an Eulerian path).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A069730 Number of nonisomorphic unrooted unicursal planar maps with n edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A069720 a(n) = 2^(n-1)binomial(2n-1, n).