OFFSET
0,3
COMMENTS
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).
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.
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
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..73
FORMULA
a(n) = n! * A003024(n). - 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.
MAPLE
b:= proc(n) option remember; `if`(n=0, 1, add((-1)^(k+1)*
binomial(n, k)*2^(k*(n-k))*b(n-k), k=1..n))
end:
a:= n-> n!*b(n):
seq(a(n), n=0..14); # Alois P. Heinz, Jun 27 2023
MATHEMATICA
Binomial[n, k]*2^(k*(n - k))*A003024[n - k], {k, 1, n}]];
a[n_] := n! * A003024[n];
Table[a[n], {n, 0, 13}] (* Jean-François Alcover, Sep 20 2024 *)
CROSSREFS
KEYWORD
nonn,changed
AUTHOR
Hugo Pfoertner, Nov 05 2003
EXTENSIONS
a(6) from Gordon F. Royle
More terms from Vladeta Jovovic, Oct 26 2009
a(0)=1 prepended by Alois P. Heinz, Jun 27 2023
STATUS
approved