Written: Jan. 22, 2024

[To appear in Journal of Symbolic Computation (special issue in memory of Marko Petkovsek)]

We study maximal seating arrangments, either on a line, or in a rectangular auditorium with a fixed number of columns but an arbitrary number of rows, that obey any prescribed set of `social distancing' restrictions. In addition to enumeration, we study the statistical distribution of the density, and give efficient algoirthms for generating these at random.

Added Jan. 25, 2024: read interesting feedback by Mate Puljiz, Stjepan Sebek, and Josip Zubrinic.

Added Jan. 30, 2024: read more detailed feedback by Mate Puljiz, Stjepan Sebek, and Josip Zubrinic.   

Maple packages

• SD.txt, a Maple package to investigate social distancing configurations in rectangular classrooms with a fixed number of columns but an arbitrary (symbolic) number of rows.

  ---

  The following package only deals with the one-dimensional case, and uses a different approach. It is not discussed in the article, and is here for old time's sake.
• SD1row.txt, a Maple package to investigate 1D social distancing with varios restrictions.

Sample Input and Output for SD.txt

• If you want to see exact information about enumerating MAXIMAL seating arrangements on one row of seats, where it is prohibited to have a block of b consecutive occupied seats, for b from 2 to 8
  the input file yields the output file.

• If you want to see exact information about enumerating MAXIMAL seating arrangements, on one row of seats where social distancing is more strict, and and any person should have at least b empty seats next to his or her neighbors to the left and right, for b from 1 to 8, as well as the conjectured formula for the generating function (left to the reader) for abitrary b,
  the input file yields the output file.

  ---

• If you want to see exact information about enumerating MAXIMAL rectangular housing developments with THREE columns, avoiding T (i.e. that do not block the sunshine), and comparing their statistics with the RSA (Random Sequential Adsorption, NOT Rivest-Shamir-Adleman) approach by simulating 1000 times for 100x3 0-1 matrices
  the input file yields the output file.

  
  If you do the same but simulating 10000 times then
  the input file yields the output file.

  ---

• If you want to see exact information about enumerating MAXIMAL rectangular housing developments with FOUR columns, avoiding T (i.e. that do not block the sunshine), and comparing their statistics with the RSA (Random Sequential Adsorption) approach by simulating 1000 times for 100x4 0-1 matrices
  the input file yields the output file.

  
  If you do the same but simulating 10000 times then
  the input file yields the output file.

  ---

• If you want to see exact information about enumerating MAXIMAL rectangular housing developments with FIVE columns, avoiding T (i.e. that do not block the sunshine), and comparing their statistics with the RSA (Random Sequential Adsorption) approach by simulating 1000 times for 100x5 0-1 matrices
  the input file yields the output file.

  
  If you do the same but simulating 10000 times then
  the input file yields the output file.

  ---

• If you want to see exact information about enumerating MAXIMAL rectangular housing developments with SIX columns, avoiding T (i.e. that do not block the sunshine), and comparing their statistics with the RSA (Random Sequential Adsorption) approach by simulating 1000 times for 100x6 0-1 matrices
  the input file yields the output file.

  
  If you do the same but simulating 10000 times then
  the input file yields the output file.

  ---

  ---

• If you want to see exact information about enumerating 0-1 matrices with THREE columns, avoiding without neighboring ones (both horizontally and vertically, i.e. avoiding dimers) and comparing their statistics with the RSA (Random Sequential Adsorption) approach by simulating 1000 times for 100x3 0-1 matrices
  the input file yields the output file.

• If you want to see exact information about enumerating 0-1 matrices with FOUR columns, avoiding without neighboring ones (both horizontally and vertically, i.e. avoiding dimers) and comparing their statistics with the RSA (Random Sequential Adsorption) approach by simulating 1000 times for 100x4 0-1 matrices
  the input file yields the output file.

• If you want to see exact information about enumerating 0-1 matrices with FIVE columns, avoiding without neighboring ones (both horizontally and vertically, i.e. avoiding dimers) and comparing their statistics with the RSA (Random Sequential Adsorption) approach by simulating 1000 times for 100x5 0-1 matrices
  the input file yields the output file.

  ---

  ---

• If you want to see exact information about enumerating 0-1 matrices with THREE columns, avoiding without neighboring ones (both horizontally and vertically and diagonally, i.e. non-attacking kings) and comparing their statistics with the RSA (Random Sequential Adsorption) approach by simulating 1000 times for 100x3 0-1 matrices
  the input file yields the output file.

• If you want to see exact information about enumerating 0-1 matrices with FOUR columns, avoiding without neighboring ones (both horizontally and vertically and diagonally, i.e. non-attacking kings) and comparing their statistics with the RSA (Random Sequential Adsorption) approach by simulating 1000 times for 100x4 0-1 matrices
  the input file yields the output file.

• If you want to see exact information about enumerating 0-1 matrices with FIVE columns, avoiding without neighboring ones (both horizontally and vertically and diagonally, i.e. non-attacking kings) and comparing their statistics with the RSA (Random Sequential Adsorption) approach by simulating 1000 times for 100x5 0-1 matrices
  the input file yields the output file.

• If you want to see numerical information for a 5 times 1000 board
  the input file yields the output file.

  ---

  ---

• If you want to see exact information about enumerating 0-1 matrices with THREE columns, avoiding a 2x2 square of ones,i.e. the pattern
  11
  11
  and comparing their statistics with the RSA (Random Sequential Adsorption) approach by simulating 1000 times for 100x3 0-1 matrices
  the input file yields the output file.

• If you want to see exact information about enumerating 0-1 matrices with FOUR columns, avoiding a 2x2 square of ones,i.e. the pattern
  11
  11
  and comparing their statistics with the RSA (Random Sequential Adsorption) approach by simulating 1000 times for 100x4 0-1 matrices
  the input file yields the output file.

Sample Input and Output for SD1row.txt

• If you want so see generating functions and RSA simulations for maximal configurations of seatings in one row avoding a contiguous block of b people for b from 2 to 6
  the input file yields the output file.

Doron Zeilberger's Home Page