# equivalent expressions don't look equivalent

Consider the proportion

$\displaystyle\frac{a}b=\frac{c}d=\frac{e}f=\frac{g}h$.

It is equivalent to

$\displaystyle\frac{f}e=\frac{b}a=\frac{h}g=\frac{d}c$

in the sense that the fractions of one are those of the other, or all are inverted. Under that relation, how many equivalence classes are there (of proportions including $a,b,c,d,e,f,g,h$)? Well, you can construct them and count as you go, or you can consider all possible proportions and mod out by the equivalence:

Method 1: constructing inequivalent proportions:

The first element (first fraction, numerator) can arbitrarily be chosen as $a$ (i.e., this helps to pick a representative, but not a class). There are then $7$ choices for the numerator. Anything can then be chosen as the next number, but there are $2$ choices of where to put it: in a numerator or a denominator. Then there are $5$ choices of the counterpart to that third number. And so on: the number of non-arbitrary choices made in constructing an equivalence class is $7\times2\times5\times2\times3\times2\times1$.

Method 2: modding out:

There are $8!$ proportions. There are $4!$ ways to order the fractions and $2!$ choices as far which numbers are numerators, so there are $\frac{8!}{4!2!}$ classes.

I'm not seeing a direct connection between these two formulas (expressions). I would have thought, since they represent the same model (and, really, the same way of looking at the model, just worded differently), that the two formulas given my these two methods would be easy to relate to one another. I mean, sure, you can do arithmetic to get from one to the other:

$\frac{8!}{4!2!}=\frac{8!}{4\times3!2!}=\frac{7!}{3!}=7\times2\times5\times2\times3\times2\times1$,

but that requires splitting up the $4!$ into $4\times3!$ (the $4$ goes with the $2!$ to get divided into the $8$, whereas the $3!$ gets divided into the other numbers). That seems so... ugly. Am I wrong for expecting there to be some nice way of seeing the connection between these two formulas? Or is there one I'm not seeing?

-
Similar in nature to math.stackexchange.com/questions/2237, but not a duplicate. – Daisden Addalos Sep 9 '11 at 0:44
They are not exactly equivalent: the first is true if $a=c=e=g=0$ and $bdfg\neq 0$, while the second is not sensible in that situation; and conversely, the second is true if $b=d=f=g=0$ and $aceg\neq 0$, while the first is not sensible in that case. – Arturo Magidin Sep 9 '11 at 0:49
I don't understand what you are trying to count; but your method 1 does not seem to take into account the possibility that you pick the same fractions but in different order. – Arturo Magidin Sep 9 '11 at 0:52
@Arturo: It does: that’s why he arbitrarily chooses $a$ as the first element and says that there are $7$ ways to choose its mate. Then he picks (say) the first available letter in alphabetical order to belong to another pair; he now has $5$ ways choices for its mate and $2$ for orientation of the pair. Again he picks (say) the first free letter in alphabetical order to belong to another pair, chooses one of the $3$ remaining letters for its mate, and chooses one of the $2$ orientations. This leaves one pair, whose orientation must still be specified. – Brian M. Scott Sep 9 '11 at 6:39
@Brian: I'll take your word for it, since I still don't quite understand just what it is that is being counted... )-: – Arturo Magidin Sep 9 '11 at 13:09

The best I can suggest is this way of relating Method 2 to Method 1. In Method 2 you start with the $8!$ permutations of your symbols. Each permutation gives rise to $4$ pairs by pairing adjacent symbols. But you don’t care about the order of the pairs, so you divide by $4!$. Before you account for the remaining symmetry, stop here for a moment and look at how this can be written: $$\frac{8!}{4!} = \frac{8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{4 \cdot 3 \cdot 2 \cdot 1} = \frac84 \cdot 7 \cdot \frac63 \cdot 5 \cdot \frac42 \cdot 3 \cdot \frac21 \cdot 1 = 2 \cdot 7 \cdot 2 \cdot 5 \cdot 2 \cdot 3 \cdot 2 \cdot 1.$$ Now divide out the rest of the symmetry: that factor of $2!$ in the denominator in Method 2 exactly wipes out the leading factor of $2$ in the diplayed expression to leave you with $7 \cdot 2 \cdot 5 \cdot 2 \cdot 3 \cdot 2 \cdot 1$.

Why might you think of doing this? Because the $7 \cdot 5 \cdot 3 \cdot 1$ in your Method 1 product looks like a moth-eaten $7!$ or $8!$, so you might wonder whether there’s a nice explanation for where the rest went. In this problem $8!$ looks like a better place to start, so you might ask what’s missing from $7 \cdot 2 \cdot 5 \cdot 2 \cdot 3 \cdot 2 \cdot 1$ to make $8!$. The answer, of course, is ‘all the even factors’, and $-$ not coincidentally $-$ you have a bunch of spare factors of $2$, as if somehow just half of each even factor had been wiped out. Because your product in Method 1 already takes into account the orientation symmetry, it’s missing one of the needed factors of $2$, but this line of thought could still be enough to put you on the track of the connection.

Added: Because there’s been some question about what you’re counting, I’m going to offer what I hope is a slightly clearer description; please tell me if you think that it’s wrong. The question, as I understand it, is this:

Consider the $8!$ expressions of the form $\displaystyle\frac{a}{b}=\frac{c}{d}=\frac{e}{f}=\frac{g}{h}$ that can be formed from the symbols $a,b,\dots,h$. Assuming only that these symbols represent positive integers, some of these expressions are provably equivalent: in particular, the truth value of the expression is not affected by permutation of the fractions or by simultaneous inversion of all of them. If we consider provably equivalent expressions to be the same, how many different expressions are there?

-

The equality between the two expressions is more natural than it looks.

I will tell a story which is a little different from the story that you tell, as has been pointed out by Brian M. Scott. But to get to your problem, one simply divides the counts in the story below by $2$. That does not change the structure of the argument.

We have $8$ students, and we want to divide them into $4$ working groups of $2$ people each, and name one of the two people the leader of the group. If you prefer not to talk about leaders, call that person the numerator (the person on top). The underling in each working group, is, of course, at the bottom.

Line up the people according to student number. The first student can be paired with $7$ people. For each such pairing, look at the first unpaired student. She can be paired with $5$ people. For each such choice, look at the first unpaired student. She can be paired with $3$ people. So the total number of pairings is $7\cdot 5\cdot 3\cdot 1$ (the $1$ at the end is to make things prettier).

For each division into $4$ groups, the leader of each group can be selected in $2$ ways. So the total number of groups-with-leader is $$(7\cdot 5\cdot 3\cdot 1)(2\cdot 2\cdot 2\cdot 2).$$ (We could have done the selecting the leader as soon as the group is determined. That would give $7\cdot 2\cdot 5\cdot 2 \cdot 3\cdot 2\cdot 1\cdot 2$.)

Alternately, imagine lining up the $8$ people in some order. There are $8!$ ways to do this. For each ordering, pair person $1$ with person $2$, declare person $1$ leader. Pair person $3$ with person $4$, and declare person $3$ leader. And so on. Does $8!$ then count the number of groups-with-leader? No, because each division into groups-with leader can arise from $4!$ different permutations. For example, the permutation $34785612$ gives the same groups-with-leader as $12345678$, or as $34125678$. So $8!$ overcounts the right answer by a factor of $4!$, and the true number is $$\frac{8!}{4!}.$$

Our two expressions for the number of groups-with-leader are correct, so must be equal. Thus there is good combinatorial reason for them to be equal. I claim that there is also good algebraic reason.

We are looking at $$(7\cdot 5 \cdot 3 \cdot 1)(2\cdot 2\cdot 2 \cdot 2).$$ What's missing from the first part? Obviously, the even numbers. So let's put in $8$ and $6$ and $4$ and $2$, in the places where they belong. We can't do that without changing the expression, so let's divide by $8\cdot 6\cdot 4\cdot 2$ to compensate. We get $$\frac{(8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1)(2\cdot 2\cdot 2\cdot 2)}{8\cdot 6\cdot 4\cdot 2}.$$ Now use the four $2$'s on top to cancel with the $2$'s "in" $8$, $6$, $4$, $2$ at the bottom. We get $$\frac{8!}{4!},$$ exactly the second expression obtained by the combinatorial argument. The same ideas work for $2n$ people divided into $n$ groups-with-leader.

-
Your story isn’t exactly equivalent to Daisden’s. You’re counting the number of ways to make $4$ ordered pairs from $8$ things. Daisden then wants to identify two of these $4$-sets if the pairs in one are the reversals of the pairs in the other, so his figure is half yours. In your terms that means that two sets of teams should be equivalent if they’re identical, or if one is obtained from the other by interchanging top and bottom on every team. – Brian M. Scott Sep 9 '11 at 7:52

The formulas are directly related by

$$\frac{8!}{4!2!}=\frac12\frac{8!}{4!}=\frac12\frac{8\cdot6\cdot4\cdot2}{4\cdot3\cdot2\cdot1}\cdot7\cdot5\cdot3\cdot1=\frac{2\cdot7\cdot2\cdot5\cdot2\cdot3\cdot2\cdot1}2=7\cdot2\cdot5\cdot2\cdot3\cdot2\cdot1\;.$$

Now the two symmetry factors $4!$ and $2!$ remain separate and intact.

-