A054961 - OEIS

This site is supported by donations to The OEIS Foundation.

A054961

Maximal number of binary vectors of length n such that the unions (or bitwise ORs) of any 2 distinct vectors are all distinct.

1, 2, 3, 4, 5, 6, 8, 10, 13 (list; graph; refs; listen; history; internal format)

	OFFSET	`0,2`
	COMMENTS	`Maximal number of subsets of an n-set such that the unions of any 2 distinct subsets are all distinct.`
	REFERENCES	`Computed by Michael B. Greenwald (mbgreen(AT)central.cis.upenn.edu), Jud McCranie (JudMcCranie(AT)ugaalum.uga.edu), 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.`
	EXAMPLE	`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}`
	CROSSREFS	`A054962 gives number of solutions.` `Sequence in context: A141341 A116910 A139446 * A141283 A186445 A080078` `Adjacent sequences: A054958 A054959 A054960 * A054962 A054963 A054964`
	KEYWORD	`nonn,hard,nice`
	AUTHOR	`N. J. A. Sloane (njas(AT)research.att.com), May 24 2000`
	EXTENSIONS	`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`

Content is available under The OEIS End-User License Agreement .

Last modified February 16 14:07 EST 2012. Contains 205930 sequences.