login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A054961 Maximal number of binary vectors of length n such that the unions (or bitwise ORs) of any 2 distinct vectors are all distinct. 3
1, 2, 3, 4, 5, 6, 8, 10, 13 (list; graph; refs; listen; history; text; 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.

The concatenation of these vectors produces a 2-separable matrix.

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

a(9) >= 17. Here is a candidate solution: {011010001 001001010 101000110 100000001 000010110 110010100 010000011 000110000 001001101 010000100 110001000 000101100 100100010 001000000 010100101 111100000 000011001}. - Dmitry Kamenetsky, Jul 17 2017

a(10) >= 22. Here is a candidate solution: {1010110000 1110000000 0010011000 0110100001 1000010101 0011000101 1001000000 0000000010 0001110100 0001001000 0010101010 1100010010 0000010001 0000101101 0100010100 0000011110 0100101000 0001100011 0000100100 0101000001 0101000110 1010000011}. - Dmitry Kamenetsky, Jul 17 2017

a(11) >= 31. Here is a candidate solution: {00101010010 01100101000 00001101100 00001010101 00100110100 00101001001 01000100101 00010101001 10001100001 11010000010 01001001010 00000001111 01111000000 00110010001 10000111000 11100000001 10010000101 00011110000 01000011001 00100100011 01010010100 01000110010 10110100000 10101000100 11001010000 00011000110 10000010011 10000100110 10100001010 00010011010 00000000100}. - Dmitry Kamenetsky, Jul 21 2017

a(12) >= 46. Here is a candidate solution: {011000011000 000000001000 000110100001 111000000010 110100000100 000010110100 010100010010 000011000011 010001001010 000111001000 010000101100 001001100010 100010000110 000001010110 001010101000 010010100010 001001001001 101000100100 000001100101 100011100000 000100011100 001000010011 010100001001 101100001000 100110010000 001110000010 100001001100 010101100000 110001000001 110010001000 011000100001 001100110000 001000001110 000010001101 110000110000 000100100110 000010011010 101001010000 000101010001 001100000101 100000010101 000001111000 101010000001 100101000010 010000000111 010010010001}. - Dmitry Kamenetsky, Jul 21 2017

REFERENCES

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

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

LINKS

Table of n, a(n) for n=0..8.

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.

Wikipedia, Disjunct Matrix

EXAMPLE

Solutions for n=4..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

Cf. A054962 gives number of solutions, A286874.

Sequence in context: A238110 A211385 A116910 * A141283 A276828 A241089

Adjacent sequences:  A054958 A054959 A054960 * A054962 A054963 A054964

KEYWORD

nonn,hard,more,nice

AUTHOR

N. J. A. Sloane, May 24 2000

EXTENSIONS

a(8) from Giovanni Resta, Mar 30 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified January 20 10:23 EST 2018. Contains 297960 sequences.