A197458 - OEIS

%I #25 Apr 08 2020 00:16:53

%S 1,2,16,265,7343,304186,17525812,1336221251,129980132305,

%T 15686404067098,2297230134084416,400977650310256537,

%U 82188611938415464231,19536244019455339261970,5328019975275896220786388,1651867356348327784988233291,577522171260292028520919811777

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

%H <a href="http://math.stackexchange.com/q/72600">Filling out an n x n square grid with 0's and 1's</a> at math.stackexchange

%H R. J. Mathar, <a href="/A247158/a247158.pdf">The number of binary n X m matrices with at most k 1's in each row or column</a>, (2014) Table 2.

%F 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.

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

%o (Java)

%o import java.math.BigInteger;

%o public class AtMostTwoOnes {

%o     public static void main (String [] args) {

%o         for (int n = 0;n <= 40;n++) {

%o             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

%o             for (int k = 0;k <= n;k++)

%o                 for (int l = 0;l <= n;l++)

%o                     counts [0] [k] [l] = BigInteger.ZERO;

%o             counts [0] [n] [0] = BigInteger.ONE; // only one 0xn matrix, with all n column sums 0

%o             for (int m = 1;m <= n;m++) {

%o                 BigInteger [] [] old = counts [m - 1];

%o                 for (int k = 0;k <= n;k++)

%o                     for (int l = 0;l <= n;l++) {

%o                         BigInteger sum = BigInteger.ZERO;

%o                         // new row contains no 1s

%o                         sum = sum.add (old [k] [l]);

%o                         // new row contains one 1

%o                         //   added to column sum 0

%o                         if (k < n && l > 0)

%o                             sum = sum.add (old [k + 1] [l - 1].multiply (BigInteger.valueOf (k + 1)));

%o                         //   added to column sum 1

%o                         if (l < n)

%o                             sum = sum.add (old [k] [l + 1].multiply (BigInteger.valueOf (l + 1)));

%o                         // new row contains two 1s

%o                         //   added to two column sums 0

%o                         if (k < n - 1 && l > 1)

%o                             sum = sum.add (old [k + 2] [l - 2].multiply (BigInteger.valueOf (((k + 2) * (k + 1)) / 2)));

%o                         //   added to one column sum 0, one column sum 1

%o                         if (k < n)

%o                             sum = sum.add (old [k + 1] [l].multiply (BigInteger.valueOf ((k + 1) * l)));

%o                         //   added to two column sums 1

%o                         if (l < n - 1)

%o                             sum = sum.add (old [k] [l + 2].multiply (BigInteger.valueOf (((l + 2) * (l + 1)) / 2)));

%o                         counts [m] [k] [l] = sum;

%o                     }

%o             }

%o             BigInteger sum = BigInteger.ZERO;

%o             for (int k = 0;k <= n;k++)

%o                 for (int l = 0;l <= n;l++)

%o                     sum = sum.add (counts [n] [k] [l]);

%o             System.out.println (n + " : " + sum);

%o         }

%o     }

%o }

%Y Cf. A001499, A002720. Column of A283500.

%K nonn

%O 0,2

%A _Felix A. Pahl_, Oct 15 2011