login
A197458
Number of n X n binary matrices with at most two 1's in each row and column, other entries 0.
12
1, 2, 16, 265, 7343, 304186, 17525812, 1336221251, 129980132305, 15686404067098, 2297230134084416, 400977650310256537, 82188611938415464231, 19536244019455339261970, 5328019975275896220786388, 1651867356348327784988233291, 577522171260292028520919811777
OFFSET
0,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
KEYWORD
nonn
AUTHOR
Felix A. Pahl, Oct 15 2011
STATUS
approved