On April 19 2008 12:36 azndsh wrote:
if you fix 5 coordinates, the remaining 2 coordinates determine a unit square... thus 632
if you fix 5 coordinates, the remaining 2 coordinates determine a unit square... thus 632
^there
Blogs > micronesia |
micronesia
United States24343 Posts
On April 19 2008 12:36 azndsh wrote: if you fix 5 coordinates, the remaining 2 coordinates determine a unit square... thus 632 ^there | ||
azndsh
United States4447 Posts
definitely 672 | ||
micronesia
United States24343 Posts
On April 19 2008 16:10 azndsh wrote: typo, sorry hehe definitely 672 All right, cool. I know how to calculate the answer to it (I showed the work above, sort of) but I have absolutely no understanding of it. | ||
sigma_x
Australia285 Posts
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 | ||
micronesia
United States24343 Posts
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 Every time someone attempts to explain this to people who haven't learned about it already, it seems to result in them going 'HUH?' I guess only those who study the proper topics in college will get what the hell this means. | ||
| ||
StarCraft 2 StarCraft: Brood War Britney 28436 Dota 2Sea 8275 GuemChi 3594 Calm 3553 firebathero 2740 Bisu 1782 Larva 961 Horang2 939 Pusan 532 Shuttle 524 [ Show more ] Counter-Strike Other Games summit1g10131 singsing1998 B2W.Neo1533 DeMusliM721 shoxiejesuss636 crisheroes437 ArmadaUGS428 Lowko169 NuckleDu105 Crank 17 Organizations StarCraft 2 StarCraft: Brood War StarCraft 2 StarCraft: Brood War
StarCraft 2 • intothetv StarCraft: Brood War• aXEnki • Gussbus • Kozan • IndyKCrew • LaughNgamez Trovo • Laughngamez YouTube • Migwel • Poblha League of Legends Other Games |
Kung Fu Cup
H.4.0.S
GSL Code S
herO vs Reynor
soO vs GuMiho
World Team League
Korean StarCraft League
Replay Cast
World Team League
Chat StarLeague
H.4.0.S
BSL
[ Show More ] Chat StarLeague
Sparkling Tuna Cup
World Team League
BSL
ForJumy Cup
|
|