Re: Hypercube

[David Bowman <David_Bowman@GEORGETOWNCOLLEGE.EDU>]

Regarding John D.'s comment about the vertices of a hypercube:
>  ...
> 4) In computer architecture, it is common to connect multiprocessors using
> a the topology of a hypercube.  Note that a plain old 3-cube has 8 corners,
> each of which is connected to 3 neighbors;  in a hypercube there are 2^D
> nodes each of which is connected to D neighbors.  ...

This has inspired me to propose problem/puzzle about how various
dimensionality hypercubes are put together in terms of lower dimensional
hypercubes.  Let's first define a *single point* (such as a vertex or
corner that lies at the ends of various line segments or edges in a
higher dimensional hypercube as a 0-dimensional hypercube (or 0-cube for
short).  We define a *line segment* that defines a common edge of some
squares that bound a higher dimensional hypercube as a hypercube of
dimension 1 (or 1-cube for short).  In this case we consider the line
segment/edge/1-cube as an open set that does *not* include its end
points.  We define a *square* that forms common faces on the boundary of
a higher dimensional hypercube as a 2-dimensional hypercube (or 2-cube
for short).  In his case we consider the 2-cube to *only* include the
open set interior of the square *not* including its outer boundary edges.
We iterate these constructive definitions in higher dimensions as needed
to discuss the boundary of some given hypercube.  In each case the
definition of a given boundary hypercube is supposed to only include its
*interior* points as an open set and *not* include any of its own
boundary.  So in general a D-cube will be bounded by a collection of
(D-1)-cubes.  Each of these will, in turn, be bounded at common joints by
a collection of (D-2)-cubes. These, in turn will be bound and joined
together by a collection of (D-3)-cubes.  This continues until we go all
the way down to the 0-cube vertices or corners of the original hypercube.

For instance, if we considered the set made up of a single 1-cube and its
boundary this set would consist of 2 0-cubes at the ends of the 1-cube
*and* would include the 1-cube itself.  (IOW, the closed line segment is
made of the segment's interior and its two end points.)

If we considered the closed set made up of a single 2-cube *and* its
complete boundary set, that set would be made of 4 0-cubes (i.e.
vertices), 4 1-cubes (i.e. edges), and 1 2-cube (interior of the square).

If we considered the closed set of an ordinary cube including all of its
boundary that set would consist of 8 0-cubes (vertices), 12 1-cubes
(edges), 6 2-cubes (faces), and 1 3-cube (interior of the cube).

Now consider a generic D-cube (i.e. D-dimensional hypercube) whose
boundary is made up of various lower dimensional hypercubes.  Let N(D,n)
be the total number of n-cubes that are included in the set comprising
the original D-cube *and* all of its boundary pieces.

Question A: What is the closed form formula for N(D,n)?

Question B: What is the closed form sum total number S(D) of 'parts' that
            make up the complete closed set of the D-cube *and* all of
            its boundary pieces?  IOW, S(D) = SUM{n = 0 to D, N(D,n)}.
            Find S(D) in closed form.

Hints: From our above discussion we know that:

      N(0,0) = 1
      N(1,0) = 2   N(1,1) = 1
      N(2,0) = 4   N(2,1) = 4   N(2,2) = 1
      N(3,0) = 8   N(3,1) = 12  N(3,2) = 6  N(3,3) = 1

Have fun!

David Bowman
David_Bowman@georgetowncollege.edu