A089482 - OEIS

%I #32 Sep 20 2024 05:46:30

%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

%t A003024[n_] := A003024[n] = If[n == 0 || n == 1, 1, Sum[-(-1)^k*

%t    Binomial[n, k]*2^(k*(n - k))*A003024[n - k], {k, 1, n}]];

%t a[n_] := n! * A003024[n];

%t Table[a[n], {n, 0, 13}] (* _Jean-François Alcover_, Sep 20 2024 *)

%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