A006343 Arkons: number of elementary maps with n-1 nodes.

1, 0, 1, 1, 4, 10, 34, 112, 398, 1443, 5387, 20482, 79177, 310102, 1228187, 4910413, 19792582, 80343445, 328159601, 1347699906, 5561774999, 23052871229, 95926831442, 400587408251, 1678251696379, 7051768702245, 29710764875014

Offset: 0

Author

N. J. A. Sloane

Keywords

• easy
• nonn
• nice

References

• K. Appel and W. Haken, Every planar map is four colorable. With the collaboration of J. Koch. Contemporary Mathematics, 98. American Mathematical Society, Providence, RI, 1989. xvi+741 pp. ISBN: 0-8218-5103-9.
• F. R. Bernhart, Topics in Graph Theory Related to the Five Color Conjecture. Ph.D. Dissertation, Kansas State Univ., 1974.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
• F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999), 73-112.
• F. R. Bernhart, Fundamental chromatic numbers, Unpublished. (Annotated scanned copy)
• F. R. Bernhart and N. J. A. Sloane, Correspondence, 1977.
• F. R. Bernhart and N. J. A. Sloane, Emails, April-May 1994.
• G. D. Birkhoff and D. C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60, (1946). 355-451.

Crossrefs

Cf. A000108, A000934, A007318.

Programs

Haskell

a006343 0 = 1
a006343 n = sum $ zipWith div
   (zipWith (*) (map (a007318 n) ks)
                (map (\k -> a007318 (2*n - 3*k - 4) (n - 2*k - 2)) ks))
   (map (toInteger . (n - 1 -)) ks)
   where ks = [0 .. (n - 2) `div` 2]
-- Reinhard Zumkeller, Aug 23 2012

Maple

A006343:=n->add(binomial(n,k)*binomial(2*n-3*k-4,n-2*k-2)/(n-k-1), k=0..(n-2)/2): (1, seq(A006343(n), n=1..30)); # Wesley Ivan Hurt, Jun 22 2015

Mathematica

a[n_] := Sum[ Binomial[n, k]*Binomial[2*n-3*k-4, n-2*k-2]/(n-k-1), {k, 0, (n-2)/2}]; a[0] = 1; Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Dec 14 2012, from formula *)

Formula

a(n-1) = Sum (n-k-1)^(-1)*binomial(n, k)*binomial(2*n-3*k-4, n-2*k-2); k = 0..[ (n-2)/2 ], n >= 3.

From Peter Bala, Jun 22 2015: (Start)

O.g.f. A(x) equals 1/x * series reversion ( x/(1 + x^2*C(x)) ), where C(x) = (1 - sqrt(1 - 4*x))/(2*x) is the o.g.f. for A000108.

A(x) is an algebraic function satisfying x^3*A^3(x) - (x - 1)*A^2(x) + (x - 2)*A(x) + 1 = 0. (End)

a(n) ~ sqrt(s*(1 - s + 3*r^2*s^2) / (1 - r + 3*r^3*s)) / (2*sqrt(Pi) * n^(3/2) * r^(n - 1/2)), where r = 0.2229935155751761877673240243525445951244491757706... and s = 1.116796494086474135831052534637944909439048671327... are real roots of the system of equations 1 + (r-2)*s + r^3*s^3 = (r-1)*s^2, r + 2*s + 3*r^3*s^2 = 2 + 2*r*s. - Vaclav Kotesovec, Nov 27 2017

Conjecture: D-finite with recurrence: -(n+3)*(n-1)*a(n) +(11*n^2-2*n-45)*a(n-1) -(37*n+29)*(n-3)*a(n-2) +(29*n^2-125*n+78)*a(n-3) +(61*n-106)*(n-3)*a(n-4) -155*(n-3)*(n-4)*a(n-5)=0. - R. J. Mathar, Feb 20 2020

Extensions

Erroneously duplicated term 4 removed per Frank Bernhart's report by Max Alekseyev, Feb 11 2010