login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A089482 Number of real {0,1}-matrices having permanent=1. 7
1, 6, 150, 13032, 3513720, 2722682160, 5739447495600, 31598877919109760, 440333998013384657280, 15150599165671354541318400, 1261508968034974650352062240000, 250009928097136435131869478983500800 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

a(6) from Gordon F. Royle.

The following is Max Alekseyev's proof of the formula: Suppose that we have a (0,1)-matrix M with permanent equal to 1. Then in M there is a unique set of n elements, each equal to 1, whose product makes the permanent equal 1. Permute the columns of M so that these n elements become arranged along the main diagonal, denote the resulting matrix by M'. It is clear that each M' correspond to n! different matrices M (here the factor n! comes).

Let M'' be the same as M' except for zeros on the main diagonal. Then the permanent of M'' is zero. Viewing M'' as an adjacency matrix of a directed graph G, we notice that G cannot have a cycle. Indeed, if there is a cycle x_1 -> x_2 -> ... -> x_k -> x_1, then the set of elements (x_1,x_2), (x_2,x_3), ..., (x_k,x_1) together (y_1,y_1), ..., (y_{n-k},y_{n-k}), where { y_1,...,y_{n-k} } is the complement of { x_1, ..., x_k } in the set { 1, 2, ..., n }, form a set of elements of the matrix M' whose product is 1, making the permanent of M' greater than 1.

This works in the reverse direction as well, resulting in the statement: The permanent of M' is 1 if and only if M'' represents the adjacency matrix of some DAG. Therefore there exist A003024(n) distinct matrices M'. [From Vladeta Jovovic, Oct 27 2009]

LINKS

Table of n, a(n) for n=1..12.

FORMULA

a(n) = n!*A003024(n). [From Vladeta Jovovic, Oct 26 2009]

EXAMPLE

a(2)=6 because there are 6 matrices ((1,0),(0,1)), ((0,1),(1,0)), ((0,1),(1,1)), ((1,0),(1,1,)), ((1,1),(0,1)), ((1,1,),(1,0)) with permanent=1.

CROSSREFS

Cf. A088672 number of (0, 1)-matrices with zero permanent, A089479 occurrence counts for permanents of all (0, 1)-matrices, A089480 occurrence counts for permanents of non-singular (0, 1)-matrices.

Sequence in context: A233734 A227044 A188420 * A126679 A232689 A165436

Adjacent sequences:  A089479 A089480 A089481 * A089483 A089484 A089485

KEYWORD

nonn

AUTHOR

Hugo Pfoertner, Nov 05 2003

EXTENSIONS

More terms from Vladeta Jovovic, Oct 26 2009

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 7 13:08 EST 2021. Contains 349581 sequences. (Running on oeis4.)