Paper Info
Title
A set partition number system.
Abstract
We propose a number system that is based on set partitions. This represents the third number system that is based on combinatorial objects, the other two being combinations and permutations. A number system based on set partitions is useful in the hardware enumeration of set partitions, which is significantly faster than software enumeration. Specifically, the restricted growth string (b(0)b(1) ... b(n-1)) of a set partition pi(I) allows a unique index I to be associated with pi(I), where I is a nonnegative integer in the number system that is represented as I = b(0)omega(0)+ ... +b(n-2)omega(n-2)+b(n-1)omega(n-1). Here, omega(i) is specified by the set partition tree, a data structure derived from the generating tree of set partitions. We show another data structure, the set partition mesh, that is equivalent to the set partition tree. It also stores all set partitions but is much more compact. Indeed, it makes possible the design of hardware set partition generators for n-sets as large as n = 32, compared to the set partition tree, which limits the sets to size no greater than n = 10.
Year
Venue
DocType
2016
AUSTRALASIAN JOURNAL OF COMBINATORICS
Journal
Volume
ISSN
Citations 
65
2202-3518
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Jon T. Butler132142.77
Tsutomu Sasao21083141.62