pase@hubcap.UUCP (08/31/87)
[ 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