

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

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



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



KEYWORD

nonn


AUTHOR



STATUS

approved



