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

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,2

Comments

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."

Links

Table of n, a(n) for n=2..108.

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

Example

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.

Crossrefs

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.

Sequence in context: A122651 A343378 A351700 * A300013 A130535 A329194

Adjacent sequences: A361925 A361926 A361927 * A361929 A361930 A361931

Keyword

nonn,tabl

Author

Arthur O'Dwyer, Mar 30 2023

Status

approved