OFFSET
0,2
LINKS
Filling out an n x n square grid with 0's and 1's at math.stackexchange
R. J. Mathar, The number of binary n X m matrices with at most k 1's in each row or column, (2014) Table 2.
FORMULA
a(n) = Sum_{k=0}^n Sum_{l=0}^{n-k} a(k,l,n,n) where a(k,l,m,n) is the number of binary m X n matrices with at most two 1's per row, k columns with sum 0, l columns with sum 1 and the remaining n - k - l columns with sum 2.
a(k,l,m,n) = a(k,l,m-1,n) +(k+1)*a(k+1,l-1,m-1,n) +(l+1)*a(k,l+1,m-1,n) +(k+1)*2*a(k+2,l-2,m-1,n)/(k+2) +(k+1)*l*a(k+1,l,m-1,n) +(l+1)*2*a(k,l+2,m-1,n)/(l+2).
PROG
(Java)
import java.math.BigInteger;
public class AtMostTwoOnes {
public static void main (String [] args) {
for (int n = 0; n <= 40; n++) {
BigInteger [] [] [] counts = new BigInteger [n + 1] [n + 1] [n + 1]; // counts [m] [k] [l] : number of mxn matrices with k column sums 0, l column sums 1
for (int k = 0; k <= n; k++)
for (int l = 0; l <= n; l++)
counts [0] [k] [l] = BigInteger.ZERO;
counts [0] [n] [0] = BigInteger.ONE; // only one 0xn matrix, with all n column sums 0
for (int m = 1; m <= n; m++) {
BigInteger [] [] old = counts [m - 1];
for (int k = 0; k <= n; k++)
for (int l = 0; l <= n; l++) {
BigInteger sum = BigInteger.ZERO;
// new row contains no 1s
sum = sum.add (old [k] [l]);
// new row contains one 1
// added to column sum 0
if (k < n && l > 0)
sum = sum.add (old [k + 1] [l - 1].multiply (BigInteger.valueOf (k + 1)));
// added to column sum 1
if (l < n)
sum = sum.add (old [k] [l + 1].multiply (BigInteger.valueOf (l + 1)));
// new row contains two 1s
// added to two column sums 0
if (k < n - 1 && l > 1)
sum = sum.add (old [k + 2] [l - 2].multiply (BigInteger.valueOf (((k + 2) * (k + 1)) / 2)));
// added to one column sum 0, one column sum 1
if (k < n)
sum = sum.add (old [k + 1] [l].multiply (BigInteger.valueOf ((k + 1) * l)));
// added to two column sums 1
if (l < n - 1)
sum = sum.add (old [k] [l + 2].multiply (BigInteger.valueOf (((l + 2) * (l + 1)) / 2)));
counts [m] [k] [l] = sum;
}
}
BigInteger sum = BigInteger.ZERO;
for (int k = 0; k <= n; k++)
for (int l = 0; l <= n; l++)
sum = sum.add (counts [n] [k] [l]);
System.out.println (n + " : " + sum);
}
}
}
CROSSREFS
KEYWORD
nonn
AUTHOR
Felix A. Pahl, Oct 15 2011
STATUS
approved