OFFSET
0,3
COMMENTS
a(n) = number of real non-singular (0,1)-matrices of order n having maximal permanent = A000255(n). Proof: [W. Edwin Clark and Richard Brualdi] The maximum permanent is per A where A has all 1's except for n-1 0's on the main diagonal. By Corollary 4.4 in the Brualdi et al. reference for n >= 4 any n X n (0,1)-matrix B with per B = per A can be obtained from A by permuting rows and columns. Since there are n ways to place the single 1 on the main diagonal and then n! ways to permute the distinct rows, a(n) = n*n! if n >=4. Direct computation shows this also holds for n = 1 and 3. - W. Edwin Clark, Nov 15 2003
LINKS
Richard A. Brualdi, John L. Goldwasser, T. S. Michael, Maximum permanents of matrices of zeros and ones, J. Combin. Theory Ser. A 47 (1988), 207-245.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 602
FORMULA
E.g.f.: x*(-2*x^2+x^3+x+1)/(-1+x)^2.
EXAMPLE
a(2)=6 because there are 6 (0,1)-matrices with nonzero determinant having permanent=1. See example in A089482. The (0,1)-matrix with maximal permanent=2 ((1,1),(1,1)) has det=0.
MAPLE
spec := [S, {S=Prod(Z, Union(Z, Prod(Sequence(Z), Sequence(Z))))}, labeled]: seq(combstruct[count](spec, size=n), n=0..20);
MATHEMATICA
Join[{0, 1, 6}, Table[n*n!, {n, 3, 20}]] (* Harvey P. Dale, Apr 20 2012 *)
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
encyclopedia(AT)pommard.inria.fr, Jan 25 2000
STATUS
approved