The Computational Challenges of Counting 0-1 balanced matrices

The (Symbolic and Numeric) Computational Challenges of Counting 0-1 balanced matrices
By Robert Dougherty-Bliss, Christoph Koutschan, Natalya Ter-Saakov, and Doron Zeilberger
.pdf LaTex source .bib

appeared in Enumerative Combinatorics and Applications 5:2 (2005) #S2R14

Posted: Oct. 10, 2024
Last update of this web-page and paper: Feb. 3, 2025

Dedicated to our hero, Neil James Alexander Sloane (b. Oct 10, 1939) on his 85th birthday.

Maple packages

Hardin.txt, A Maple package to enumerate balanced 0-1 matrices with or without restrictions

NotAlone.txt, A Maple package to create and solve Not Alone puzzles that created the web-book Some Not Alone Puzzles
Along with the Maple package you need to download the data file M88.txt,
(in order to use procedure Ptor for 8 by 8 matrices)

Mathematica package

HolonomicFunctions (from Christoph Koutschan's web site)

C program

balmat4p.c

Sample Input and Output for Hardin.txt

If you want to see the first 55 term, starting at n=1, of the sequence enumerating 6 by 2*n balanced 0-1 matrices, OEIS sequence A172556 due to Ron H. Hardin (6 more than given there, computed from scratch)
the input file produces the output file
Using these terms, if you want to see the empirically derived (non-rigorous but very certain) fourth order linear recurrence satisfied by this sequence using the Maple package FindRec.txt, as well as the 1000-th term
the input file produces the the output file .

As above, but with the 10000-th term
the input file produces the the output file .

If you want to see the first few terms, starting at n=1, of the sequence enumerating 4 by 2*n balanced 0-1 matrices, followed by the empirically guessed recurrence, using the Maple package FindRec.txt, followed by a fully rigorous derivation of the operator, using the multivariate Almkvist-Zeilberger algoirthm implemented in the Maple package SMAZ.txt, then
the input file produces the the output file .
[Note that they are the same!]

If you want to see the first terms, starting at n=1, of the sequence enumerating 2B by 2*n balanced 0-1 matrices, for B=2,3,4,5, in other words OEIS sequences A2896, A172556, A172555 , A172557, respectively,
the input file produces the the output file .

If you want to see the rational generating function in t whose coefficient of t^n is the weight-enumerator of n by 4 0-1 matrices according to the weight where a 1 in the i-th column (i=1,2,3,4) has weight x[i]
the input file produces the the output file .

If you want to see how this generating function produces the first 140 terms of the sequence of 4 by 2n balanced 0-1 matrices avoiding the patterns 010 and 101 both vertically and horizontally (not yet in the OEIS, Sept. 2024)
the input file produces the the output file .

If you want to see the rational generating function in t whose coefficient of t^n is the weight-enumerator of n by 6 0-1 matrices according to the weight where a 1 in the i-th column (i=1,2,3,4,5,6) has weight x[i]
the input file produces the the output file .

If you want to see how this generating function produces the first 30 terms of the sequence of 6 by 2n balanced 0-1 matrices avoiding the patterns 010 and 101 both vertically and horizontally (not yet in the OEIS, Sept. 2024)
the input file produces the the output file .

If you want to see the rational generating function in t whose coefficient of t^n is the number of 2xn 0-1 matrices avoding patterns 010 and 101 both vertically and horizontal, as well as the implied first 50 terms, that happens to be OEIS sequence A206981
the input file produces the the output file .

If you want to see the rational generating function in t whose coefficient of t^n is the number of 3xn 0-1 matrices avoding patterns 010 and 101 both vertically and horizontal, as well as the implied first 50 terms, that happens to be OEIS sequence A060521
the input file produces the the output file .

If you want to see the rational generating function in t whose coefficient of t^n is the number of 4xn 0-1 matrices avoding patterns 010 and 101 both vertically and horizontal, as well as the implied first 50 terms, that happens to be OEIS sequence A060522
the input file produces the the output file .

[Added Nov. 10, 2024]: If you want to see the first 1000 terms of Number of 2*n X 8 binary arrays with row sums 4 and column sums n. OEIS sequence A172555, using the guessed recurrence, that is fully rogorizable, a posteriori,
the input file produces the the output file .

[Added Feb. 2, 2025]: If you want to see the guessedrecurrence that produced the above numbers, i.e. the number of 2*n X 8 binary arrays with row sums 4 and column sums n. OEIS sequence A172555, See here .

Input and Output for HolonomicFunctions with a RIGOROUS proof of the Recurrence Satisfified by OEIS sequence A172556

If you want to see a fully rigorous proof of the recurrence satisfied by the the sequence enumerating 6 by 2*n balanced 0-1 matrices, OEIS sequence A172556 due to Ron H. Hardin
the input file produces the the output file .

[Added Nov. 8, 2024]: If you want to see the guessed (but absolutely certain, and RIGORIZABLE) linear recurrence equation of order 9, satisfied by OEIS sequence A172555 due to Ron H. Hardin, look here:
output file .

Added Jan. 13, 2025: Here
The three-variable rational generating function R(a,b;t) whose coefficient of t^(2n) gives the weight enumerator of all 4 x 2n matrices which avoid the patterns 010 and 101, and which contain only the four possible columns (0011, 0110, 1001, 1100) whose weights are given by (a, b, 1/b, 1/a). The coefficient gives the number of not-alone balanced matrices of size 4 x 2n is given in this output file .

The rigorously computed recurrence for such matrices can be found in
this output file .

Output of the C program for computing Hardin Sequences for Enumerating balanced 0-1 matrices

If you want to see 150 terms of the sequence enumerating 2*n by 8 0-1 arrays with row sums 4 and column sums n, in other words OEIS sequence A172555 (Hardin only had 33 terms)
see data file .

If you want to see 50 terms of the sequence enumerating 2*n by 10 0-1 arrays with row sums 5 and column sums n, in other words OEIS sequence A172557 (Hardin only had 24 terms)
see data file .

If you want to see 39 terms of the sequence enumerating 2*n by 12 0-1 arrays with row sums 6 and column sums n, in other words OEIS sequence A172558 (Hardin only had 19 terms)
see data file .

If you want to see 30 terms of the sequence enumerating 2*n by 14 0-1 arrays with row sums 7 and column sums n, in other words OEIS sequence A172559 (Hardin only had 17 terms)
see data file .

If you want to see 25 terms of the sequence enumerating 2*n by 16 0-1 arrays with row sums 8 and column sums n, in other words OEIS sequence A172560 (Hardin only had 14 terms)
see data file .

If you want to see the first 22 terms of the sequence enumerating 2*n by 18 0-1 arrays with row sums 9 and column sums n, in other words OEIS sequence A172554 (Hardin only had 12 terms)
see data file .

If you want to see the first 70 terms of the sequence enumerating 2*n by 6 0-1 arrays with row sums 3 and column sums n, and that in addition avoid the patterns 101 and 010 both vertically and horizontally (this sequence was the starting point of our paper, that was inspired by the Not Alone puzzle), and it is not yet (Sept. 2024) in the OEIS
see data file .

If you want to see the first 16 terms of the sequence enumerating 2*n by 8 0-1 arrays with row sums 4 and column sums n, and that in addition avoid the patterns 101 and 010 both vertically and horizontally (this sequence was the starting point of our paper, that was inspired by the Not Alone puzzle), and it is not yet (Sept. 2024) in the OEIS
see data file .

Articles of Doron Zeilberger
Doron Zeilberger's Home Page
Robert Dougherty-Bliss 's Home Page
Christoph Koutschan's Home Page