Arthur O'Dwyer - cp's OEIS frontend

User: Arthur O'Dwyer

Arthur O'Dwyer has authored 4 sequences.

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

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.

A359707 Number of 1-sided ouroboros polyominoes with k=2n cells.

Original entry on oeis.org

0, 1, 0, 1, 1, 4, 11, 45, 178, 762, 3309, 14725, 66323, 302342, 1391008, 6453950

Offset: 1

Arthur O'Dwyer, Jan 11 2023

A "snake" polyomino is a polyomino in which exactly two cells have exactly one (Von Neumann) neighbor apiece, and the rest have two neighbors apiece. Arthur O'Dwyer coined the term "ouroboros polyomino" for a polyomino in which every cell has exactly two neighbors: that is, an ouroboros polyomino is like a "snake" in which the head cell neighbors the tail cell.
A324407 etc. use the term "polyomino ring" in place of "ouroboros polyomino."
A checkerboard coloring shows that every ouroboros must have an even number of cells.

Arthur O'Dwyer, Polyomino strips, snakes, and ouroboroi (gives the first 32 terms)
Arthur O'Dwyer, C++ program

A151514 counts 1-sided snake polyominoes with k=n cells. A359707 added to A151514 gives the number of 1-sided polyominoes in which each cell has at most 2 (Von Neumann) neighbors.
A359706 counts free (2-sided) ouroboros polyominoes with k=2n cells. A359707 minus A359706 gives the count of chiral pairs. This sequence first differs from A359706 at k=14; the four chiral pairs of 14-cell ouroboroi are
    ###   ####   ###   ###
    # #   #  ##  # #   # ##
    # ##  ##  #  # ##  #  #
    #  #   ####  ## #  #  #
    ####          ###  ####
and their mirror-reflections.

A359706 Number of free (2-sided) ouroboros polyominoes with k=2n cells.

Original entry on oeis.org

0, 1, 0, 1, 1, 4, 7, 31, 95, 420, 1682, 7544, 33288, 152022, 696096, 3231001

Offset: 1

Arthur O'Dwyer, Jan 11 2023

A "snake" polyomino is a polyomino in which exactly two cells have exactly one (Von Neumann) neighbor apiece, and the rest have two neighbors apiece. Arthur O'Dwyer coined the term "ouroboros polyomino" for a polyomino in which every cell has exactly two neighbors: that is, an ouroboros polyomino is like a "snake" in which the head cell neighbors the tail cell.
A324407 etc. use the term "polyomino ring" in place of "ouroboros polyomino."
A checkerboard coloring shows that every ouroboros must have an even number of cells.
This sequence counts ouroboroi which do not designate a specific head or tail cell; thus the unique 8-cell ouroboros is
    ###
    # #
    ###
One could imagine counting "headed" ouroboroi, in which the head and tail are distinguished. There are two distinct ways to create a free 8-cell "headed" ouroboros:
    ##H  #HT
    # T  # #
    ###  ###
This sequence first differs from A359707 (the count of 1-sided ouroboroi) at k=14. The four chiral 14-cell ouroboroi, each of which is counted once by A359706 and twice by A359707, are
    ###   ####   ###   ###
    # #   #  ##  # #   # ##
    # ##  ##  #  # ##  #  #
    #  #   ####  ## #  #  #
    ####          ###  ####

Arthur O'Dwyer, Polyomino strips, snakes, and ouroboroi (gives the first 32 terms)
Arthur O'Dwyer, C++ program

A002013 counts free (2-sided) snake polyominoes with k=n cells. A359706 added to A002013 gives the number of free polyominoes in which each cell has at most 2 (Von Neumann) neighbors.

A359707 counts free (2-sided) ouroboros polyominoes with k=2n cells. A359706 subtracted from A359707 gives the count of chiral pairs.

A359068 Number of 1-sided strip polyominoes with n cells.

Original entry on oeis.org

1, 1, 2, 5, 10, 24, 52, 124, 282, 668, 1548, 3654, 8533, 20093, 47033, 110533, 258807, 607227, 1421055, 3329585, 7785995, 18221563, 42575336, 99539106, 232398659, 542864111, 1266567155, 2956342341, 6893180336, 16078817198, 37469245219, 87347384305, 203447081205

Offset: 1

Arthur O'Dwyer, Jan 11 2023

A "strip" polyomino is a snake polyomino (A151514) with no holes.
This sequence first differs from A151514 at n = 7. An example of a polyomino counted by A151514, but not by this sequence, is:
  ###
  # #
  ##

Arthur O'Dwyer, Polyomino strips, snakes, and ouroboroi (gives first 33 terms).
Arthur O'Dwyer, C++ program.

A333313 gives the number of free (2-sided) strip polyominoes with n cells. Subtracting A333313 from A359068 gives the number of chiral pairs.
A151514 gives the number of 1-sided snake polyominoes with n cells; A151514(n) > A359068(n) for n >= 7.
Subtracting A359068 from A151514 gives the number of snake polyominoes with n cells that have at least one hole.

cp's OEIS Frontend

User: Arthur O'Dwyer

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

A359707 Number of 1-sided ouroboros polyominoes with k=2n cells.

Views

Author

Keywords

Comments

Links

Crossrefs

A359706 Number of free (2-sided) ouroboros polyominoes with k=2n cells.

Views

Author

Keywords

Comments

Links

Crossrefs

A359068 Number of 1-sided strip polyominoes with n cells.

Views

Author

Keywords

Comments

Links

Crossrefs