# sequence needs work

N. J. A. Sloane njas at research.att.com
Tue May 23 21:34:17 CEST 2000

```Here is a classical combinatorial problem,
which will produce a sequence,
which will probably be new.

Fix n, 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.

For n=1 we take {0,1}, so a(1)=2

For n=2 we can take { 00, 01, 10 }, so a(2)=3

For n=3 take {000, 001, 010, 100 }, and a(3)=4.
[the six unions of pairs of these vectors are
001, 010, 100, 011, 101, 110,
which indeed are all different]

For n=4 we could try {0000, 0001, 0010, 0100, 1000}, giving
a(4) >= 5, and i'm pretty sure that's optimal

For n=5 the answer is 6, 7 or 8.

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.

I'm also interested in seeing what the optimal codes look like.

If anyone cares to do some computing on this problem, please let me
know what you find.

Neil J. A. Sloane, njas at research.att.com,
AT&T Shannon Lab, 180 Park Ave, Room C233,
Florham Park, NJ 07932-0971 USA.