|
|
A046747
|
|
Number of n X n rational {0,1}-matrices of determinant 0.
|
|
17
|
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 2^(n^2) - n! * binomial(2^n -1, n) + n! * A000410(n).
a(n) + A055165(n) = 2^(n^2) = total number of n X n (0, 1) matrices.
The probability that a random n X n {0,1}-matrix is singular is conjectured to be asymptotic to C(n+1, 2)*(1/2)^(n-1). [Corrected by N. J. A. Sloane, Jan 02 2007]
|
|
EXAMPLE
|
a(2)=10: the matrix of all 0's, 4 matrices with 2 zeros in the same row or column, 4 matrices with 3 zeros and the all-1 matrix.
|
|
MATHEMATICA
|
Sum[KroneckerDelta[Det[Array[Mod[Floor[k/(2^(n*(#1-1)+#2-1))], 2]&, {n, n}]], 0], {k, 0, (2^(n^2))-1}] (* John M. Campbell, Jun 24 2011 *)
|
|
PROG
|
(PARI) A046747(n) = m=matrix(n, n); ct=0; for(x=0, 2^(n*n)-1, a=binary(x+2^(n*n)); for(i=1, n, for(j=1, n, m[i, j]=a[n*i+j+1-n])); if(matdet(m)==0, ct=ct+1, ); ); ct \\ Randall L Rathbun
(PARI) a(n)=sum(i=0, 2^n^2-1, matdet(matrix(n, n, x, y, (i>>(n*x+y-n-1))%2))==0) \\ Charles R Greathouse IV, Feb 21 2015
|
|
CROSSREFS
|
|
|
KEYWORD
|
hard,nonn,nice
|
|
AUTHOR
|
Günter M. Ziegler (ziegler(AT)math.tu-berlin.de)
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|