Counting and computing 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.
Yuji Yamauchi,
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 distancek.
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
$B_n$ 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.
-
This is the journal version of the earlier conference paper, and has gone
from 12 conference pages to 13 journal pages.
We also added Yuji Yamauchi as a co-author since he contributed creatively
to some of the new algorithms that are included in the paper.
-
Available online:
dx.doi.org/10.1016/j.jda.2012.04.003.
-
Files: pdf.
-
The earlier conference paper:
2011, LNCS 7056, 287-299.
-
Please send me a note if
you download one of these files.
It's always nice to know who's reading your papers.
-
OEIS entries related to this paper:
A124104, A192100, and a bunch of others.
-
Selected citations:
Back to list of publications.
