cp's OEIS Frontend

A089482 Number of real {0,1}-matrices having permanent = 1.

%I A089482 #32 Sep 20 2024 05:46:30
%S A089482 1,1,6,150,13032,3513720,2722682160,5739447495600,31598877919109760,
%T A089482 440333998013384657280,15150599165671354541318400,
%U A089482 1261508968034974650352062240000,250009928097136435131869478983500800,116299581308873767293693697630883742796800
%N A089482 Number of real {0,1}-matrices having permanent = 1.
%C A089482 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 A089482 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 A089482 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 A089482 Alois P. Heinz, <a href="/A089482/b089482.txt">Table of n, a(n) for n = 0..73</a>
%F A089482 a(n) = n! * A003024(n). - _Vladeta Jovovic_, Oct 26 2009
%e A089482 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 A089482 b:= proc(n) option remember; `if`(n=0, 1, add((-1)^(k+1)*
%p A089482       binomial(n, k)*2^(k*(n-k))*b(n-k), k=1..n))
%p A089482     end:
%p A089482 a:= n-> n!*b(n):
%p A089482 seq(a(n), n=0..14);  # _Alois P. Heinz_, Jun 27 2023
%t A089482 A003024[n_] := A003024[n] = If[n == 0 || n == 1, 1, Sum[-(-1)^k*
%t A089482    Binomial[n, k]*2^(k*(n - k))*A003024[n - k], {k, 1, n}]];
%t A089482 a[n_] := n! * A003024[n];
%t A089482 Table[a[n], {n, 0, 13}] (* _Jean-François Alcover_, Sep 20 2024 *)
%Y A089482 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 A089482 Cf. A000142, A003024, A227414 number of (0,1)-matrices with permanent greater than zero.
%K A089482 nonn
%O A089482 0,3
%A A089482 _Hugo Pfoertner_, Nov 05 2003
%E A089482 a(6) from _Gordon F. Royle_
%E A089482 More terms from _Vladeta Jovovic_, Oct 26 2009
%E A089482 a(0)=1 prepended by _Alois P. Heinz_, Jun 27 2023