|
%I #29 Dec 20 2023 19:15:38
%S 1,1,6,150,13032,3513720,2722682160,5739447495600,31598877919109760,
%T 440333998013384657280,15150599165671354541318400,
%U 1261508968034974650352062240000,250009928097136435131869478983500800,116299581308873767293693697630883742796800
%N Number of real {0,1}-matrices having permanent = 1.
%C 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, and denote the resulting matrix by M'. It is clear that each M' corresponds to n! different matrices M (this is where the factor n! in the formula comes from).
%C 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 with (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.
%C 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'. - _Vladeta Jovovic_, Oct 27 2009
%H Alois P. Heinz, <a href="/A089482/b089482.txt">Table of n, a(n) for n = 0..73</a>
%F a(n) = n! * A003024(n). - _Vladeta Jovovic_, Oct 26 2009
%e 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.
%p b:= proc(n) option remember; `if`(n=0, 1, add((-1)^(k+1)*
%p binomial(n, k)*2^(k*(n-k))*b(n-k), k=1..n))
%p end:
%p a:= n-> n!*b(n):
%p seq(a(n), n=0..14); # _Alois P. Heinz_, Jun 27 2023
%Y 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.
%Y Cf. A000142, A003024, A227414 number of (0,1)-matrices with permanent greater than zero.
%K nonn
%O 0,3
%A _Hugo Pfoertner_, Nov 05 2003
%E a(6) from _Gordon F. Royle_
%E More terms from _Vladeta Jovovic_, Oct 26 2009
%E a(0)=1 prepended by _Alois P. Heinz_, Jun 27 2023
|
