| � Provide and validate a simple expression for
� N(r,n), the number r-dimensional boundary
� hypercubes of a given n-dimensional hypercube,
N(r,n) = 2^(n-r) * (n choose r)
square:
2^1 * (2 choose 1) = 4 sides
2^2 * (2 choose 0) = 4 vertices
cube:
2^1 * (3 choose 2) = 6 faces
2^2 * (3 choose 1) = 12 edges
2^3 * (3 choose 0) = 8 vertices
tesseract:
2^1 * (4 choose 3) = 8 3-faces
2^2 * (4 choose 2) = 24 2-faces
2^3 * (4 choose 1) = 32 1-faces (edges)
2^4 * (4 choose 0) = 16 0-faces (vertices)
- Jim
|
|
Re: .3
Jim, I really appreciated your direct, elegant and concise
argument (especially in light of the way I attacked it!). It took
me an embarrassing long time to finally grok the part about
"translated along along any subset of the (n-r) coordinates in
the complement" but it was well worth the effort.
For the benefit of any of the other readers who may struggle
with combinatorial arguments as I do, and did with this particular
one along with me, I understood it to mean that by an translating
an r-face through a choice of subset the (n-r) coordinates
is the same choosing whether
or not to translate (either forward or backward depending on which
keeps the face inside the cube) in each of the (n-r) complementary
directions. E.g., for a suitably choosen edge (1-face) of a cube
there are four choices of translations:
(00) - stay put
(10) - move across
(01) - move down
(11) - move across and down (order doesn't matter)
I came up a with reductionist approach which is far less direct
but perhaps interesting. It was motivated by wanting to compute the
Euler Characteristic of the boundary, Bd(I^n), of the n-dimenensional
hypercube, I^n (and therefore the Euler Characteristic of S^(n-1) the
(n-1)-dimensional hyper-sphere -- its continuous equivalent. I'm
aware that this can also be done with simplexes as is standard in
a course in Alg. Top., however I thought a cube approach might lead
to a geometrically simplier argument.)
Reductive observation:
The n-dimenensional hypercube, I^n, can be generated by
unit parallel translation of an I^(n-1). In the process,
each of the I^(n-2) boundary component faces of the
moving I^(n-1), sweeps out a unique I^(n-1) face of I^n.
If we add to this, the final and initial position of the
moving I^(n-1) face, we obtain the relation:
N(n-1,n) = N(n-2,n-1) + 2
More generally, each I^(r-1) component of the sweeping
I^(n-1) face generates a unique I^r component of I^n. This together
with the initial and final positions of each I^r component in the
the sweeping I^(n-1) yields the recurrance relation:
N(r,n) = N(r-1,n-1) + 2 N(r,n-1)
With the aim of eventually computing the Euler characteristic
(a generalization of the V-F+E invariant for surfaces), consider
the polynomial C_n(x) in x of degree n with coefficients N(r,n):
n
___ r
C_n(x) = > N(r,n) x
---
r=0
Using the above recurrance relation we obtain
C_n(x) = x C_n-1(x) + 2 C_n-1(x) = (2 + x) C_n-1(x)
Which inductively results in
n
C_n(x) = (2 + x) , whose coefficients yield
n-r
N(r,n) = c(r,n) 2 , where c(r,n) is "r choose n".
Since the Euler characteristic is just the alternating sum of the
number of boundary components of fixed dimension, we get
n
n ___ r
Euler_char (I) = > N(r,n) (-1) = C_n(-1) = 1
---
r=0
Finally, the Euler characteristic of Bd(I^n) is just the C_n(-1) minus
its last term , we get:
n n
Euler_char (Bd(I^n)) = C_n(-1) - (-1) = 1 - (-1)
/ 0 if n is even
= |
\ 2 if n is odd
-Franklin
|