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,2

Links

Table of n, a(n) for n=0..16.

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

Cf. A001499, A002720. Column of A283500.

Sequence in context: A326272 A372513 A283685 * A050974 A012188 A217816

Adjacent sequences: A197455 A197456 A197457 * A197459 A197460 A197461

Keyword

nonn

Author

Felix A. Pahl, Oct 15 2011

Status

approved