sequence needs work
N. J. A. Sloane
njas at research.att.com
Thu May 25 01:13:57 CEST 2000
Yesterday I mentioned this problem:
For n=1,2,3,4,..., find the max number of binary vectors of length n
such that the unions of any 2 distinct vectors are all distinct.
(I think it is known that this grows exponentially with n)
(Erdos, Frankl, Furedi, JCT 1982 vol. A33, 158-162).
(But i'm interested in finding the exact values)
(of the first few cases so as to get a sequence for the database.)
Thanks to
Michael B Greenwald <mbgreen at central.cis.upenn.edu>
Jud McCranie <jud.mccranie at mindspring.com>
David W. Wilson <wilson at cabletron.com>
who worked on this.
The following is a summary of their results.
For n=0..8 the max number of vectors is:
1 2 3 4 5 6 8 10 >=13
The number of different solutions is:
1 1 1 1 1 13 120 1680 >=1
Both sequences are new.
Examples of optimal sets:
f(0) = 1
null vector
f(1) = 2
0 1
f(2) = 3
00 01 10
f(3) = 4
000 001 010 100
f(4) = 5
0000 0001 0010 0100 1000
f(5) = 6
00000 00001 00010 00100 01000 10000
f(6) = 8
000000 000011 001100 010101 011010 100110 101001 110000
f(7) = 10
0000000 0000011 0000101 0001001 0010010 0100100 0111000 1001000
1010100 1100010
f(8) >=13
00000000 00000011 00001100 00010101 00100110 00111000 01001001
01010010 01100000 10001010 10010000 10100001 11000100
Neil Sloane
More information about the SeqFan
mailing list