Unit cubes
kunzmilan
2-dimensional cube (square) has 4 sides.
3-dimensional cube has 6 sides.
Return back: 1-dimensional cube (abscissa) has 2 sides (end points).
0-dimensional cube (empty space) has none side.
Each space dimension must be filled from two directions.
>Generating function: (1 + e_j)^n.
1 = (e_j)^0.
(1 + e_j)^0 = 1.
(1 + e_j)^2 = 1 + a + b + ab.
>Vertices of unit cubes:
1
1;a
1;(a,b); ab
1;(a,b,c);(ab,ac,bc);abc
They are counted by the binomial coefficients.
>Paths over vertices [(1), {(1-a),(1-b)}, {(1-a-ab),(1-b-ab)}]:
1
1;1
1;2;2
1;3;6;6
They are counted by the growing factorial.
>These reccurencies justify the definition of the empty space.
kunzmilan
Dave L. Renfro
[Remarks about n-cubes]
The following might be of interest.
A square is bounded by 4 vertices and 4 edges. A cube
is bounded by 8 vertices, 12 edges, and 6 squares. There
exists an explicit recursively given formula for the
number of k-cubes that bound an n-cube, where n and k
are nonnegative integers such that 0 <= k <= n.
THEOREM 1: If F(n,k) denotes the number of k-cubes that
bound an n-cube, then F satisfies the following double
recursion:
1. F(n,0) = 2^n
2. F(n,n) = 1
3. F(n,k) = 2*F(n-1, k) + F(n-1, k-1) [1 <= k <= n-1]
PROOF: The equality F(n,n) = 1 is immediate. To obtain
the other two equalities, note that we can obtain an
n-cube C_n by taking the union of all the points traversed
when an (n-1)-cube C_(n-1) is translated in a direction
that is perpendicular to each of the edges in C_(n-1) for
a distance that is equal to the length of an edge in C_(n-1).
Since the number of vertices doubles each time this action
is carried out, and repeating this action n times beginning
with a point gives an n-cube, it follows that F(n,0) = 2^n.
The remaining equality is the result of adding the k-cubes
in the beginning copy of C_(n-1) with the k-cubes in the
ending copy of C_(n-1) with the k-cubes generated by the
translation of C_(n-1). Since a perpendicular translation
of a (k-1)-cube generates a k-cube, the k-cubes generated
by the translation of C_(n-1) arise from the (k-1)-cubes
in C_(n-1). Thus, #3 arises from the fact that F(n,k) equals
P + Q + R, where
P = F(n-1, k) = number of k-cubes in beginning C_(n-1)
Q = F(n-1, k) = number of k-cubes in ending C_(n-1)
R = F(n-1, k-1) = number of k-cubes generated by the
translation of each of the F(n-1, k-1)
many (k-1)-cubes in C_(n-1).
THEOREM 2: The number of k-cubes that bound an n-cube is the
coefficient of x^k in the expansion of (x+2)^n.
PROOF: We prove this by induction on n, using the recursion
formula above. Thus, our statement S_n is: "For each 0 <= k <= n,
the number of k-cubes in an n-cube is the coefficient of x^k
in the expansion of (x+2)^n." The result is clearly true for
n=0 (and also for n=1,2 if the zero-dimensional statement seems
uncomfortably vacuous). Assume the result is true for n=m. Then
the number of k-cubes in an m-cube is the coefficient of x^k in
the expansion of (x+2)^m. By the recursion formula above, the
number of k-cubes in an (m+1)-cube is the coefficient of x^k in
the expansion of 2*(x+2)^m + x*(x+2)^m = (x+2)^(m+1). Therefore,
the result is true for n=m+1. [Technical Note: Because 0 <= k <= m
(we began this last part by considering k-cubes in an m-cube),
we have actually only verified the result for 0 <= k < m+1, and
hence we have not completely verified the statement S_(m+1).
However, it is trivial to verify the result for k=m+1, namely
that the number of (m+1)-cubes in an (m+1)-cube is the coefficient
of x^(m+1) in the expansion of (x+2)^(m+1). Note that we only
need to prove S_(m+1) follows from S_m. It is not relevant
whether we are able to do this entirely from recursion formula.]
NOTE: A proof of Theorem 2 that is independent of Theorem 1
can be found in Banchoff [1] (p. 76) and Henry [2].
[1] Thomas F. Banchoff, "Beyond the Third Dimension: Geometry,
Computer Graphics, and Higher Dimensions", Scientific
American Library, 1990, xii + 210 pages.
[MR 91h:00001; Zbl 771.51002]
[2] Boyd Henry, "The fourth dimension and beyond...with a surprise
ending!", Mathematics Teacher 67 #3 (March 1974), 274-279.
Specifically, Banchoff [1] (p. 76) says:
"There are n edges emanating from each vertex, and we get a
k-cube for any subset of k distinct edges from among these n edges.
Therefore the number of k-cubes at each vertex of an n-cube is
C(k,n) = n! / [k!*(n-k)!], the combinations of n things taken
k at a time. Since we have C(k,n) k-cubes at each of the 2^n
vertices, we obtain a total number 2^n * C(k,n). But in this
count, each k-cube is counted 2^k times, so we divide by that
number to get the final formula ..."
At a more advanced level, quite a bit more about n-cubes can
be found in the following survey article (available on-line,
without a subscription):
[3] Chuanming Zong, "What is known about unit cubes", Bulletin
of the American Mathematical Society 42 #2 (2005), 181-211.
http://www.ams.org/journals/bull/2005-42-02/
Dave L. Renfro