Re: Hypercube

[David Bowman <David_Bowman@GEORGETOWNCOLLEGE.EDU>]

Regarding Ken C.'s nicely explained solution to the problem of the number
of sub-hypercubes belonging to the boundary of a generic hypercube:

> ...
> Answer to Question A:
>
>   N(D,n) = ... = 2^(D-n) D! / [n! (D-n)!]
>
> For Question B, ...
>
>   For all D>=0, S(D) = 3^D.

Muy bueno & sehr gut!

> ...
> > Have fun!
>
> Thanks, I did!

I thought you would.

Note that a tricky use of generating functions nicely encodes the problem
and its solution (without the need for messy recursion relations and
induction arguments).

Consider a generating function describing the generic D-cube problem as
being a D-degree polynomial in the variable x such that the the numerical
coefficient of the x^n term in the polynomial is N(D,n). IOW, we define:
N(D,0) + N(D,1)*x^1 + N(D,2)*x^2 + ... + N(D,D)*x^D
to represent the generating function for the D-cube problem.  When D = 1
we know we have the trivial monic 1st degree form: x + 2 for the
generating function.  Now recall that a D-cube is the D-fold *point by
point* direct product of a 1-cube.  It might not take a huge amount of
reasoning to convince yourself that the generating function for the
D-cube is just the D-th power of the generating function of the 1-cube.
This means that the generating function for the D-cube is: (x + 2)^D .
Now all we have to do to to get N(D,n) is to expand the form: (x + 2)^D
using the Binomial Theorem and find the coefficient of x^n to be:
N(D,n) = (D!/(n!*(D - n)!))*2^(D-n) , immediately giving us the answer
to part A.  To get the answer to part B we merely set x = 1 and evaluate
the numerical value of the generating function as: (1 + 2)^D = 3^D.  BTW,
the meaning of the 1 & 2 split in (1 + 2)^D is that the parts of the
D-cube and its boundary are the direct product taken D times of the
*1* interior piece of a line segment and its *2* endpoints.

David Bowman
David_Bowman@georgetowncollege.edu