[seqfan] a question about arrangements of pennies

N. J. A. Sloane njas at research.att.com
Mon Dec 14 05:02:26 CET 2009


Dear Seq Fans,  J. Lowell submitted a sequence today
which I am still stuggling with.  His definition and terms 
seemed unsatisfactory.  

First let me state a simpler question.  

1.  Take the standard triangular lattice packing
of pennies, in which each penny touches 6 others.
How many ways are there to pick n pennies (modulo
rotations and reflections) such that if you construct 
the graph with nodes = centers of pennies,
edges = pairs of touching pennies,
then this graph is connected and every edge
belongs to at least one triangle?

Here's what I get for the first few cases:
n  1 2 3 4 5 6 7
#  1 0 1 1 2 3 6

Here they are:
 o
o o

 o
o o
 o

 o o
o o o

   o
o o o
 o

I'll skip 6

 o o o
o o o o

 o o
o o o
 o o

  o o
 o o
o o o

   o o
o o o o
 o

   o o
  o o o
 o o

   o
o o o o
 o   o

This may well be in the OEIS already.  It reminds me of the problems Ron Graham and I looked at in this paper:
Penny-Packing and Two-Dimensional Codes, R. L. Graham and N. J. A. Sloane, Discrete and Comput. Geom., 5 (1990), pp. 1-11.  (Available from my home page, Pub List, item 138)


2.  J Lowell asked (in effect) how many of these arrangements of
pennies are "rigid", without defining the term.

This is not "rigid", for example,

   o
o o o
 o

because the central node can act as a hinge,
and one triangle can rotate with respect to the other.

There are several ways to enforce rigidity.  Perhaps
the best is to add a further constraint to the first 
problem.  Form a second graph with nodes = triangles,
edges = two triangles that share an edge.  Then this second graph
must be connected.

For this arrangement
   o
o o o
 o
the second graph contains 2 isolated nodes, so is ruled out.

Here are Lowell's values, as corrected by me:

%S A171604 1,0,1,1,1,3,4


Can anyone compute a few more terms of either sequence?

Neil





More information about the SeqFan mailing list