A000934 -id:A000934 - cp's OEIS frontend

A109394 A000934(A000934(n)).

10, 12, 13, 13, 14, 15, 15, 15, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22

Offset: 0

Jonathan Vos Post, Aug 26 2005

			a(0) = 10 because A000934(0) = 4 and A000934(4) = 10.
a(1) = 12 because A000934(1) = 7 and A000934(7) = 12.

Cf. A000934.

a(n) = floor( (7+sqrt(1+48*floor( (7+sqrt(1+48*n))/2 )))/2 ).

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

Original entry on oeis.org

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

N. J. A. Sloane

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).

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.

Cf. A000108, A000934, A007318.

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

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

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 *)

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

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

A158411 Maximum number of colors required to paint a map having n regions.

Original entry on oeis.org

0, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4

Offset: 0

Jaume Oliver Lafont, Mar 18 2009

The generating function can be arranged to have four zeros at the fourth roots of unity. - Jaume Oliver Lafont, Mar 23 2009
Also, the arithmetic function uhat(n,4,3) as defined in A291041. - Robert Price, Aug 25 2017
Decimal expansion of 1111/90000. - Elmo R. Oliveira, May 06 2024

Eric Weisstein's World of Mathematics, Four-Color Theorem
Wikipedia, Four color theorem
Index entries for linear recurrences with constant coefficients, signature (1).

Cf. A000934, A130130, A291041.

PadRight[Range[0, 3], 100, 4] (* Paolo Xausa, Aug 22 2024 *)

PARI
```
a(n)=if(n<4,n,4)
```

G.f.: x*(1+x+x^2+x^3)/(1-x).
G.f.: x*(1-x^4)/(1-x)^2. - Jaume Oliver Lafont, Mar 20 2009
G.f.: Product_{k=0..3} (1-I^k*x)*x/(1-x)^2. - Jaume Oliver Lafont, Mar 23 2009
a(n) = A130130(n) + A130130(n-2). - Jaume Oliver Lafont, Mar 24 2009
a(n) = min(n,4). - Wesley Ivan Hurt, Apr 16 2014
E.g.f.: 4*exp(x) - 4 - 3*x - x^2 - x^3/6. - Stefano Spezia, May 19 2024

A000703 Chromatic number (or Heawood number) of nonorientable surface with n crosscaps.

Original entry on oeis.org

4, 6, 7, 7, 8, 9, 9, 10, 10, 10, 11, 11, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24

Offset: 0

N. J. A. Sloane

J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley, 1987; see Table 5.2 p. 221.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 368 and 631.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..1000
K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429-490.
G. A. Dirac, Map-color theorems, Canad. J. Math., 4 (1952), 480ff.
G. Ringel & J. W. T. Youngs, Solution Of The Heawood Map-Coloring Problem, Proc. Nat. Acad. Sci. USA, 60 (1968), 438-445.
Eric Weisstein's World of Mathematics, Chromatic Number
Eric Weisstein's World of Mathematics, Heawood Conjecture

Cf. A000934 (the orientable case).

a000703 = floor . (/ 2) . (+ 7) . sqrt . (+ 1) . (* 24) . fromInteger
-- Reinhard Zumkeller, Dec 04 2012

A000703:=n->floor((7+sqrt(1+24*n))/2): seq(A000703(n), n=0..150); # Wesley Ivan Hurt, Apr 24 2017

Floor[(7+Sqrt[1+24*Range[0,80]])/2] (* Harvey P. Dale, Feb 03 2012 *)

a(n) = floor((7+sqrt(1+24*n))/2).

A135919 Chromatic number of stage-n Menger sponge.

Original entry on oeis.org

4, 11, 34, 133, 566, 2488, 11056, 49323, 220373, 985176, 4405203, 19699535, 88096982, 393978082, 1761917118, 7879521402, 35238270419, 157590299379, 704765178272, 3151805575994, 14095302829230, 63036110202947

Offset: 0

Marc LeBrun, Dec 05 2007

a(n) = A000934(A135918(n)).

			a(0)=4 because a cube requires at most 4 colors. a(1)=11 because a cube with holes drilled through the faces meeting in the center requires at most 11 colors.

C. Mackeprang & K. Myers, Coloring Graphs on Sponges: Problem 11208, Amer. Math. Monthly 114 (November 2007), p. 842.

Cf. A000934, A135918.

Table[Floor[(7+Sqrt[1+48*(21*20^n+38*8^n-59)/133])/2],{n,0,30}] (* Harvey P. Dale, Mar 07 2012 *)

a(n) = floor((7 + sqrt(1 + 48*(21*20^n + 38*8^n - 59)/133))/2).

A176074 Partial sums of A006343.

Original entry on oeis.org

1, 1, 2, 3, 7, 17, 51, 163, 561, 2004, 7391, 27873, 107050, 417152, 1645339, 6555752, 26348334, 106691779, 434851380, 1782551286, 7344326285, 30397197514, 126324028956, 526911437207, 2205163133586, 9256931835831, 38967696710845

Offset: 0

Jonathan Vos Post, Apr 07 2010

Partial sums of Arkons: number of elementary maps with n-1 nodes. The subsequence of primes in the partial sum begins: 2, 3, 7, 17, 163, no more through a(26).

			a(7) = 1 + 0 + 1 + 1 + 4 + 10 + 34 + 112 = 163 is prime.

Cf. A006343, A000934.

a(n) = SUM[i=0..n] A006343(i) = SUM[i=0..n].

A213443 a(0)=5, thereafter a(n) = chromatic number (or Heawood number) Chi(n) of surface of genus n.

Original entry on oeis.org

5, 7, 8, 9, 10, 11, 12, 12, 13, 13, 14, 15, 15, 16, 16, 16, 17, 17, 18, 18, 19, 19, 19, 20, 20, 20, 21, 21, 21, 22, 22, 22, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 27, 27, 27, 27, 28, 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31, 31, 32, 32

Offset: 0

N. J. A. Sloane, Jun 12 2012

nonn

This is what A000934 would have looked like if the four-color conjecture had turned out to be false.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

Cf. A000934.

cp's OEIS Frontend

A109394 A000934(A000934(n)).

Views

Author

Keywords

Examples

Crossrefs

Formula

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A158411 Maximum number of colors required to paint a map having n regions.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A000703 Chromatic number (or Heawood number) of nonorientable surface with n crosscaps.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

A135919 Chromatic number of stage-n Menger sponge.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A176074 Partial sums of A006343.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A213443 a(0)=5, thereafter a(n) = chromatic number (or Heawood number) Chi(n) of surface of genus n.

Views

Author

Keywords

Comments

References

Crossrefs