sequence needs work
N. J. A. Sloane
njas at research.att.com
Tue May 23 21:34:17 CEST 2000
- Previous message (by thread): -1,-1,0,0,+1,0,+1,0,0,0,0,-1,......
- Next message (by thread): sequence needs work
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
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.
Home page: http://www.research.att.com/~njas/
Office: (973) 360 8415; fax: (973) 360 8178; virtual office: (732) 828 6098
- Previous message (by thread): -1,-1,0,0,+1,0,+1,0,0,0,0,-1,......
- Next message (by thread): sequence needs work
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
More information about the SeqFan
mailing list