cp's OEIS Frontend

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

%I A361928 #12 Mar 31 2023 14:23:25
%S A361928 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,
%T A361928 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,
%U A361928 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
%N A361928 Triangle read by rows: T(n,d) = number of non-adaptive group tests required to identify exactly d defectives among n items.
%C A361928 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.
%C A361928 T(n,d) is the smallest number of rows that an n-column matrix can have while remaining d-separable.
%C A361928 Observations:
%C A361928 T(n,n-1) = n-1.
%C A361928 T(n,d) <= T(n+1,d).
%C A361928 T(n,d) <= T(n,d+1) whenever d <= n-2.
%C A361928 T(n,d) <= T(n+1,d) <= T(n,d)+1 whenever d < n.
%C A361928 T(n,d) < T(n+1,d+1) whenever d < n.
%C A361928 T(n+2,k+1) = n+1 whenever T(n,k)=n-1.
%C A361928 T(n, ceil(n/2)) = n-1 for all n >= 1.
%C A361928 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."
%H A361928 Elaqqad, <a href="https://math.stackexchange.com/questions/3195281/partition-a-set-into-g-groups-k-different-ways-such-that-no-pair-of-elements-i/3488985#3488985">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</a>, MathOverflow
%H A361928 Arthur O'Dwyer, <a href="https://github.com/Quuxplusone/wolves-and-sheep">Quuxplusone/wolves-and-sheep</a>, a program to find optimal testing designs by brute-force exhaustive search
%e A361928 Triangle begins:
%e A361928   1;
%e A361928   2, 2;
%e A361928   2, 3,  3;
%e A361928   3, 4,  4,  4;
%e A361928   3, 5,  5,  5,  5;
%e A361928   3, 6,  6,  6,  6,  6;
%e A361928   3, 6,  7,  7,  7,  7,  7;
%e A361928   4, 7,  8,  8,  8,  8,  8,  8;
%e A361928   4, 7,  9,  9,  9,  9,  9,  9,  9;
%e A361928   4, 8, 10, 10, 10, 10, 10, 10, 10, 10;
%e A361928   ...
%e A361928 If we have 8 items, 3 of which are defective, we can identify the 3 defectives in 6 tests:
%e A361928        Test 1.  T..TT...
%e A361928        Test 2.  T....TT.
%e A361928        Test 3.  .T.T.T..
%e A361928        Test 4.  .T..T.T.
%e A361928        Test 5.  ..T.TT..
%e A361928        Test 6.  ..TT..T.
%e A361928 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.
%Y A361928 Cf A054961: A054961(i) is the smallest n such that T(n,2)=i.
%Y A361928 Cf A290492: A290492(i) is the smallest n such that T(n,3)=i.
%K A361928 nonn,tabl
%O A361928 2,2
%A A361928 _Arthur O'Dwyer_, Mar 30 2023