2
$\begingroup$

If I have a $2\times 2\times 2\times 2$ hyper cubic lattice, how many corners, edges, faces, and cells will it be composed of? E.g. the 4D analogue of figure below. Assume the faces within the figure are filled in too. This figure has $36$ 2D faces (1x1 each), $27$ vertices, and $54$ 1D edges of length 1. (Some of the faces of the lattice are shared by more than one cell... and I don't want to double-count here).

$\hskip 2in$ hyperrectangle

$\endgroup$
1
  • $\begingroup$ That's why i said "4D analogue of". Also imagine that the imagine the 2D faces are filled in. $\endgroup$ – Bob Aug 6 '15 at 4:23
1
$\begingroup$

Let $f(n,k)$ denote the number of $k$-dimensional faces in the $n$-dimensional hpercube with sides of length $2$. Then $f(n,k)$ is the coefficient of $x^k$ in $(2x+3)^n$, in particular $$f(n,k)=\binom{n}{k} 2^k 3^{n-k}.$$ Here are the values for dimensions up through $5$:

$$\begin{array}{c|cccccc} & 0&1&2&3&4&5\\ \hline 0& 1 & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1& 3 & 2 & \text{} & \text{} & \text{} & \text{} \\ 2& 9 & 12 & 4 & \text{} & \text{} & \text{} \\ 3& 27 & 54 & 36 & 8 & \text{} & \text{} \\ 4& 81 & 216 & 216 & 96 & 16 & \text{} \\ 5& 243 & 810 & 1080 & 720 & 240 & 32 \\ \end{array} $$

If the sides of the cubes have length $r$ (so that $r=2$ in your case), then you get $( rx+ r+1)^n$ instead; in particular taking $r=1$ gives the usual formula for faces of the unit hypercube. Interestingly, the total number of faces at dimension $n$ is $(2r+1)^n$, i.e. $5^n$ in your case.

Proof: let the integer points in the grid be $\{0,\ldots,r\}$. A $k$-face has a "starting point" $(i_1,\ldots,i_n)$, and $k$ of these coordinates vary from their starting value up to the next integer. The set of valid choices for the $j$-th coordinate $i_j$ of the starting point is $\{0,\ldots,r\}$ if that coordinate is non-varying ($r+1$ choices) and $\{0,\ldots,r-1\}$ otherwise (only $r$ choices). There are $\binom nk$ ways to pick which coordinates will vary, so the number of $k$-faces is $\binom nk r^k (r+1)^{n-k}$.

Another way to see this is by induction on the dimension. The dimension-$n$ picture consists of $r+1$ copies of the dimension-$(n-1)$ picture (which we'll think of as "horizontal".) So there are two kinds of $k$-faces at dimension $n$: horizontal faces corresponding to $k$-faces one dimension down, and vertical faces which arise as the product of a horizontal $(k-1)$-face with the $1$-dimensional picture. This gives the recurrence $$f(n,k)=r\,f(n-1,k-1)+(r+1)\,f(n-1,k)$$ and you can now prove the claimed formula by inspection (or induction, if you like).

A shorter way to say this: the face-generating function at dimension $1$ is $rx + r + 1$, the $n$-dimensional cube is the product of $n$ copies of the $1$-dimensional cube, and the face generating function of the product of two cubes is the product of their face generating functions. So, in particular, if you have an $r_1\times\cdots\times r_n$ grid, then the number of $k$-dimensional faces is the coefficient of $x^k$ in the product $$(r_1x + r_1+1)\cdots(r_nx + r_n+1).$$

$\endgroup$
10
  • $\begingroup$ Thanks Tad. What do you mean by "vertical faces which arise as the product of a horizontal (k−1)-face with the 1-dimensional picture" Shouldn't you have $n\times (r+1)$ faces of dimension $(n-1)$? (For ex: In a $2\times 2\times 2$ cube, I have 3 faces at constant x, 3 faces at constant y, and 3 faces at constant z.) In this example, I think you are saying that you would pick out and label the faces at constant z as your "horizontal faces", but I don't see where you go after that. $\endgroup$ – Bob Aug 8 '15 at 22:36
  • $\begingroup$ Let's look at the 2-dimensional faces in your 3-dimensional picture, with the "horizontal" 2-dim picture being the bottom level. There are 4 squares in the bottom level; each of these get multiplied by 3 when we go up to dim 3, giving 12 horizontal squares at dim 3. But each line at the bottom gets stretched upward into 2 "vertical" squares, giving $2\times 12=24$ vertical squares. Total squares in the 3-dim picture is thus $12+24=36$. Does this help? $\endgroup$ – Tad Aug 8 '15 at 23:13
  • $\begingroup$ So you're saying to create an n-dimensional lattice with $r^n$ cells, you take a single (n-1)-face, copy it "upwards" until you have r+1 of these copies, and stretch the 0-faces into 1-faces, 1-faces into 2-faces, etc.? $\endgroup$ – Bob Aug 8 '15 at 23:31
  • $\begingroup$ Sounds like you have it! $\endgroup$ – Tad Aug 8 '15 at 23:34
  • $\begingroup$ I like the idea, but I don't see why it is obvious that this method would work in n-dimensions. Or is this where I use induction as a proof? $\endgroup$ – Bob Aug 8 '15 at 23:35
1
$\begingroup$

We can perform the same counting argument used to count the $k$-cells of an $n$-cube in order to count the $k$-cells of an $\ell_1\times\cdots\times\ell_n$ hyper-rectangle of $n$-cubes. We will do this by counting the number of marked $k$-cells in the figure (a marked $k$-cell is a $k$-cell with one of its corners "marked"). To create a marked $k$-cell, we first pick a vertex, and then pick $k$ of the edges connected to it to determine the $k$-cell the vertex is a corner of, whenever this is possible. The number of marked $k$-cells with given corner vertex $v$ is $\binom{r}{k}$, where $r=\deg(v)$.

We must determine the number of vertices $v$ with vertex degree $\deg(v)=r$ in the figure, for all possible values of $r$. Consider the $\ell_1\times\ell_2\times\ell_3$ case for inspiration. For the purpose of abbreviation, denote $t_i=\ell_i-1$ for $i=1,2,3$. There are

  • $8$ vertices $v$ with $\deg(v)=3$
  • $4(t_1+t_2+t_3)$ vertices $v$ with $\deg(v)=4$
  • $2(t_1t_2+t_2t_3+t_3t_1)$ vertices $v$ with $\deg(v)=5$
  • $t_1t_2t_3$ vertices $v$ with $\deg(v)=6$.

Consider "faces" of the hyper-rectangle of various dimensions, defined so that for instance a $3$-rectangle has one $3$-face, six $2$-faces, twelve $1$-faces and eight $0$-faces. Each face is a collection of vertices, and the set of all faces is a partition of the vertex set. For $r=n,n+1,\cdots,2n$ a vertex will have degree $r$ if and only if it is in an $(r-n)$-face.

Let $\Lambda_m$ be the set of $m$-faces. For each $m$-subset $I\subset\{1,\cdots,n\}$ let $\Lambda_m(I)$ be the subset of $m$-faces with dimensions $\prod_{i\in I}t_i$. Note that each $\Lambda_m(I)$ has the same number of $m$-faces, by symmetry. There are a total of $\binom{n}{m}$ $m$-subsets of $\{1,\cdots,n\}$, and there are $2^{n-m}\binom{n}{m}$ $m$-faces in the collection $\Lambda_m$, therefore $|\Lambda_m(I)|=2^{n-m}$ for each $I$. And so $2^{2n-r}e_{r-n}(t_1,\cdots,t_n)$ counts the number of vertices $v$ with $\deg(v)=r$. Multiply this by $\binom{r}{k}$ and sum over $r=n,\cdots,2n$ in order to get the number of marked $k$-cells. Since every $k$-cell has $2^k$ possible corners to mark, this overcounts the number of unmarked $k$-cells by a factor of $2^k$. Dividing, we get

$$\# k\textrm{-cells of an }\ell_1\times\cdots\ell_n\textrm{ hyper-rectangle} =\sum_{r=n}^{2n}2^{2n-r-k}e_{r-n}(\ell_1-1,\cdots,\ell_n-1)\binom{r}{k}.$$

$\endgroup$
3
  • $\begingroup$ did you copy this from a source? $\endgroup$ – Bob Aug 8 '15 at 2:54
  • $\begingroup$ 1. what is the figure mentioned? 2. For the case of a cubic lattice in d-dimensions, is Deg(v) = r just the number of dimensions that the lattice is embedded in? 3. Are the $t_i$ some form of vertex coordinates? 4. What is $e_{r-n}(\ell_1 -1, ...)$ $\endgroup$ – Bob Aug 8 '15 at 5:03
  • $\begingroup$ @Bob (0) No, I did this myself. I don't know of any source that addresses this combinatorial problem. (1) The "figure" is the $\ell_1\times\cdots\times\ell_n$ hyper-rectangle that is under consideration. (2) Look up "vertex degree" - it's the number of edges (for us, 1-cells) connected to it. (3) I defined $t_i=\ell_i-1$ for $i=1,2,3$ in my answer for the purpose of making the formulas smaller. (4) Look up elementary symmetric polynomials. $\endgroup$ – whacka Aug 8 '15 at 6:10
-1
$\begingroup$

Your hypercube is determined by the vertices $(0,0,0,0)$, $(0,0,0,1)$, $(0,0,1,0)$, $(0,0,1,1)$, etc. Thus there are $2^4$ vertices (one for each quadruple).

How many edges? An edge is two points that differ in only one place, such as $(0,\color{red}0,1,0)$ and $(0,\color{red}1,1,0)$. An edge is determined by the three coordinates that don't change. Thus, there are: $$\dbinom432^3=32\text{ edges};$$ $\binom43$ ways of selecting three edges and $2^3$ ways of giving them each a zero or one.

How many faces? A face is four points that differ in two places, such at $(0,\color{red}0,1,\color{red}0)$, $(0,\color{red}0,1,\color{red}1)$, $(0,\color{red}1,1,\color{red}0)$, and $(0,\color{red}1,1,\color{red}1)$. A face is determined by the two coordinates that don't change. Thus, there are: $$\binom422^2=24\text{ faces};$$ $\binom42$ ways of selecting two edges and $2^2$ ways of giving them each a zero or one.

Similarly, there are: $$\dbinom412^1=8\text{ cells}.$$

$\endgroup$
4
  • $\begingroup$ That is for a single 1x1x1x1 hypercube. I want a 2x2x2x2 hyper cubic lattice (of cells of unity volume). some of the k-dimensional faces you mention will be degenerate with each other. $\endgroup$ – Bob Aug 6 '15 at 4:36
  • $\begingroup$ This does not answer the question. $\endgroup$ – whacka Aug 7 '15 at 1:39
  • 1
    $\begingroup$ @whacka Yeah, Bob already pointed that out. :( $\endgroup$ – Akiva Weinberger Aug 7 '15 at 1:39
  • $\begingroup$ So.... ? ${}{}$ $\endgroup$ – whacka Aug 7 '15 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.