0,2

Maximal number of subsets of an n-set such that the unions of any 2 distinct subsets are all distinct.

Computed by Michael B. Greenwald (mbgreen(AT)central.cis.upenn.edu), Jud McCranie (j.mccranie(AT)comcast.net), David W. Wilson (davidwwilson(AT)comcast.net), May 24 2000. a(8) >= 13.

Asymptotic results: P. Erdos, P. Frankl and Z. Furedi, Families of finite sets in which no set is covered by the union of two others, J. Combin. Theory, A33 (1982), 158-166.

Background: D.-Z. Du and F. K. Hwang, Combinatorial Group Testing and Its Applications, World Scientific, 2nd ed., 2000; see Chap. 7.

Solutions for n=4..7 and candidate solution for n=8: {0000 0001 0010 0100 1000}; {00000 00001 00010 00100 01000 10000}; {000000 000011 001100 010101 011010 100110 101001 110000}; {0000000 0000011 0000101 0001001 0010010 0100100 0111000 1001000 1010100 1100010}; {00000000 00000011 00001100 00010101 00100110 00111000 01001001 01010010 01100000 10001010 10010000 10100001 11000100}

A054962 gives number of solutions.

Sequence in context: A141341 A116910 A139446 this_sequence A141283 A080078 A036415

Adjacent sequences: A054958 A054959 A054960 this_sequence A054962 A054963 A054964

nonn,hard,nice

njas, May 24 2000

It follows from the Erdos-Frankl-Furedi paper that a(n) grows exponentially with n.

a(8) from Giovanni Resta (g.resta(AT)iit.cnr.it), Mar 30 2006