Saved

Press the star next to a tool's name to save it.

All my tools

Ugly Duckling Theorem Calculator

Use this ugly duckling theorem calculator to count all possible classes of n objects and the classes in which any two objects agree, which is always half.

Restored your last values ·

Enter how many objects you are comparing. The calculator counts all the ways to group them, and shows how many of those groups treat a chosen pair of objects the same way. The answer is the same for every pair, which is what the theorem says.

Everything is worked out in your browser. Nothing you type is sent anywhere.

–

–

Enter the number of objects, then press Calculate.

See full result

An ugly duckling theorem calculator shows the counting behind a surprising result in the theory of classification. If you can group n objects in every possible way, and you count every grouping the same, then any two different objects have exactly the same number of groupings in common. A swan is then as similar to a duckling as two ducklings are to each other. Enter the number of objects, and the calculator counts the groupings, the ones in which a chosen pair agree, and the share, which is always one half. It runs in your browser.

How to use the ugly duckling theorem calculator

  1. Enter the number of objects, from 2 to 200.
  2. Press Calculate.
  3. Read the total number of classes and the number in which a pair agree.

What the theorem says

The Wikipedia article on the ugly duckling theorem says that the theorem assumes finitely many properties that can be combined with logical connectives, and finitely many objects, and that it asserts that any two different objects share the same number of properties.[1] In its version for classes, the page says that any two objects have exactly the same number of classes in common if we can form any possible class, and that the number is 2ⁿ⁻¹, half of the total number of classes there are.[1] The name comes from Hans Christian Andersen's 1843 story about a duckling that looked different from its siblings, and the theorem was derived by Satosi Watanabe in 1969.[1]

The counting argument

The page explains that with n objects there are 2ⁿ ways to form a class, which is the size of the power set of n objects. Each class can be written as a string of n bits, with a 1 for each object that is in the class and a 0 for each object that is not.[1] Take two objects, and look at their two bit positions. Across all the strings, the two positions agree, both 1 or both 0, exactly half of the time.[1] So for any pair of objects, the number of classes in which they agree is 2ⁿ ÷ 2 = 2ⁿ⁻¹. This is the same for every pair, and that is the theorem. The classes that contain both objects number 2ⁿ⁻², and those that contain neither also number 2ⁿ⁻².

Watanabe's example with three objects

The page gives an example by Watanabe with three objects A, B and C, and two properties, F for first and W for white. Because F implies W, there are only 8 distinct predicates. The page says that the white ducklings A and B agree on 4 of them, but so do A and C, and so do B and C.[1] Enter 3 in the calculator and it shows 8 classes in all, 4 in which any pair agree, 2 that contain both objects of the pair and 2 that contain neither. The ugly duckling is therefore just as similar to the others as they are to one another, when all classes are counted.

What the numbers show

For 10 objects, the number of classes is 1,024, and any pair agree in 512 of them. There are 45 pairs of objects, and every one of them has the same 512. For 100 objects, the number of classes is about 1.27 × 10³⁰. The share of the classes in which a pair agree is always exactly 50 percent, whatever n is. That is why the calculator shows the share as a constant. It stays the same because the class count doubles each time an object is added, and a pair's agreeing count doubles with it.

Why the theorem matters

The theorem is often used to show that there is no similarity without a point of view. If we count every possible feature equally, nothing is more similar to anything else. Real judgments of similarity work because we give some features more weight than others, such as color, shape or ancestry. A duckling and a swan are more alike in some respects, and the ducklings are more alike in others. A learning algorithm, a biologist and a child must all choose which features matter, and that choice cannot come from counting alone. In machine learning, this idea is related to the need for bias in any method of classification, so that it does not treat all patterns as equally likely.

The theorem and similarity measures

When you compare objects in practice, you use a limited set of features. With a feature set that you choose, the counts are no longer all equal, and a pair of objects can agree on more of them than another pair. The ugly duckling theorem does not say that every comparison is meaningless. It says that the comparison rests on a choice that the facts themselves do not make. In the example with three objects, if you decide that being first matters, then A and B are less alike than A and C, since the first object is different.

Common mistakes

  • Counting only some classes. The result needs all 2ⁿ possible classes.
  • Leaving out the empty class. It counts as a class in which every pair agree.
  • Confusing agreeing with sharing. Agreeing includes both being in a class and both being out of it.
  • Taking the result as a rule for real data. It describes the case in which all features are weighted alike.

What next

Use this often? Add Ugly Ducklin to your Home screen.

Frequently asked questions

What is an ugly duckling theorem calculator?

A tool for the theorem, which says that, if all possible classes are counted equally, any two different objects share exactly the same number of classes, namely 2ⁿ⁻¹.

Who proved the ugly duckling theorem?

Satosi Watanabe derived it in 1969. The name comes from Hans Christian Andersen's story of 1843.

How many classes are there for n objects?

2ⁿ, the size of the power set. Each class is a subset of the objects, including the empty set and the whole set.

Why do any two objects agree on half of the classes?

In each class, two chosen objects are both in or both out exactly half of the time, because the two bits agree in half of all bit strings.

Does the theorem mean that similarity is meaningless?

No. It means that similarity depends on choosing which features matter, since counting all features equally makes every pair equally similar.

What went wrong?

We only receive the reason you pick, never what you typed into the tool.

Thanks for your feedback.

More Math Tools