1,2

Comment from Joshua Zucker, Dec 21 2006: Given a partition of {1, ..., n}, look at a pair of elements. If the two elements are in the same block of the partition, they're called "co-clustered". The Rand distance between two partitions then counts the pairs that are co-clustered in exactly one of the two partitions. The Rand index is found by dividing the Rand distance by (n choose 2).

Comment from Joshua Zucker, Dec 21 2006 (cont.): Example: The distance from 12 3 4 to 1 234 is 4 because of the four pairs 12 (in the first partition but not the second), and 23, 24, 34 (in the second partition but not the first). The maximal distance of 6 is attained by 1 2 3 4 and 1234. The Rand distance has some nice properties, satisfies the triangle inequality, and there are linear-time algorithms for computing it.

W. Rand, Objective criteria for the evaluation of clustering methods. J. Amer. Stat. Assoc., 66 (336): 846-850, 1971.

Author?, Title?

a(n) = 2 * binomial(n, 2) * Bell(n - 1) * (Bell(n) - Bell(n - 1))

E.g. a(2) = 2 = 1 + 1 + 0 + 0 because the distance from 1,2 to 12 is 1 (and vice versa) and the distance from 1,2 to 1,2 or 12 to 12 is 0.

Adjacent sequences: A124101 A124102 A124103 this_sequence A124105 A124106 A124107

Sequence in context: A092852 A025608 A064030 this_sequence A112036 A093530 A001626

hard,nonn

Andrey Goder (andy.goder(AT)gmail.com), Dec 12 2006, Feb 20 2007