A197458 Number of n X n binary matrices with at most two 1's in each row and column, other entries 0.

1, 2, 16, 265, 7343, 304186, 17525812, 1336221251, 129980132305, 15686404067098, 2297230134084416, 400977650310256537, 82188611938415464231, 19536244019455339261970, 5328019975275896220786388, 1651867356348327784988233291, 577522171260292028520919811777

Offset: 0

Author

Felix A. Pahl, Oct 15 2011

Keywords

• nonn

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.

Crossrefs

Cf. A001499, A002720. Column of A283500.

Programs

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);
        }
    }
}

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).