## The Rand and block distances of pairs of set partitions

Frank Ruskey, Department of Computer Science, University of Victoria, Canada.
Jennifer Woodcock, Department of Computer Science, University of Victoria, Canada.

### Abstract:

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 Rank distance $k$. For fixed $k$ we prove that $R(n,k)$ can be expressed as $\sum_j c_{k,j} {n \choose j} B_{n-j}$ where $c_{k,j}$ is a non-negative integer and Bn is a Bell number. For fixed $k$ we prove that there is a constant $K_n$ such that $R(n,{n \choose 2}-k)$ can be expressed as a polynomial of degree $2k$ in $n$ for all $n \ge K_n$. This polynomial is explicitly determined for $0 \le k \le 11$.

The block distance of two set partitions is the number of elements that are not in common blocks. We give formulae and asymptotics 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.

• You should probably ignore this version and go directly to the journal version.
• Files: pdf.
• International Workshop on Combinatorial Algorithms (IWOCA), Victoria, 2011. LNCS, to appear.