So Rand distance builds a Metric Space on set partitions, in a

computationally efficient way? It seems that there should be more in

OEIS on this, for set partitions limited to those with specific

properties.<br><br><div><span class="gmail_quote">On 12/20/06, <b class="gmail_sendername">Joshua Zucker</b> <<a href="mailto:joshua.zucker@gmail.com">joshua.zucker@gmail.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

On 12/20/06, N. J. A. Sloane <<a href="mailto:njas@research.att.com">njas@research.att.com</a>> wrote:<br>> 4.  An interesting recent entry:<br>> %I A124104<br>> %S A124104 0,2,36,600,11100,235560,5746524<br>

> %N A124104 Sum of the Rand distance between all pairs of set partitions of {1, 2, ... n}.<br>>

%D A124104 W. Rand, Objective criteria for the evaluation of clustering

methods. J. Amer. Stat. Assoc., 66 (336): 846-850, 1971.<br>> %e

A124104 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.<br>> %K A124104 hard,nonn,new<br>> %O A124104 1,2<br>> %A A124104 Andrey Goder (andy.goder(AT)gmail.com), Dec 12 2006<br>><br>> - what is the Rand distance?<br><br>At <a href="http://www.cs.ucdavis.edu/~filkov/papers/filkov-ijait04.pdf">

http://www.cs.ucdavis.edu/~filkov/papers/filkov-ijait04.pdf</a> they<br>explain it pretty well.<br><br>Given a partition of {1, ..., n}, look at a pair of elements.  If the<br>two elements are in the same block of the partition, they're called

"co-clustered".  The Rand distance between two partitions then counts the number of pairs that are co-clustered in exactly one of the two partitions. The Rand index is normalized by dividing the Rand distance by (n choose 2).

<br><br>Example: The distance from 12 3 4 to 1 234 is 4 because of the four<br>pairs 12 (in the first partition but not the second), and 23, 24, 34<br>(in the second partition but not the first).  The maximal distance of<br>

6 is attained by 1 2 3 4 and 1234. Apparently it originated in a 1971 paper by Rand in J Amer. Stat. Assoc., 66(336):846-850. It has some nice properties for a distance, like the triangle inequality, and there are linear-time algorithms for computing it.

<br><br>Seems like instead of just this entry with sum, we should have a table<br>with the number of pairs of partitions having each distance, and maybe<br>a few more seqs as well ...<br><br>--Joshua Zucker<br></blockquote>

</div><br>