Skip to main content

Dedekind numbers and related sequences

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2011-12-06
Authors/Contributors
Abstract
This thesis considers Dedekind numbers, where the nth Dedekind number D(n) is defined as the number of monotone Boolean functions (MBFs) on n variables, and R(n), which counts non-equivalent MBFs. The values of D(n) and R(n) are known for up to n = 8 and n = 6, respectively; in this thesis we propose a strategy to compute R(7) by considering profile vectors of monotone Boolean functions. The profile of an MBF is a vector that encodes the number of minimal terms it has with 1,2,...,n elements. The computation is accomplished by first generating all profile vectors of 7-variable MBFs, and then counting the functions that satisfy each one by building up from scratch and taking disjunctions one by one. As a consequence of this result, we will be able to extend some sequences on the Online Encyclopedia of Integer Sequences, notably R(n) up to n = 7, using only modest computational resources.
Document
Identifier
etd6894
Copyright statement
Copyright is held by the author.
Permissions
The author granted permission for the file to be printed and for the text to be copied and pasted.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Stephen, Tamon
Member of collection
Download file Size
etd6894_TYusun.pdf 933.96 KB

Views & downloads - as of June 2023

Views: 45
Downloads: 2