# [seqfan] Toothpicks A139250 defines set of graphs

Richard Mathar mathar at strw.leidenuniv.nl
Mon Jan 11 18:24:37 CET 2010

```The basic toothpick sequence
http://research.att.com/~njas/sequences/A139250
defines planar, connected, unlabeled, non-oriented, loop-less graphs
of three types/variants:
Type 0 :
Vertices are defined by all toothpick ends. (Points on the grid shared by
two or more toothpicks ends define only one node.) Edges are toothpicks
which are not touched at the mid-point, or the two half-toothpicks
of toothpicks touched at the midpoint.
Example for generation n=3, where the first toothpick was placed vertically,
then two toothpicks horizontally, then 4 toothpicks vertically, nodes
marked as N:
N   N
N-N-N
N | N
N-N-N
N   N
This has 12 vertices, 13 edges, 2 faces.
Type 1:
Vertices are all end points and all mid points of toothpicks. Edges are the
halved toothpicks.
This is the computationally simplest implementation.
The number of edges is 2*A139250(n). The number of vertices is one
larger than the number of vertices for Type 0 (at the same generation)
because the initial single toothpick at n=0 is the only one which
does not stick with its midpoint at another toothpick.
Example for generation n=3:
N   N
N-N-N
N N N
N-N-N
N   N
This has 13 vertices, 14 edges, 2 faces.

Type 2:
Vertices are exposed end points, or end points that are also midpoints
(of other toothpicks) or points that are shared by 3 or more toothpick ends.
This graph is obtained from Type 1 by elimination of all joints of just
two toothpick ends (ie, elimination of vertices of degree=2, independent
of whether the angle at the joint is 180 or 90 degrees).
Example for generation n=3:
N   N
N-N-N
| | |
N-N-N
N   N
This has 10 vertices, 11 edges, 2 faces.

Above, faces = 1+edges -vertices (Euler's formula, not counting the exterior
face).

I assume that the number of faces is the same for all three types.

The number of vertices would be some mean to define the fractal dimensions
as the number of toothpicks grows infinitely. Essentially this allows
discussions in terms of percolations, electric networks etc.

Can anyone verify the following counts ?

Number of faces (any of the three types of graphs) for n=0,1,2,...:

0,0,0,2,4,4,8,18,24,24,28,36,40,44,64,94,108,108,112,120,124,128,148,176,188,
192,208,228,240,268,340,418,448,448,452,460,464,468,488,516,528,532,548,568,
580,608,680,756,784,788,804,824,836,864,932,1000,1028,1052,1104,1156,1208,1336,
1560,1750,1812,1812,1816,1824,1828,1832,1852,1880,1892,1896,1912,1932,1944,
1972,2044

First differences of the previous sequence:

0,0,2,2,0,4,10,6,0,4,8,4,4,20,30,14,0,4,8,4,4,20,28,12,4,16,20,12,28,72,78,
30,0,4,8,4,4,20,28,12,4,16,20,12,28,72,76,28,4,16,20,12,28,68,68,28,24,52,52,
52,128,224,190,62,0,4,8,4,4,20,28,12,4,16,20,12,28,72

Number of vertices (Type 0), for n=0,1,2,3,...:

0,2,6,12,18,26,38,52,62,70,82,98,118,146,182,216,234,242,254,270,290,318,354,
390,418,446,486,538,606,698,802,884,918,926,938,954,974,1002,1038,1074,1102,
1130,1170,1222,1290,1382,1486,1570,1614,1642,1682,1734,1802,1894,2002,2102,
2186,2282,2414,2586,2814,3102,3390,3584,3650,3658,3670,3686,3706,3734,3770,
3806,3834,3862,3902,3954,4022,4114,4218

First differences of this:

2,4,6,6,8,12,14,10,8,12,16,20,28,36,34,18,8,12,16,20,28,36,36,28,28,40,52,68,
92,104,82,34,8,12,16,20,28,36,36,28,28,40,52,68,92,104,84,44,28,40,52,68,92,
108,100,84,96,132,172,228,288,288,194,66,8,12,16,20,28,36,36,28,28,40,52,68,92,
104

Number of vertices (Type 2), for n=0,1,2,3,...:

0,2,6,10,14,22,34,42,46,54,66,78,94,122,154,170,174,182,194,206,222,250,282,
302,318,346,382,422,482,570,650,682,686,694,706,718,734,762,794,814,830,858,
894,934,994,1082,1162,1198,1214,1242,1278,1318,1378,1466,1550,1606,1666,1758,
1870,2010,2218,2474,2666,2730,2734,2742,2754,2766,2782,2810,2842,2862,2878,
2906,2942,2982,3042,3130,3210

First differences of this:

2,4,4,4,8,12,8,4,8,12,12,16,28,32,16,4,8,12,12,16,28,32,20,16,28,36,40,60,88,
80,32,4,8,12,12,16,28,32,20,16,28,36,40,60,88,80,36,16,28,36,40,60,88,84,56,60,
92,112,140,208,256,192,64,4,8,12,12,16,28,32,20,16,28,36,40,60,88,80

Richard

```