

A124104


Sum of the Rand distance between all pairs of set partitions of {1, 2, ... n}.


1



0, 2, 36, 600, 11100, 235560, 5746524, 160252456, 5069446560, 180479494440, 7177165063750, 316636751823480, 15401586272510880, 821382267765103590, 47788292465454829260, 3019446671476746981600, 206339807951889894605488
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

From Joshua Zucker, Dec 21 2006: (Start)
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 "coclustered". The Rand distance between two partitions then counts the pairs that are coclustered in exactly one of the two partitions. The Rand index is found by dividing the Rand distance by (n choose 2).
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 lineartime algorithms for computing it. (End)


LINKS

Table of n, a(n) for n=1..17.
V. Filkov and S. Skiena, Integrating microarray data by consensus clustering, (see also doi: 10.1142/S0218213004001867 or 10.1109/TAI.2003.1250220).
A. Goder and V. Filkov, Consensus clustering algorithms: Comparison and refinement, Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments, 2008, 109117.
W. Rand, Objective criteria for the evaluation of clustering methods, J. Amer. Stat. Assoc., 66 (336): 846850, 1971.


FORMULA

a(n) = 2 * binomial(n,2) * Bell(n1) * (Bell(n)  Bell(n1)).
a(n) ~ n*LambertW(n)*Bell(n)^2 * (1  LambertW(n)/n).  Vaclav Kotesovec, Jul 28 2021


EXAMPLE

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.


MATHEMATICA

Table[2 Binomial[n, 2]*BellB[n  1] (BellB[n]  BellB[n  1]), {n, 17}] (* Michael De Vlieger, Apr 16 2015 *)


CROSSREFS

Equals twice A193317.
Sequence in context: A141132 A064030 A228790 * A262973 A207832 A112036
Adjacent sequences: A124101 A124102 A124103 * A124105 A124106 A124107


KEYWORD

nonn


AUTHOR

Andrey Goder, Dec 12 2006, Feb 20 2007


STATUS

approved



