Number of parallelograms in two rows of 7 dots

Question

I'm going through Oscar Levin's discrete mathematics intro book, and one of the problems in the combinations/permutations section asks how many parallelograms can be created with two rows of seven dots in each row. (Problem 6c)

I know the answer is 91, by chunking the problem into 6 parts based on where the top-left vertex is:

$$ 91 =\\ 6+5+4+3+2+1\\ +5+5+4+3+2+1\\ +4+4+4+3+2+1\\ +3+3+3+3+2+1\\ +2+2+2+2+2+1\\ +1+1+1+1+1+1\\ =\\ 21+(21-1)+(21-3)+(21-6)+(21-10)+(21-15)\\ =\\ 7{7 \choose 2} - {8 \choose 3} $$

I understand the literal counting behind this, and seem to be able to morph the numbers into something meaningful (triangular numbers, etc.), but I cannot figure out how to comprehend the actual math behind this, or how the binomial coefficients come into play.

Answer 1

For quadrilaterals $^7C_2\cdot ^7C_2 = 21\cdot 21 = 441$ makes sense as every pair of dots on the bottom row can be combined with $21$ different pairs of dots on the top row. Here the binomial coefficient reflects the number of ways of choosing $2$ dots from $7$

For the parallelogram, there is a limitation that the spacing of the dots on the bottom row must match the spacing of the dots on the upper row. For this, by counting using the left upper dot location as a basis for each count, it comes out that the furthest left dot has $21$ configurations of parallelograms which is $^7C_2$, and further counting uses this as a basis and subtracts a reduction amount. So your question is, why does the first number come out to be $^7C_2$, of which we use $7$ of these as the basis of our counts, and why does the subtraction amount come out to be $^8C_3$?

Counting the number of ways to choose $2$ from $7$ happens to be an identical count to the number of ways of matching the $6$ different $2$ point pairs, each containing the upper left corner point, with identically spaced points on the lower row. That is, the descending count matches the $2$nd diagonal column of pascals triangle and hence the number $21$ on the $7$th row.

As for $^8C_3$, the subtractions correspond to the $3$rd diagonal column and hence the number $56$ on the $8$th row.

I suggest that it's only practice and proficiency that enables someone to look at this and see it as a $2$ from $7$, and even less so, a $3$ from $8$ combination count.

Having said that, maybe the method below is a simpler and more comprehensible way of counting the number of parallelograms.

In both rows of dots we have: $6$ single spacings, $5$ double spacings, $4$ triple spacings, $3$ quadruple spacings, $2$ quintuple spacings, and $1$ sextuple spacing

As we can only make parallelograms by matching like with like:

$6^2 + 5^2 + 4^2 + 3^2 + 2^2 + 1^2 = 36+25+16+9+4+1 = 91$

Answer 2

Writing the answer in the form $$7\binom{7}{2} - \binom{8}{3}$$ obscures the author's reasoning.

Since opposite sides of a parallelogram are congruent, choosing the top left vertex and two vertices in the bottom row also determines the top right vertex.

However, we cannot pick two vertices in the bottom row that are farther apart than the top left vertex and the last vertex in the top row.

Top left vertex is the first vertex in the top row: There are $\binom{7}{2}$ ways to choose the vertices in the bottom row. Since the length of the side on the bottom row determines the length of the side on the top row, choosing these vertices also determines the top right vertex. For any choice of a pair of vertices in the bottom row, the top right vertex is on the grid. Hence, there are $$\binom{7}{2}$$ such parallelograms.

Top left vertex is the second vertex in the top row: Of the $\binom{7}{2}$ ways to choose the vertices in the bottom row, the one that uses the leftmost and rightmost vertices in the bottom row is not admissible since the vertices in the top row can be at most five units apart. Hence, there are $$\binom{7}{2} - 1$$ such parallelograms.

Top left vertex is the third vertex in the top row: Since the top right vertex can be at most four places to the right of the top left vertex, we cannot choose two vertices in the bottom row that are more than four units apart. There is one choice of vertices in the bottom row that are six units apart and two choices that are five units apart (since the bottom left endpoint must be in one of the first two positions). Hence, the number of parallelograms in which the top left vertex is the third vertex in the top row is $$\binom{7}{2} - 3$$

Top left vertex is the fourth vertex in the top row: Since the top right vertex can be at most three units to the right of the top left vertex, we cannot choose two vertices in the bottom row that are more than three units apart. There are six such choices: one in which the vertices in the bottom row are six units apart, two in which the vertices in the bottom row are five units apart, and three in which the vertices in the bottom row are four units apart (as the bottom left endpoint must be in one of the first three positions). Hence, there are $$\binom{7}{2} - 6$$ such parallelograms.

Top left vertex is the fifth vertex in the top row: Since the top right vertex can be at most two units to the right of the top left vertex, we cannot choose two vertices in the bottom row that are more than two units apart. There are ten such choices: one in which the vertices in the bottom row are six units apart, two in which the vertices in the bottom row are five units apart, three in which the vertices in the bottom row are four units apart, and four in which the vertices in the bottom row are three units apart (as the bottom left endpoint must be in one of the first four positions). Hence, there are $$\binom{7}{2} - 10$$ such parallelograms.

Top left vertex is the sixth vertex in the top row: Since the top right vertex must be one unit to the right of the top left vertex, we cannot choose two vertices in the bottom row that are more than one unit apart. There are fifteen such choices: one in which the vertices in the bottom row are six units apart, two in which the vertices in the bottom row are five units apart, three in which the vertices in the bottom row are four units apart, four in which the vertices in the bottom row are three units apart, and five in which the vertices in the bottom row are two units apart (as the bottom left endpoint must be in one of the first five positions). Hence, there are $$\binom{7}{2} - 15$$ such parallelograms.

Since the top left vertex must be in one of the first six positions, the number of parallelograms that can be formed is found by adding the above results.

Alternate Solution: That said, as Phil H points out in his answer, the problem can be done more simply.

If the length of the top side of the parallelogram is $k$, the length of the bottom side of the parallelogram must have the same length.

There is one way to choose a side of length $6$ in the top row and one way to choose a side of length $6$ in the bottom row, so there is $1 \cdot 1 = 1$ such parallelogram.

There are two ways to choose a side of length $5$ in the top row. For each such choice, there are two ways to choose a side of length $5$ in the bottom row, so there are $2 \cdot 2 = 4$ such parallelograms.

More generally, there are $7 - k$ ways to choose a side of length $k$ in the top row and $7 - k$ ways to choose a side of length $k$ in the bottom row, so there are $(7 - k)(7 - k)$ parallelograms in which the sides drawn on the top and bottom rows each have side length $k$. Hence, the number of admissible parallelograms is $$\sum_{k = 1}^{6} (7 - k)^2 = \sum_{j = 1}^{6} j^2$$

Answer 3

If the horizontal edges of the parallelogram have length $7-j$, $\>j\in[6]$, then they can be placed in $j$ ways each on the top and bottom row. It follows that there are $$N=\sum_{j=1}^6 y^2={6\cdot7\cdot13\over6}=91$$ different parallelograms.