|
%I #21 Jul 28 2021 06:08:17
%S 0,2,36,600,11100,235560,5746524,160252456,5069446560,180479494440,
%T 7177165063750,316636751823480,15401586272510880,821382267765103590,
%U 47788292465454829260,3019446671476746981600,206339807951889894605488
%N Sum of the Rand distance between all pairs of set partitions of {1, 2, ... n}.
%C From _Joshua Zucker_, Dec 21 2006: (Start)
%C 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).
%C 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. (End)
%H V. Filkov and S. Skiena, <a href="http://www.cs.ucdavis.edu/~filkov/papers/filkov-ijait04.pdf">Integrating microarray data by consensus clustering</a>, (see also doi: 10.1142/S0218213004001867 or 10.1109/TAI.2003.1250220).
%H A. Goder and V. Filkov, <a href="http://dx.doi.org/10.1137/1.9781611972887.11">Consensus clustering algorithms: Comparison and refinement</a>, Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments, 2008, 109-117.
%H W. Rand, <a href="http://www.jstor.org/stable/2284239">Objective criteria for the evaluation of clustering methods</a>, J. Amer. Stat. Assoc., 66 (336): 846-850, 1971.
%F a(n) = 2 * binomial(n,2) * Bell(n-1) * (Bell(n) - Bell(n-1)).
%F a(n) ~ n*LambertW(n)*Bell(n)^2 * (1 - LambertW(n)/n). - _Vaclav Kotesovec_, Jul 28 2021
%e 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.
%t Table[2 Binomial[n, 2]*BellB[n - 1] (BellB[n] - BellB[n - 1]), {n, 17}] (* _Michael De Vlieger_, Apr 16 2015 *)
%Y Equals twice A193317.
%K nonn
%O 1,2
%A _Andrey Goder_, Dec 12 2006, Feb 20 2007
|
