Number of "Overlapping" Cells Within a Hypercube 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.
 A: 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.
A: 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$
