0,3

A simple regular expression in a labeled universe.

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 (eclark(AT)math.usf.edu), Nov 15 2003

Brualdi, Richard A.; Goldwasser, John L.; and Michael, T. S., 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

E.g.f.: x*(-2*x^2+x^3+x+1)/(-1+x)^2

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.

spec := [S, {S=Prod(Z, Union(Z, Prod(Sequence(Z), Sequence(Z))))}, labeled]: seq(combstruct[count](spec, size=n), n=0..20);

Cf. A000255. A089480 gives occurrence counts for permanents of non-singular (0, 1)-matrices, A051752 number of (0, 1)-matrices with maximal determinant A003432.

Essentially the same as A001563.

Sequence in context: A104970 A151470 A009573 this_sequence A108735 A143556 A007126

Adjacent sequences: A052652 A052653 A052654 this_sequence A052656 A052657 A052658

easy,nonn

encyclopedia(AT)pommard.inria.fr, Jan 25 2000