Counting problems on lattices

Question

I'm very curious to learn whether there are counting techniques that can be used to simplify counting problems on lattices.

Let us take an example:

• Say we have a $10$ by $10$ square lattice, and we want to count all combinations of pairs of points whose coordinates differ by $\Delta_{x} = \pm 1$ and $\Delta_{y} = \pm 1$.
  
  In words: all pairs of points that are diagonal to one another and distant by only one point in between them.
• So if we treat the lattice as a matrix, the pair with indices $\left(0,0\right)$ and $\left(1,1\right)$ would be one example.
• But how many possible combinations are there in total ?.
• Can the structure of the lattice be leveraged to simplify such counting problems ?.

Answer 1

Define a "single square" as a $1\times 1$ grid, and a "single diagonal" as a diagonal across a single square.

For each single square, there are $2$ single diagonals, each connecting a pair of points where $|\Delta x|=1,|\Delta y|=1$.

Consider an $n\times n$ grid from $(0,0)$ to $(n,n)$.

There are $n^2$ single squares.

Hence there are $\color{red}{2n^2}$ single diagonals, and correspondingly, the same number of point pairs where $|Δx|=1,|Δy|=1$.

Answer 2

Suppose the lattice has opposite corners at $(0,0)$ and $(n,n)$ (so it is an $(n+1)\times (n+1)$ grid.

Imagine drawing all the diagonal (45 degree) lines you can through the lattice. So there would be one line from $(0,0)$ to $(n,n)$, one from $(1,0)$ to $(n-1, n)$, etc. We need to count all the segments that make up these diagonals.

Let's just count the ones with positive slope (there will be an equal number with negative slope). The long diagonal from $(0,0)$ to $(n,n)$ will have $n$ segments of the type you are counting. The two closest parallel diagonals will have $(n-1)$ segments each; the next two closest parallel diagonals will have $(n-2)$ segments each and so on. So the number of segments with positive slope will be $n + 2\cdot [(n-1)+(n-2)+...+1]$. You can use the formula for triangular numbers to get a closed form for this expression.

For the other direction (slope $=-1$) you will get the same amount. Also if your pairs are ordered (rather than unordered) you will double your result again.