|
| |
|
|
A052655
|
|
a(2) = 6, otherwise a(n) = n*n!.
|
|
2
| |
|
|
0, 1, 6, 18, 96, 600, 4320, 35280, 322560, 3265920, 36288000, 439084800, 5748019200, 80951270400, 1220496076800, 19615115520000, 334764638208000, 6046686277632000, 115242726703104000, 2311256907767808000
(list; graph; refs; listen; history; internal format)
|
|
|
|
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 (eclark(AT)math.usf.edu), Nov 15 2003
|
|
|
REFERENCES
| 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.
|
|
|
LINKS
| 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);
|
|
|
CROSSREFS
| 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 * A181038 A108735 A143556
Adjacent sequences: A052652 A052653 A052654 * A052656 A052657 A052658
|
|
|
KEYWORD
| easy,nonn
|
|
|
AUTHOR
| encyclopedia(AT)pommard.inria.fr, Jan 25 2000
|
| |
|
|
