Revision History for A089482
(Underlined text is an addition;
strikethrough text is a deletion.)
Showing entries 1-10
| older changes
|
|
|
|
#29 by Alois P. Heinz at Wed Dec 20 19:15:38 EST 2023
|
|
|
|
#28 by Alois P. Heinz at Wed Dec 20 16:36:48 EST 2023
|
|
|
|
#27 by Alois P. Heinz at Wed Dec 20 16:36:42 EST 2023
|
| 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.
|
| STATUS
|
proposed
editing
|
|
|
|
#26 by Jon E. Schoenfield at Tue Dec 19 21:28:11 EST 2023
|
|
|
|
#25 by Jon E. Schoenfield at Tue Dec 19 21:26:07 EST 2023
|
|
|
Discussion
|
Tue Dec 19
| 21:28
| Jon E. Schoenfield: @Editors: the wording seemed a little rough to me in some places. Do these changes look okay?
|
|
|
|
#24 by Jon E. Schoenfield at Tue Dec 19 21:25:09 EST 2023
|
| 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' correspondcorresponds to n! different matrices M (herethis 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.
|
| 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.
Cf. A000142, A003024, A227414 number of (0, ,1)-matrices with permanent greater than zero.
|
| STATUS
|
proposed
editing
|
|
|
|
#23 by Geoffrey Critzer at Tue Dec 19 18:13:22 EST 2023
|
|
|
Discussion
|
Tue Dec 19
| 18:25
| Alois P. Heinz: Why does A227414 not contain this sequence (or any sequence) in its CROSSREFS section?
|
|
|
|
#22 by Geoffrey Critzer at Tue Dec 19 18:09:52 EST 2023
|
|
|
Discussion
|
Tue Dec 19
| 18:13
| Geoffrey Critzer: "a(6) from Gordon F.Royle" in COMMENTS should be moved to the EXTENSIONS ?
|
|
|
|
#21 by Geoffrey Critzer at Tue Dec 19 18:01:38 EST 2023
|
|
|
|
#20 by OEIS Server at Tue Jun 27 11:18:11 EDT 2023
|
| LINKS
|
Alois P. Heinz, <a href="/A089482/b089482_1.txt">Table of n, a(n) for n = 0..73</a>
|
|
|
|
|