A054961 -id:A054961 - cp's OEIS frontend

A054962 Number of different solutions to problem in A054961.

Original entry on oeis.org

1, 1, 1, 1, 1, 13, 120, 1680, 4200, 181440

Offset: 0

N. J. A. Sloane, May 24 2000

Initial terms computed by Michael B. Greenwald (mbgreen(AT)central.cis.upenn.edu), May 24 2000.

Cf. A304041.

a(8) from Giovanni Resta, Mar 30 2006

a(9) from Zhao Hui Du, Mar 29 2018

A304041 Number of inequivalent solutions to problem in A054961.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 3, 2, 1

Offset: 0

Zhao Hui Du, May 06 2018

If one solution can be transformed into another by reordering the bits, they are considered to be equivalent.

			List of all inequivalent solutions(in hexadecimal format)
0: {0}
1: {1 0}
2: {2 1 0}
3: {4 2 1 0}
4: {8 4 2 1 0}
5: {10 8 4 2 1 0}
    {12 11 c 6 9 0}
6: {30 a 5 2c 23 19 16 0}
    {2 1 24 18 32 29 e 15}
7: {9 5 3 18 44 22 68 34 52 0}
    {21 22 18 14 a 5 70 49 46 0}
    {40 21 22 18 14 a 5 70 49 46}
8: {c0 30 9 6 a8 92 85 64 51 4a 23 1c 0}
    {2 1 c0 24 18 8c 70 a2 91 4a 45 16 29}
9: {100 21 18 6 1c0 85 43 68 b0 54 8a 115 10b 164 1a2 2d 33}

Cf. A054961, A054962.

A286874 Maximal number of binary vectors of length n such that the union (or bitwise OR) of any 2 distinct vectors does not contain any other vector.

Original entry on oeis.org

1, 2, 2, 3, 4, 5, 6, 7, 8, 12, 13, 17, 20, 26

Offset: 0

Dmitry Kamenetsky, Aug 02 2017

The concatenation of these vectors produces a 2-disjunct matrix.
a(10) >= 13. Here is a candidate solution: {0101000001 0001000110 1000100001 0010000011 1001010000 0010110000 1000001010 0011001000 0100100010 1110000000 0100010100 0000011001 0000101100}. - Dmitry Kamenetsky, Sep 07 2017
a(11) >= 17. Here is a candidate solution: {01000010100 10000100100 00000001110 00010010001 10000011000 01000001001 00001010010 00010101000 00100110000 00100000101 00000100011 00101001000 10110000000 11000000010 00011000100 10001000001 01001100000}. - Dmitry Kamenetsky, Sep 07 2017
The best lower bounds known for the next terms a(14)-a(16) are 28, 40 (corrected by Steinar H. Gunderson, Jul 22 2025) and 45 (see attached files for the solutions).
The bounds for a(10) and a(11) are tight, by the Z3 SMT solver. - Steinar H. Gunderson, Jun 23 2025
a(12)-a(13) were determined by exhaustive parallel search. - Steinar H. Gunderson, Jul 17 2025

			Here is a solution for n=9: {110001000 001001010 001100100 100100010 100010100 000010011 101000001 011010000 000111000 010100001 010000110 000001101}.

Johan V. Dinesen, Lower bound and solution for a(15)
P. Erdös, P. Frankl and Z. Füredi, Families of finite sets in which no set is covered by the union of two others, J. Combin. Theory, A33 (1982), 158-166.
Dmitry Kamenetsky, Lower bounds and their solutions for a(12-16)
W. Kautz and R. Singleton, Nonrandom binary superimposed codes, IEEE Transactions on Information Theory, Volume: 10, Issue: 4, October 1964.
Wikipedia, Disjunct Matrix
Wikipedia, Superimposed code

Cf. A054961, A303977 gives the number of distinct solutions.

a(10)-a(11) from Zhao Hui Du, May 04 2018

a(12)-a(13) from Steinar H. Gunderson, Jul 17 2025

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

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14

Offset: 0

Dmitry Kamenetsky, Aug 04 2017

Maximal number of subsets of an n-set such that the unions of any 3 distinct subsets are all distinct.
The concatenation of these vectors produces a 3-separable matrix.
a(13) >= 15. Here is a candidate solution: {1100100010000 0100010000011 0001101000001 0000000011001 1010000100001 0010100001010 0101000101000 0001000000000 0110001000100 0000110000100 0000001100010 1001000000110 0000000110100 0011010010000 1000011001000}. - Dmitry Kamenetsky, Sep 07 2017

			Here is a solution for n=12: {100000001100 000001010001 100101100000 010000110100 000110000101 011100000000 001000101001 000000000000 101010010000 001001000110 000100011010 000010100010 110000000011 010011001000}.

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

Wikipedia, Disjunct Matrix

Cf. A054961, A361928.

A361928 Triangle read by rows: T(n,d) = number of non-adaptive group tests required to identify exactly d defectives among n items.

Original entry on oeis.org

1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 3, 5, 5, 5, 5, 3, 6, 6, 6, 6, 6, 3, 6, 7, 7, 7, 7, 7, 4, 7, 8, 8, 8, 8, 8, 8, 4, 7, 9, 9, 9, 9, 9, 9, 9, 4, 8, 10, 10, 10, 10, 10, 10, 10, 10, 4, 8, 11, 11, 11, 11, 11, 11, 11, 11, 11, 4, 8, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 4, 9, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 4, 9, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 4, 9

Offset: 2

Arthur O'Dwyer, Mar 30 2023

Arguably, the triangle should be flanked by zeros on both sides -- for all n, T(n,0)=0 and T(n,n)=0 -- but these are not included here.
T(n,d) is the smallest number of rows that an n-column matrix can have while remaining d-separable.
Observations:
T(n,n-1) = n-1.
T(n,d) <= T(n+1,d).
T(n,d) <= T(n,d+1) whenever d <= n-2.
T(n,d) <= T(n+1,d) <= T(n,d)+1 whenever d < n.
T(n,d) < T(n+1,d+1) whenever d < n.
T(n+2,k+1) = n+1 whenever T(n,k)=n-1.
T(n, ceil(n/2)) = n-1 for all n >= 1.
Elaqqad writes (see Links): "The only value of d for which T(n,d) is known completely is d=1, for which T(n,1)=ceil(lg n); the exact value even for d=2 is not known. Generally, the solutions to this problem are called 'testing designs', and the main considered ones are: (1) Set-packing designs or block designs; (2) Transversal designs; (3) Designs whose d-disjunct or d-separable matrices are directly constructed."

			Triangle begins:
  1;
  2, 2;
  2, 3,  3;
  3, 4,  4,  4;
  3, 5,  5,  5,  5;
  3, 6,  6,  6,  6,  6;
  3, 6,  7,  7,  7,  7,  7;
  4, 7,  8,  8,  8,  8,  8,  8;
  4, 7,  9,  9,  9,  9,  9,  9,  9;
  4, 8, 10, 10, 10, 10, 10, 10, 10, 10;
  ...
If we have 8 items, 3 of which are defective, we can identify the 3 defectives in 6 tests:
       Test 1.  T..TT...
       Test 2.  T....TT.
       Test 3.  .T.T.T..
       Test 4.  .T..T.T.
       Test 5.  ..T.TT..
       Test 6.  ..TT..T.
For example: If tests (1,2,3,4,5) are positive, then items (1,2,5) are the defectives. If tests (2,3,4,5,6) are positive, then items (6,7,8) are the defectives. If tests (2,4,5,6) are positive, then items (3,7,8) are the defectives.

Elaqqad, Partition a set into g groups, k different ways, such that no pair of elements is ever in the same group together more than M times, MathOverflow
Arthur O'Dwyer, Quuxplusone/wolves-and-sheep, a program to find optimal testing designs by brute-force exhaustive search

Cf A054961: A054961(i) is the smallest n such that T(n,2)=i.

Cf A290492: A290492(i) is the smallest n such that T(n,3)=i.

cp's OEIS Frontend

A054962 Number of different solutions to problem in A054961.

Views

Author

Keywords

References

Crossrefs

Extensions

A304041 Number of inequivalent solutions to problem in A054961.

Views

Author

Keywords

Comments

Examples

Crossrefs

A286874 Maximal number of binary vectors of length n such that the union (or bitwise OR) of any 2 distinct vectors does not contain any other vector.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A361928 Triangle read by rows: T(n,d) = number of non-adaptive group tests required to identify exactly d defectives among n items.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs