[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
More information about the SeqFan
mailing list