[seqfan] A182080: nice sequence needing more terms
Neil Sloane
njasloane at gmail.com
Wed Apr 11 20:39:24 CEST 2012
I just came across this in an old book. It is related to many other
problems.
Please see the entry A182080 for more details.
Neil
A182080
a(n) = maximal depth of an indecomposable exact cover of an n-set.
1,2,3,5,9?,18?,38?
Let U = {1,2,...,n} and let P = collection of all subsets of U.
A block system on U is a function f: P -> {0,1,2,...}; f(S) is the number
of times a subset S occurs as a block in the system.
The sum of two block systems f,g is defined in the obvious way, and z
denotes the zero block system.
f is an exact cover of depth d(f) if for each u in U,
Sum_{ S in P: u in S} f(S) = d(f).
An exact cover is decomposable if f = g+h where g, h are nonzero exact
covers.
Then a(n) is the maximal depth of an indecomposable exact cover of U.
Example showing an indecomposable f of depth 2 for n=3, illustrating a(3) =
2:
.S. | 1 2 3 | f(S)
------------------
..- | 0 0 0 | 0
..1 | 1 0 0 | 0
..2 | 0 1 0 | 0
..3 | 0 0 1 | 0
.12 | 1 1 0 | 1
.13 | 1 0 1 | 1
.23 | 0 1 1 | 1
123 | 1 1 1 | 0
More information about the SeqFan
mailing list