Counting and computing the Rand and block distances of pairs of set partitions

• Published in: Journal of discrete algorithms (Amsterdam, Netherlands) Netherlands), 2012-10, Vol.16, p.236-248
• Main Authors: Ruskey, Frank, Woodcock, Jennifer, Yamauchi, Yuji
• Format: Article
• Language: English
• Subjects: Bell numbers; Efficient algorithms; Generating functions; Rand distance; Refinement; Set partitions
• ISSN: 1570-8667; 1570-8675
• DOI: 10.1016/j.jda.2012.04.003

The Rand distance of two set partitions is the number of 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 distinct (unordered) pairs of partitions of n that have Rand distance k. For fixed k we prove that R(n,k) can be expressed as ∑jC(j,k)(nj)Bn−j where C(j,k) is a non-negative integer, Bn is the nth Bell number, and the summation range is of size less than 2k. If n⩾2k+2 then R(n,(n2)−k) can be expressed as a polynomial of degree 2k in n. This polynomial is explicitly determined for 0⩽k⩽3. We explain how to compute R(n,k) for k=0,1,…,(n2) in time O(Bn2) using the idea of a refinement of two partitions; we also present an O(n) algorithms for computing the refinement and coarsening when the partitions are represented as restricted growth strings. The block distance of two set partitions is the number of elements that are not in common blocks. We give formulae and asymptotics for B(n,k), the number of pairs of partitions of {1,2,…,n} with block distance k; a formula that is based on N(n), the number of pairs of partitions with no blocks in common. We develop an O(n) algorithm for computing the block distance.