login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A197458 Number of n X n binary matrices with at most two 1s in each row and column, other entries 0. 11
1, 2, 16, 265, 7343, 304186, 17525812, 1336221251, 129980132305, 15686404067098, 2297230134084416, 400977650310256537, 82188611938415464231, 19536244019455339261970, 5328019975275896220786388, 1651867356348327784988233291, 577522171260292028520919811777 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

LINKS

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

Filling out an n x n square grid with 0s and 1s at math.stackexchange

R. J. Mathar, The number of binary nXm 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 1s 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: A246739 A304317 A283685 * A050974 A012188 A217816

Adjacent sequences:  A197455 A197456 A197457 * A197459 A197460 A197461

KEYWORD

nonn

AUTHOR

Felix A. Pahl, Oct 15 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 15 13:01 EDT 2018. Contains 316236 sequences. (Running on oeis4.)