1
$\begingroup$

So here is Question :-

A triangular grid of side $n$ is formed from $n^2$ equilateral triangles with sides of length $1$.Determine the number of parallellograms.

First of all , by reading the question I can understand that the answer should be evaluated by some kind of counting or combinatorial shortcut . But I really don't know what formula I can use to find the no. of parallelograms of a triangular grid of side $n$. Can anyone help with some explanation ?

$\endgroup$
1
  • $\begingroup$ I think the parallelograms come in three different orientations, so the answer is three times the number of parallelograms in your favourite orientation (say with the point corners pointing up and down). $\endgroup$ Jun 13 '20 at 15:15
2
$\begingroup$

Separate the parallelograms into the 3 directions that they point in. Focus on a single direction.

Hint: Extend the setup by 1 more row.

For a given parallelogram, extend the 4 edges till they hit the extended row. This determines 4 unique points.
This is illustrated by the red parallelogram, whose edges are extended.

enter image description here

Conversely, given these 4 points, we can reconstruct the parallelogram by following the edges.
E.g. For the 4 yellow dots, which parallelogram do they determine?

Hence, there are $ 3 \times { n + 2 \choose 4 } $ parallelograms.

$\endgroup$
4
  • $\begingroup$ Sorry to say this but this is an artificial solution. Why did you extend it, I mean, how you think about it? $\endgroup$
    – Aqua
    Jun 14 '20 at 11:49
  • $\begingroup$ @Aqua This is a "well-known elegant one-liner approach". Extending the sides of the parallelogram isn't that artificial, and after that we're forcing out the ${n+ 2 \choose 4 }$ and also the uniqueness of the bijection. I agree it's not the first approach one would take to the counting, since the brute force approaches work really well here. $\endgroup$
    – Calvin Lin
    Jun 14 '20 at 13:45
  • $\begingroup$ And what make you thinking about extending it? $\endgroup$
    – Aqua
    Jun 14 '20 at 13:50
  • $\begingroup$ Honestly speaking, because I saw it done that way before. Though, if you look at it, the "parallelograms where one vertex doesn't touch the base" gives 4 distant points, so that's ${ n + 1 \choose 4}$, and the "parallelograms where one vertex touches the base" gives 3 distinct points (with the middle repeated) so that's ${n+1 \choose 3}$, and the sum gives us ${ n + 2 \choose 4}$. The extension of the base then just "tidies" up the accounting. $\endgroup$
    – Calvin Lin
    Jun 14 '20 at 13:58
1
$\begingroup$

So we have $1+2+...+n+(n+1)= {n+2\choose 2}$ vertices determined by this grid.

Any pair, which is not on the same line determined by this grid, determine opposite vertices of some paralellogram and any parallelogram is determined by exactly one such pair.

The number of bad pairs is $$3\cdot \Big({1\choose 2} + {2\choose 2}+...+{n+1\choose 2}\Big) = {n(n+1)(n+2)\over 2}$$

So the number of good pairs is = the number of paralleograms $$ {{n+2\choose 2}\choose 2} - {n(n+1)(n+2)\over 2} =\boxed{{(n-1)n(n+1)(n+2)\over 8}} $$

$\endgroup$
1
  • $\begingroup$ Nice , clear and simple answer . Thanks $\endgroup$ Jun 13 '20 at 17:05
1
$\begingroup$

enter image description here

The parallelograms can be built in three orientations choosing (see picture) segments lying on blue-red, red-black or black-blue pairs of lines. From symmetry it is enough to count the number of parallelograms for one coloring (say blue-red).

Start the counting with the upmost red line of length 1. There is only one way to choose a pair ob blue lines and $n-1$ ways to choose the other red line. All together we have $(n-1)$ ways to construct a parallelogram. Taking the next red line (with the length 2) we have $\binom 32$ ways to choose the blue lines and $n-2$ ways to choose the other (lower-lying) red line.

Continuing in this way we find that the overall number of blue-red parallelograms is: $$ \sum_{k=1}^{n-1} \binom{k+1}2(n-k)=\frac{(n-1)n(n+1)(n+2)}{24}. $$

The total number of the parallelograms is triple of this: $$\frac{(n-1)n(n+1)(n+2)}{8}. $$

$\endgroup$

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.