Information-theoretic limits for a weighing puzzle
You don't need to distinguish n! permutations. You only need to decide whether you have one particular permutation or not.
You start with a set of n! possible permutation. Then you make a measurement, and some permutations in that set are compatible with your measurement, and some are not. So you replace the set of permutations with one that is compatible with your measurement.
For sorting, your measurement is a comparison of two elements. What you need to achieve is that no matter what the outcome is, you are finally left with a set containing one permutation only. To achieve this, you will try to find a comparison that splits your set into two halves that are as close together in size as possible, in case the outcome of the comparison leaves you with the bigger set.
For your problem, you just need to decide whether the permutation (1, 2, 3, ..., n) is in the set of permutations compatible with your measurements or not. You will therefore make a measurement where one of the two possible outcomes means that (1, 2, 3, ..., n) is in your set, and as few other permutations as possible. So you want to split the set as unevenly as possible.
That's what you did. Comparing (1, 2, 3) against 6 means that only twelve permutations including the perfectly ordered one will be compatible with the result: (1, 2, 3) can be ordered in six ways, and (4, 5) can be ordered in two ways. If the comparison is not equal, then there are 708 permutations compatible with that, but that is fine since you have your answer.
Obviously each coin except one must be part of some weighing (if you leave out two coins you can't know if they are in the right order). If you had a limit like &quot;at most four coins can be weighed&quot; that would give you a lower bound. Since you are allowed to weigh all coins in one measurement you'd have to come up with something more clever to find a useful lower bound.