Problem: How many vertices, edges, faces has the cube? Whats about the hypercube? Solution: Let's call k-cubes the k-dimensional hypercube. So vertices are 0-cubes, edges 1-cubes, squares 2-cubes and so one. Let c(n,k) be the number of k-cubes contained in an n-cube. There is a simple formula for this number c(n,k) = binomial(n,k)*2^(n-k) and a easy combinatorial explanation for it. Another way the find these numbers are their generating function (2 + x)^n = c(n,0) + c(n,1) x + c(n,2) x^2 + ... + c(n,n) x^n The binomial expansion of (2 + x)^n gives again c(n,k). Let's look at an example. (2 + x)^3 = 8 + 12x + 6x^2 + x^3 So the cube has 8 vertices, 12 edges, 6 faces, 1 cube. As (2 + x)^(n+1) = (2 + x)^n (2 + x) we immediatly get the recursion formula c(n+1,k) = 2 c(n,k) + c(n,k-1). Can you explain these Pascal like recursion in a combinatorial way? There is a further application for these polynomials. Evaluate them at 1 and at -1. You get interesting things (2 + 1)^n = c(n,0) + c(n,1) + c(n,2) + ... + c(n,n) = 3^n (2 - 1)^n = c(n,0) - c(n,1) + c(n,2) - ... + c(n,n) (-1)^n = 1 The alternating sum is the Euler characteristic. This is the general version of Euler's formula: V-E+F=2. Table of coefficients of c(n,k). n 0: 1 1: 2 1 recursion: 2: 4 4 1 x y 3: 8 12 6 1 x+2y 4: 16 32 24 8 1 5: 32 80 80 40 10 1 Table of the trinomial coefficients t(p,q,r) and their row sums. (other names are Pascal's Tetrahedron, Pascal's Pyramid) 1 1 1 1 1 1 2 1 1 2 2 4 1 2 1 4 1 1 3 3 6 3 6 3 12 1 3 3 1 8 1 1 4 4 8 6 12 6 24 4 12 12 4 32 1 4 6 4 1 16 1 1 5 5 10 10 20 10 40 10 30 30 10 80 5 20 30 20 5 80 1 5 10 10 5 1 32 Generating function of the trinomial coefficients: (x + y + z)^n = Sum_{p,q,r>=0, p+q+r=n} t(p,q,r) x^p y^q z^r. Recursuion formula: t(p,q,r) = t(p-1,q,r) + t(p,q-1,r) + t(p,q,r-1) t(0,0,0) = 1 t(p,q,r) = 0 if p<0 or q<0 or r<0. Formula: t(p,q,r) = (p+q+r)! / (p!*q!*r!) = binom(p+q, p) * binom(p+q+r, r) Appendix: EIS: http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=038207 %I A038207 %S 1,2,1,4,4,1,8,12,6,1,16,32,24,8,1,32,80,80,40,10,1,64,192,240,160,60, %T 12,1,128,448,672,560,280,84,14,1,256,1024,1792,1792,1120,448,112,16,1, %U 512,2304,4608,5376,4032,2016,672,144,18,1,1024,5120,11520,15360,13440 %N Triangle whose (i,j)-th entry is binomial(i,j)*2^(i-j). %C This infinite matrix is the square of the Pascal matrix (A007318) whose rows are [ 1,0,... ], [ 1,1,0,... ], [ 1,2,1,0,... ],... As an upper right triangle, table rows give number of points, edges, faces, cubes, 4D hypercubes etc. in hypercubes of increasing dimension by column. - Henry Bottomley (se16@btinternet.com), Apr 14 2000 %e 1; 2,1; 4,4,1; 8,12,6,1; 16,32,24,8,1; ... %o (PARI) T(n,k)=polcoeff((x+2)^n,k) - Michael Somos, Apr 27 2000 References: AMB (Aaron Burnham); Hyper-Dimensional Links http://www.cs.mu.oz.au/~amb/4d/ Banchoff Thomas F.; Beyond the Third Dimension, (1990) New York: W. H.Freeman & Co., Scientific American Library (german: Dimensionen. Figuren und Körper in geometrischen Räumen, Spektrum Akademischer Verlag, Heidelberg (1991) Bibliothek Spektrum der Wissenschaft, Band 31) Thorleif Bundgaard; Cubes in 4 dimensions, http://www.fam-bundgaard.dk/SOMA/NEWS/N010920.HTM Vladimir Dubrovsky; The multidimensional cube, an introduction and a quick tour, Quantum 7:1 (Sept/Oct 1996) 4-9, 63 Jürgen Köller; Hypercube (Hyperkubus), http://www.mathematische-basteleien.de/hyperkubus.htm (German) http://www.mathematische-basteleien.de/hypercube.htm (English) Martin Gardner; Mathematical Carnival, A. Knopf (1975) (german: Mathematischer Karneval, Frankfurt am Main, 1977) Chap. 4: Hypercubes - shows the generating polynomial (2x + 1)^n that gives the reverse order. Jan Huber; Problem G-3, American Mathematical Association of Two-Year Colleges, 6 (1984/1) 55 proposal: Jan Huber 7 (1986/2) 77 solution: William P. Wardlaw 7 (1986/2) 78 solution: Jan Huber Consider an n-dimensional cube, and reagard 0-dimensional components as vertices, 1-dimensional components as edges, 2-dimensional components as two-dimensional faces, etc. Prove that the number of k-components in an n-dimensional cube is equal to the k-th term in the expansion of (2 + 1)^n for k = 0, 1, 2, ..., n. F. Nedemeyer, Y. Smorodinsky; Resistances in the multidimensional cube, Quantum 7:1 (Sept./Oct. 1996) 12-15 and 63 Rudy Rucker; HYPERCUBE98. Tumbling Hypercubes. http://www.mathcs.sjsu.edu/faculty/rucker/index.html Ju. A. Saskin; Ecken, Flächen, Kanten, Deutsch Taschenbücher Band 59, Harri Deutsch Verlag, 1989, ISBN 3-8171-1012-X - Euler characteristic N. J. A. Sloane, S. Plouffe; The Encyclopedia of Integer Sequences, Academic Press, (1995) http://www.research.att.com/~njas/sequences/ Eric F. Weinstein; Hypercube, http://mathworld.wolfram.com/Hypercube.html Mike D'Zmura; The 4D Web Page, http://www.cvr.uci.edu/dzmura/4D/ References: Pascal's Tetrahedron, Pascal's Pyramid, Trinomial Coefficients Stephen Mueller; Recursions Associated with Pascal's Pyramid, Pi Mu Epsilon Journal, (Spring 1969) 417-422 John A. Price; Pascal Pyramid, Mathematics Teacher, 72:1 (Jan. 1979) 4, 14 Alice Schwandt, Janet Lind; Revisiting Pascal's Pyramid, Mathematics Teacher, 72:2 (Feb. 1979) 84-86 - Pascal's triangle in three dimensions and a vareity of applications. Janet Shorter, F. Max Stein; Pascal's Tetrahedron and the Trinomial Coefficients, The Pentagon 42 (Fall 1982) 19-33 - containing a short bibliography John Staib, Larry Staib; The Pascal Pyramid, Mathematics Teacher, 71:6 (Sep. 1978) 505-510 - patterns of the coefficients in the expansion of (x + y + z)^n. -- http://www.mathematik.uni-bielefeld.de/~sillke/ mailto:Torsten.Sillke@uni-bielefeld.de