Valery A. Liskovets - cp's OEIS frontend

A124092 From a question about accepting states in certain finite automata.

1, 7, 98, 1020, 10160, 89960, 780368, 6419109

Offset: 0

Valery A. Liskovets, Nov 27 2006

George S. Lueker, Improved Bounds on the Average Length of Longest Common Subsequences. Journal of the ACM 56(3) (2009), Article 17. (Fig.1).

A118447 Number of rooted n-edge one-vertex maps on the Klein bottle (dually: one-face maps).

4, 42, 304, 1870, 10488, 55412, 280768, 1379286, 6616360, 31144300, 144367584, 660746892, 2991902704, 13424189160, 59758420736, 264191654758, 1160934273288, 5074150057916, 22071747625120, 95596117130724

Offset: 2

Valery A. Liskovets, May 04 2006

nonn

One-vertex maps on the projective plane are counted by A000346 and one-vertex maps on a non-orientable genus-3 surface by A118448. Such maps are also called bouquets of loops (and their duals are called unicellular maps).

E. R. Canfield, Calculating the number of rooted maps on a surface, Congr. Numerantium, 76 (1990), 21-34.
D. M. Jackson and T. I. Visentin, An atlas of the smaller maps in orientable and nonorientable surfaces. CRC Press, Boca Raton, 2001.

((R - 1)^2 (R + 1) (R + 3)/(8 R^5) /. R -> Sqrt[1 - 4x]) + O[x]^22 // CoefficientList[#, x]& // Drop[#, 2]& (* Jean-François Alcover, Aug 28 2019 *)

O.g.f.: (R-1)^2(R+1)(R+3)/8R^5, where R=sqrt(1-4x).
Conjecture: -(n-2)*(n-1)^2*a(n) +2*n*(4*n-5)*(n-2)*a(n-1) -8*n*(n-1)*(2*n-3)*a(n-2)=0. - R. J. Mathar, Jun 22 2016
a(n) ~ n^(3/2) * 2^(2*n-1) / sqrt(Pi) * (1 - sqrt(Pi/n)/2). - Vaclav Kotesovec, Aug 28 2019

A118450 Number of rooted n-edge one-vertex one-face maps on a non-orientable surface (of genus n).

Original entry on oeis.org

1, 4, 41, 488, 8229, 164892, 4016613, 112818960

Offset: 1

Valery A. Liskovets, May 04 2006

One-vertex one-face maps on orientable surfaces are counted by A035319.

E. R. Canfield, Calculating the number of rooted maps on a surface, Congr. Numerantium, 76 (1990), 21-34.
D. M. Jackson and T. I. Visentin, An atlas of the smaller maps in orientable and nonorientable surfaces. CRC Press, Boca Raton, 2001.

Main diagonal of A267180.

Cf. A035319.

a(7)-a(8) added by Andrew Howroyd, Jan 16 2022

A118445 Number of tree-rooted maps of genus 1 with n edges: rooted maps on the torus with a distinguished spanning tree.

Original entry on oeis.org

1, 25, 490, 8820, 152460, 2576574, 42942900, 709171320, 11636856660, 190068658780, 3093732938296, 50222937310000, 813611584422000, 13158602740363500, 212528020730913000, 3428785401125396400, 55266606794455402500, 890117467077758188500

Offset: 2

Valery A. Liskovets, May 04 2006

nonn

Tree-rooted planar maps are counted by A005568 and tree-rooted maps of (orientable) genus 2 by A118446. Typically, a(11) = 190068658780 = 2^2*5*7^2*11*13^2*17^2*19^2.

E. A. Bender, E. R. Canfield and R. W. Robinson, The asymptotic number of tree-rooted maps on a surface, J. Comb. Theory, Ser. A, 48, No. 2 (1988), 156-164.
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. II, J. Comb. Theory, Ser. B, 13, No. 2 (1972), 122-141 (pp. 137, 140).

HypergeometricPFQ[{5/2, 5/2}, {4}, 16x] + O[x]^18 // CoefficientList[#, x]& (* Jean-François Alcover, Aug 28 2019 *)
Table[n*(n-1) * Binomial[2*n,n]^2 / (24*(n+1)), {n, 2, 20}] (* Vaclav Kotesovec, Feb 17 2024 *)

a(n) = binomial(2n, 0) C(0) b(n) + binomial(2n, 2) C(1) b(n-1) + binomial(2n, 4) C(2) b(n-2) + ... + binomial(2n, 2n) C(n) b(0), where C(n) = A000108(n) - n-th Catalan number and b(n) = (2n-1)!/(6(n-2)! (n-1)!) = A002802(n-2) - the number of toroidal one-vertex maps with n edges for n >= 2 and b(0) = b(1) = 0.
O.g.f.: x^2 * hypergeom([5/2, 5/2], [4], 16*x).  - Mark van Hoeij, Apr 06 2013
D-finite with recurrence -(n+1)*(n-2)*a(n) +4*((2*n-1)^2)*a(n-1)=0. - R. J. Mathar, Jul 27 2022
From Vaclav Kotesovec, Feb 17 2024: (Start)
a(n) = n*(n-1) * binomial(2*n,n)^2 / (24*(n+1)).
a(n) ~ 2^(4*n-3)/(3*Pi). (End)

Added more terms, Joerg Arndt, Apr 07 2013

A118446 Number of tree-rooted maps of genus 2 with n edges: rooted maps with a distinguished spanning tree on an orientable surface of genus 2.

Original entry on oeis.org

21, 1428, 59136, 1936935, 55165110, 1430857428, 34701610944, 800003272068, 17726513264460, 380471504212800, 7955313269904000, 162738137109652650, 3267801532548762300, 64578810084245919000, 1258643138633207712000, 24234564983959535297400, 461636913607179055445700

Offset: 4

Valery A. Liskovets, May 04 2006

nonn

Tree-rooted planar maps are counted by A005568 and tree-rooted maps on the torus by A118445.

E. A. Bender, E. R. Canfield and R. W. Robinson, The asymptotic number of tree-rooted maps on a surface, J. Comb. Theory, Ser. A, 48, No. 2 (1988), 156-164.
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. II, J. Comb. Theory, Ser. B, 13, No. 2 (1972), 122-141 (pp. 137, 140).

C := proc(n) binomial(2*n,n)/(n+1) end:
b := proc(n) options remember;
  if n<4 then 0 elif n=4 then 21 else
    ((5*(n-1)+3)*(4*(n-1)+2)*b(n-1))/((5*(n-1)-2)*(n-1-3))
  fi
end:
seq(add(binomial(2*n,2*i)*C(i)*b(n-i), i=0..n), n=4..20);
# Mark van Hoeij, Apr 06 2013

a[n_] := 2^(4n-9)(n-2)(5n^2+n+6) Gamma[n-3/2] Gamma[n+1/2]/(45 Pi (n-4)! (n+1)! );
Table[a[n], {n, 4, 20}] (* Jean-François Alcover, Aug 28 2019 *)

C(n) = binomial(2*n, n)/(n+1);
A006298(n) = if(n<4,0,if(n==4,21,((5*(n-1)+3)*(4*(n-1)+2)*A006298(n-1))/((5*(n-1)-2)*((n-1)-3))));
b(n)=A006298(n);
a(n)=sum(k=0,n, binomial(2*n,2*k) * C(k) * b(n-k) );
/* Joerg Arndt, Apr 07 2013 */

a(n) = sum(k=0..n, binomial(2*n,2*k) * C(k) * b(n-k) ), where C(n)=A000108(n) - n-th Catalan number and b(n)=A006298(n) - the number of one-vertex maps of genus 2 for n>=4 and b(n)=0 for n<4.
G.f.: 7*x^4*(3*(1-9*x)*hypergeom([7/2,11/2],[6],16*x)+77*(1-6*x)*x*hypergeom([9/2,13/2],[7],16*x)). - Mark van Hoeij, Apr 07 2013
a(n) = (n-3)*(n-2)^2*(n-1)*n*(5*n^2+n+6) * binomial(2*n,n)^2 / (5760*(n+1)*(2*n-3)*(2*n-1)). - Vaclav Kotesovec, Oct 26 2024

Corrected (replaced 34385678184 by 34701610944) and added more terms, Mark van Hoeij and Joerg Arndt, Apr 07 2013

A118449 Number of rooted n-edge one-vertex maps on a non-orientable genus-4 surface (dually: one-face maps).

Original entry on oeis.org

0, 488, 11660, 160680, 1678880, 14771680, 115457832, 827303280, 5545466520, 35257287120, 214730922120, 1262004908528, 7197437563680, 40007524376960, 217501266966160, 1159737346931040, 6079078540464072, 31385516059734960

Offset: 3

Valery A. Liskovets, May 04 2006

nonn

One-vertex maps on a non-orientable genus-3 surface are counted by A118448. Such maps are also called bouquets of loops (and their duals are called unicellular maps).

E. R. Canfield, Calculating the number of rooted maps on a surface, Congr. Numerantium, 76 (1990), 21-34.
D. M. Jackson and T. I. Visentin, An atlas of the smaller maps in orientable and nonorientable surfaces. CRC Press, Boca Raton, 2001.

Didier Arquès and Alain Giorgetti, Counting rooted maps on a surface, Theoret. Comput. Sci. 234 (2000), no. 1-2, 255--272. MR1745078 (2001f:05078).

Cf. A118448. A diagonal of A214806.

With[{r=Sqrt[1-4x]},Drop[CoefficientList[Series[-(r-1)^4 (r+1)^3 (65r^3+ 337r^2- 433r-945)/(256r^11),{x,0,20}],x],3]] (* Harvey P. Dale, Aug 05 2019 *)

O.g.f.: -(R-1)^4(R+1)^3(65R^3+337R^2-433R-945)/(256R^11), where R=sqrt(1-4x).

a(n) ~ n^(9/2) * 2^(2*n-3) / sqrt(Pi) * (1 - 2*sqrt(Pi)/(3*sqrt(n))). - Vaclav Kotesovec, Oct 27 2024

A118451 Number of rooted n-edge maps on a non-orientable genus-3 surface.

Original entry on oeis.org

41, 1380, 31225, 592824, 10185056, 164037704, 2525186319, 37596421940, 545585129474, 7758174844664, 108518545261360, 1497384373878512, 20426386710028260, 275940187259609296, 3696482210884173349

Offset: 3

Valery A. Liskovets, May 04 2006

nonn

E. R. Canfield, Calculating the number of rooted maps on a surface, Congr. Numerantium, 76 (1990), 21-34.
D. M. Jackson and T. I. Visentin, An atlas of the smaller maps in orientable and nonorientable surfaces. CRC Press, Boca Raton, 2001.

R. J. Mathar, Table of n, a(n) for n = 3..100
Didier Arquès, Alain Giorgetti, Counting rooted maps on a surface, Theoret. Comput. Sci. 234 (2000), no. 1-2, 255--272. MR1745078 (2001f:05078). - _N. J. A. Sloane_, Jul 27 2012

Cf. A006344, A214334.

R := sqrt(1-12*x) ;
(R-1)*(R+1)*(68*R^5+280*R^4+588*R^3+808*R^2+416*R -(28*R^4+59*R^3+114*R^2+119*R+40)*sqrt(12*R*(R+2)))/96/R^5/(R+2)^3 ;
g := series(%,x=0,101) ;
for n from 3 to 100 do
    printf("%d %d\n",n,coeftayl(g,x=0,n)) ;
end do: # R. J. Mathar, Oct 17 2012

R = Sqrt[1-12x];
(R-1)(R+1)(68R^5 + 280R^4 + 588R^3 + 808R^2 + 416R - (28R^4 + 59R^3 + 114R^2 + 119R + 40) Sqrt[12R(R+2)])/96/R^5/(R+2)^3 + O[x]^18 // CoefficientList[#, x]& // Drop[#, 3]& (* Jean-François Alcover, Aug 28 2019 *)

O.g.f.: (R-1) *(R+1) *(68*R^5 +280*R^4 +588*R^3 +808*R^2 +416*R -(28*R^4+59*R^3+114*R^2+119*R+40)*sqrt(12*R*(R+2)))/ (96*R^5*(R+2)^3), where R=sqrt(1-12*x).

a(n) ~ 2^(2*n + 1/2) * 3^(n - 1/2) * n^(5/4) / Gamma(1/4) * (1 - 13*Gamma(1/4) / (8*sqrt(6)*n^(1/4)) + 23*Gamma(1/4)^2 / (32*Pi*sqrt(2*n)) - 23*Gamma(1/4) / (16*sqrt(6*Pi)*n^(3/4))). - Vaclav Kotesovec, Oct 27 2024

A118448 Number of rooted n-edge one-vertex maps on a non-orientable genus-3 surface (dually: one-face maps).

Original entry on oeis.org

41, 690, 7150, 58760, 420182, 2736524, 16661580, 96411060, 536075430, 2886649260, 15139322276, 77665981120, 391031449340, 1937266785080, 9464122525784, 45670084085004, 218002466412870, 1030588793671980

Offset: 3

Valery A. Liskovets, May 04 2006

nonn

One-vertex maps on the Klein bottle are counted by A118447 and one-vertex maps on a non-orientable genus-4 surface by A118449. Such maps are also called bouquets of loops (and their duals are called unicellular maps).

E. R. Canfield, Calculating the number of rooted maps on a surface, Congr. Numerantium, 76 (1990), 21-34.
D. M. Jackson and T. I. Visentin, An atlas of the smaller maps in orientable and nonorientable surfaces. CRC Press, Boca Raton, 2001.

R. J. Mathar, Table of n, a(n) for n = 3..100
Didier Arquès, Alain Giorgetti, Counting rooted maps on a surface, Theoret. Comput. Sci. 234 (2000), no. 1-2, 255--272. MR1745078 (2001f:05078). - _N. J. A. Sloane_, Jul 27 2012

A diagonal of A214337.

((R-1)^3 (R+1)^2 (11 R^2 - 29 R - 64)/(64 R^8) /. R -> Sqrt[1-4x]) + O[x]^21 // CoefficientList[#, x]& // Drop[#, 3]& (* Jean-François Alcover, Aug 29 2019 *)

O.g.f.: (R-1)^3*(R+1)^2*(11*R^2-29*R-64)/(64*R^8), where R=sqrt(1-4*x).
D-finite with recurrence (69104*n+95905)*(n-2)*(n-3) *a(n) +2*(n-3) *(34552*n^2-2691825*n+3948578) *a(n-1) +4*(-967456*n^3+10134720*n^2-23520179*n+15213000) *a(n-2) + 144 *(2*n-5) *(34552*n-41477) *(n-2) *a(n-3)=0. R. J. Mathar, Oct 17 2012
a(n) ~ n^3 * 2^(2*n-1) / 3 * (1 - 7/(4*sqrt(Pi*n))). - Vaclav Kotesovec, Oct 27 2024

A118095 Number of unrooted regular odd-valent planar maps with 8 vertices; maps are considered up to orientation-preserving homeomorphisms and the vertices are of valency 2n+1.

Original entry on oeis.org

0, 191, 39670362, 4742588317460, 457373823022288900, 39758207592119720043060, 3253001744463113558023410456, 255859318139167527752722081113072

Offset: 0

Valery A. Liskovets, Apr 13 2006

nonn

There is a closed formula.

Z. C. Gao, V. A. Liskovets and N. C. Wormald, Enumeration of unrooted odd-valent regular planar maps

Cf. A112946.

A118094 Numbers of unrooted hypermaps on the torus with n darts up to orientation-preserving homeomorphism (darts are semi-edges in the particular case of ordinary maps).

Original entry on oeis.org

1, 6, 33, 285, 2115, 16533, 126501, 972441, 7451679, 57167260, 438644841, 3369276867, 25905339483, 199408447446, 1536728368389, 11856420991413, 91579955286519, 708146055343668, 5481535740059577, 42473608898628639

Offset: 3

Valery A. Liskovets, Apr 13 2006

nonn

A. Mednykh and R. Nedela, Counting unrooted hypermaps on closed orientable surface, 18th Intern. Conf. Formal Power Series & Algebr. Comb., Jun 19, 2006, San Diego, California (USA).
A. Mednykh and R. Nedela, Enumeration of unrooted hypermaps of a given genus, Discr. Math., 310 (2010), 518-526. [From _N. J. A. Sloane_, Dec 19 2009]
Mednykh, A.; Nedela, R. Recent progress in enumeration of hypermaps, J. Math. Sci., New York 226, No. 5, 635-654 (2017) and Zap. Nauchn. Semin. POMI 446, 139-164 (2016), table 3.
Timothy R. Walsh, Space-efficient generation of nonisomorphic maps and hypermaps
T. R. Walsh, Space-Efficient Generation of Nonisomorphic Maps and Hypermaps, J. Int. Seq. 18 (2015) # 15.4.3

Cf. A090371, A118093.

Phi2 := proc(l)
    local a,k ;
    a := 0 ;
    for k in numtheory[divisors](l) do
        a := a+numtheory[mobius](l/k)*k^2 ;
    end do:
    a ;
end proc:
h0 := proc(m)
    if type(m,integer) then
        binomial(2*m,m)*3*2^(m-1)/(m+1)/(m+2) ;
    else
        0;
    end if;
end proc:
h1 := proc(n)
    local a;
    a := 0 ;
    if n >= 3 and type(n,integer) then
        a := add(2^k*(4^(n-2-k)-1)*binomial(n+k,k),k=0..n-3) ;
    end if;
    a/3 ;
end proc:
A118094 := proc(n)
    binomial(n/2+2,4)*h0(n/2) ;
    %+2*binomial(n/3+2,3)*h0(n/3) ;
    %+6*binomial(n/4+2,3)*h0(n/4) ;
    a := %+12*binomial(n/6+2,3)*h0(n/6) ;
    for l in numtheory[divisors](n) do
        if modp(n,l) = 0 then
            a := a+h1(n/l)*Phi2(l) ;
        end if;
    end do:
    a/n ;
end proc:
seq(A118094(n),n=3..14) ; # R. J. Mathar, Dec 17 2014

h0[n_] := If[Denominator[n] == 1, 3*2^(n-1)*Binomial[2*n, n]/((n+1)*(n+2)), 0]; h1[n_] := Sum[(4^(n-2-k)-1)*Binomial[n+k, k]*2^k, {k, 0, n-3}]/3; phi2[n_] := Sum[MoebiusMu[n/d]*d^2, {d, Divisors[n]}]; a[n_] := (Binomial[n/2+2, 4]*h0[n/2] +  2*Binomial[n/3+2, 3]*h0[n/3]+6*Binomial[n/4+2, 3]*h0[n/4] + 12*Binomial[n/6+2, 3]*h0[n/6] + Sum[ phi2[d]*h1[n/d], {d, Divisors[n]}])/n; Table[a[n], {n, 3, 22}] (* Jean-François Alcover, Dec 18 2014, translated from PARI *)

h0(n) = if(denominator(n)==1, 3*2^(n-1)*binomial(2*n, n)/((n+1)*(n+2)), 0);
h1(n) = sum(k=0, n-3, (4^(n-2-k)-1)*binomial(n+k, k)<Michel Marcus, Dec 11 2014 ; corrected by Charles R Greathouse IV, Dec 17 2014

cp's OEIS Frontend

User: Valery A. Liskovets

A124092 From a question about accepting states in certain finite automata.

Views

Author

Keywords

Links

A118447 Number of rooted n-edge one-vertex maps on the Klein bottle (dually: one-face maps).

Views

Author

Keywords

Comments

References

Programs

Mathematica

Formula

A118450 Number of rooted n-edge one-vertex one-face maps on a non-orientable surface (of genus n).

Views

Author

Keywords

Comments

References

Crossrefs

Extensions

A118445 Number of tree-rooted maps of genus 1 with n edges: rooted maps on the torus with a distinguished spanning tree.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

Formula

Extensions

A118446 Number of tree-rooted maps of genus 2 with n edges: rooted maps with a distinguished spanning tree on an orientable surface of genus 2.

Views

Author

Keywords

Comments

Links

Programs

Maple

Mathematica

PARI

Formula

Extensions

A118449 Number of rooted n-edge one-vertex maps on a non-orientable genus-4 surface (dually: one-face maps).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A118451 Number of rooted n-edge maps on a non-orientable genus-3 surface.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A118448 Number of rooted n-edge one-vertex maps on a non-orientable genus-3 surface (dually: one-face maps).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A118095 Number of unrooted regular odd-valent planar maps with 8 vertices; maps are considered up to orientation-preserving homeomorphisms and the vertices are of valency 2n+1.