Math Homework Help - Page 2

On April 19 2008 12:36 azndsh wrote:
if you fix 5 coordinates, the remaining 2 coordinates determine a unit square... thus 632

On April 19 2008 16:10 azndsh wrote:
typo, sorry hehe
definitely 672

On April 20 2008 16:49 sigma_x wrote:
What your method exhibits is the following:
Sum( C(n,k)C(k,m) ) = 2^(n-m) C(n,m) for an "n" dimensional cube within which we select "m" dimensional cubes. So, for example, a 3-dimensional cube has 6 2-dimensional cubes (faces).

We shall prove the identity by double-counting. The right hand side is readily solvable by graph theory. Each n dimensional cube has 2^n vertices. Now, there are C(n,m) ways of selecting an m-th dimensional cube. Further, each selected m-th dimensional cube has 2^m vertices, so that we have 2^n * C(n,m)/2^m and we are done.

For the second method, place the n-th dimensional cube on a Cartesian plane. Let the cube have side length 2. Then each vertex can be specified by (±1,±1,±1,...,±1,±1). Now, for any given vertex defined by a set of coordinates, we can change m of them (from +1 to -1 and vice versa) and the vertex will still lie on the m-th dimensional cube. Further, these two points define a unique m-cube (since this is the maximal number of coordinates that can be changed for both coordinates to lie on the same m-cube).

Now, there are C(n,m) ways of selecting m coordinates (and assign them the value +1). For each of these, m of them can be changed to -1 C(m,m) ways. Together, these two points define a unique m-cube. Thus, there are C(n,m)C(m,m) ways of doing this. Now, do the same by assigning m+1 coordinates +1, C(n,m+1) ways. For each of these, m of them can be changed to -1, C(m+1,m) ways. Thus, there are C(n,m+1)C(m+1,m) ways of doing this. We repeat this process until we are assigning n coordinates +1, of which we change m of them to -1. Since this process is mutually disjoint, and covers all m-cubes, the total number of m-dimensional cubes in an n-dimensional cube is
Sum( C(n,k)C(k,m) ).

This completes the proof and explains why your process works.

Edit: lol, i didn't actually answer the question. Let n=7, m=2, and we have C(7,2)C(2,2)+C(7,3)C(3,2)+C(7,4)C(4,2)+C(7,5)C(5,2)+C(7,6)C(6,2)+C(7,7)C(7,2)=21x1 + 35x3 + 35x6 + 21x10 + 7x15 + 1x21 = 2^5 C(7,2) = 672