1
$\begingroup$

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 ?.
$\endgroup$
5
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ what about the corner points? Should it not be $2n^2 - 4$? $\endgroup$ – Ma0 Nov 17 '16 at 16:35
  • $\begingroup$ @Ev.Kounis - Consider the case where $n=1$ in which case there are only $2$ pairs of such points. $\endgroup$ – hypergeometric Nov 17 '16 at 16:38
  • $\begingroup$ Very true. Thanks! $\endgroup$ – Ma0 Nov 17 '16 at 16:43
  • $\begingroup$ Thanks a lot for your answer. Im curious, how extensible is this way of counting to changing deltas? E.g. if we set now $|\Delta_{x,y}|=2$, is the count of corresponding diagonals $2(n-1)^2$? $\endgroup$ – user929304 Nov 17 '16 at 18:05
  • $\begingroup$ You're welcome. That sounds quite reasonable. $\endgroup$ – hypergeometric Nov 18 '16 at 3:01
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ wouldn't it be a $n\times n$ grid? otherwise, for instance, if $n=0$, which is a point, but a $1\times 1$ grid is a single square. $\endgroup$ – hypergeometric Nov 17 '16 at 16:08
  • $\begingroup$ @hypergeometric Counting by squares it's $n\times n$. Counting by lattice points it's $(n+1)\times (n+1)$. $\endgroup$ – paw88789 Nov 17 '16 at 16:28
  • $\begingroup$ agreed. that's correct. $\endgroup$ – hypergeometric Nov 17 '16 at 16:29
  • $\begingroup$ Very informative, thanks! $\endgroup$ – user929304 Nov 17 '16 at 18:06

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.