🚀 go-pugleaf

[ I took the liberty of combining an immediate followup by Doug to this
  article.
	Steve]

While working on a problem concerning the topology of binary n-cubes (or
hypercubes, if you wish), something caught my eye.  I was looking at the number
of nodes at a certain distance from a root node, and I noticed the following:

				dimension
	distance	0	1	2	3	4
	-------------------------------------------------
   	0...............1	1	1	1	1
   	1.......................1	2	3	4
   	2...............................1	3	6
   	3.......................................1	4
   	4...............................................1

You probably guessed it -- Pascal's triangle.  If n = dimension and
r = distance, the number of nodes at distance r is

			  n!
		      ----------
		       r! (n-r)!

Does anyone out there have some reasonable justification for this?  Or better
still, do you have a reference where it is proven this is so?  In this case a
reference would be better than a proof.  Any help you might be able to give
would be highly appreciated.  (I suppose I could just label it "a well known
fact".)

Doug's answer to himself:

<> Little did I know, the answer is *very* easy.  This formula also describes the
<> number of combinations of n objects taken r at a time.  Consider the cube
<> dimension n to be a vector of n bits whose values are either 1 or 0.  Since the
<> root node's vector contains all zeros, the distance from the root to any node
<> is simply the number of ones which occur in its vector.  The number of vectors
<> where exactly r bits are set is simply the number of combinations of n bits
<> taken r at a time, which is also the number of nodes at distance r.
<> 
<> *NOW* I can label it as "a well known fact".
--
Doug Pase   --   ...ucbvax!tektronix!ogcvax!pase  or  pase@Oregon-Grad.csnet