1
$\begingroup$

I have a hypercube in $k$-space which is divided along each dimension into $n$ cells. Each cell in the hypercube is assigned a unique ordered set of coordinates as follows:

$(a_{1}, a_{2}, a_{3}, ... , a_{k})$

Given a particular cell, I'd like to derive a closed form for the number of cells that "overlap," or share at least one coordinate with, that cell (inclusive). For example, for $n = 3$ and $k = 3$, the number of "overlaps" for any particular cell should be $20$.

I know that number of possible $combinations$ where at least one coordinate is shared is:

${k\choose 1} * n^{k-1}$ ,

since there are $n$ possibilities for each coordinate that is not shared.

Obviously this overstates the number of "overlapping" cells, since it double-counts cells that overlap in multiple dimensions. So how would I proceed to find a closed form from here (I know it probably involves inclusion-exclusion)?

Thank you in advance.

$\endgroup$
3
  • $\begingroup$ Inclusion-Exclusion should work here. Subtract the cases where two coordinates are the same. Now you're undercounting a bit. So add the cases where $3$ are the same, and so on. This will resolve into a nice binomial theorem sum with a couple of terms missing. $\endgroup$ Oct 29, 2015 at 3:28
  • $\begingroup$ For $k = 3$, do the cells $(0,0,0)$ and $(0,2,2)$ overlap, since they share a coordinate? But the cells $(0,0,0)$ and $(1,1,1)$, which meet at a single vertex, do not overlap; is that correct? $\endgroup$
    – David K
    Oct 29, 2015 at 3:37
  • $\begingroup$ That's correct - (1, 1, 1) and (0, 0, 0) do not overlap. Thank you stochasticboy321, it does indeed become a binomial theorem sum! $\endgroup$ Oct 29, 2015 at 3:42

2 Answers 2

1
$\begingroup$

Supposing the range of coordinates is from $1$ to $n$, you can count the number of overlapping cells by examining the cell at coordinates $(n, n, \ldots, n)$, that is, $(a_1, a_2, \ldots, a_k)$ where $a_1 = a_2 = \ldots = a_k = n$. Every cell has the same number of overlapping cells, which can be shown for any other cell $C$ by swapping "slices" of the cube until cell $C$ is moved to the coordinates $(n, n, \ldots, n)$.

For any other cell at coordinates $(b_1, b_2, \ldots, b_k)$, in order for that cell not to overlap the cell at $(n, n, \ldots, n)$, it must be the case that $b_i < n$, and therefore $1 \leq b_i \leq n - 1$, for every $i$. That is, $(b_1, b_2, \ldots, b_k)$ must be a cell of a hypercube divided $n - 1$ times in each dimension. Moreover, no cell of that hypercube overlaps the cell at $(n, n, \ldots, n)$.

So the number of cells that overlap $(n, n, \ldots n)$ is the number of cells in the $n \times n \times \cdots \times n$ hypercube, excluding the cells in an $(n-1) \times (n-1) \times \cdots \times (n-1)$ hypercube within the larger hypercube. If you say that the cell $(n, n, \ldots, n)$ overlaps itself, then the number of overlapping cells is

$$ n^{k} - (n - 1)^{k}. $$

If you do not want to say that a cell overlaps itself, then subtract $1$ from that total.

$\endgroup$
0
$\begingroup$

There are $n^k$ total cells. For a cell to not overlap, we must change all the coordinates and have $n-1$ choices for each one. There are $(n-1)^k$ non-overlapping cells, so $n^k-(n-1)^k-1$ other cells that overlap. For $n=k=3$ that gives $18$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .