A193317 -id:A193317 - cp's OEIS frontend

A192100 Table read by rows of numbers of unordered pairs of partitions of n-element set that have Rand distance k (n>=2, 1 <= k <= n(n-1)/2).

1, 3, 6, 1, 12, 30, 32, 24, 6, 1, 50, 150, 280, 300, 240, 220, 60, 15, 10, 1, 225, 780, 1720, 3360, 3426, 4100, 2400, 2700, 1075, 471, 150, 35, 45, 15, 1, 1092, 4200, 10885, 25200, 42672, 56889, 60165, 57750, 46585, 31374, 24528, 14140, 4725, 1890, 1302, 252, 210, 140, 105, 21, 1

Offset: 1

Frank Ruskey and Yuji Yamauchi (eugene.uti(AT)gmail.com), Jul 28 2011

The Rand distance of two set partitions is the number of unordered pairs {x,y} such that there is a block in one partition containing both x and y, but x and y are in different blocks in the other partition. Let R(n,k) denote the number of unordered pairs of partitions of a n-element set that have Rand distance k.

The (n,k) entry contains R(n,k) where n is a row number and k is a column number. Rows are of length C(n,2) = n(n-1)/2 and n is in the range [2..7]. Columns are counted from 1.

			The table starts:
1
3 6 1
12 30 32 24 6 1
50 150 280 300 240 220 60 15 10 1
225 780 1720 3360 3426 4100 2400 2700 1075 471 150 35 45 15 1
...
One of the 300 pairs of partitions of 5-element set having Rand distance 4:
  {1, 2, 3}{4, 5}
  {1, 2}{3, 4}{5}

Frank Ruskey and Jennifer Woodcock, The Rand and block distances of pairs of set partitions, Combinatorial algorithms, 287-299, Lecture Notes in Comput. Sci., 7056, Springer, Heidelberg, 2011.
Frank Ruskey, Jennifer Woodcock and Yuji Yamauchi, Counting and computing the Rand and block distances of pairs of set partitions, Journal of Discrete Algorithms, Volume 16, October 2012, Pages 236-248. - From N. J. A. Sloane, Oct 03 2012

Frank Ruskey, Rows n = 2..13, flattened
F. Ruskey and J. Woodcock, The Rand and block distances of pairs of set partitions, Combinatorial algorithms, 287-299, Lecture Notes in Comput. Sci., 7056, Springer, Heidelberg, 2011.

Cf. A105479 (first column), A193317.

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

Original entry on oeis.org

0, 2, 36, 600, 11100, 235560, 5746524, 160252456, 5069446560, 180479494440, 7177165063750, 316636751823480, 15401586272510880, 821382267765103590, 47788292465454829260, 3019446671476746981600, 206339807951889894605488

Offset: 1

Andrey Goder, Dec 12 2006, Feb 20 2007

nonn

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 "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).
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)

			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.

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, 109-117.
W. Rand, Objective criteria for the evaluation of clustering methods, J. Amer. Stat. Assoc., 66 (336): 846-850, 1971.

Equals twice A193317.

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

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

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

cp's OEIS Frontend

A192100 Table read by rows of numbers of unordered pairs of partitions of n-element set that have Rand distance k (n>=2, 1 <= k <= n(n-1)/2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs