A227414 -id:A227414 - cp's OEIS frontend

A088672 Number of n X n (0,1)-matrices with zero permanent.

0, 1, 9, 265, 27713, 10363361, 13906734081, 68121583929729

Offset: 0

Michael Somos, Oct 03 2003

C. J. Everett and P. R. Stein, The asymptotic number of (0,1)-matrices with zero permanent, Disc. Math. 6 (1973), 29-34.
Index entries for sequences related to binary matrices

a[ n_] := Count[Table[Permanent[Partition[a, n]], {a, Tuples[{0, 1}, n^2]}], 0]; (* Michael Somos, Aug 05 2018 *)

a(n) is asymptotic to n*(2^(n^2 - n + 1)). [Everett and Stein]

a(n) = A002416(n) - A227414(n). - Geoffrey Critzer, Dec 19 2023

a(5) from Jaap Spies, Nov 02 2003
a(6) from Gordon F. Royle, Nov 03 2003
a(7) added by Geoffrey Critzer, Dec 19 2023 after Noam Zeilberger in A227414.
a(0)=0 prepended by Alois P. Heinz, Dec 19 2023

A089479 Triangle T(n,k) read by rows, where T(n,k) = number of times the permanent of a real n X n (0,1)-matrix takes the value k, for n >= 0, 0 <= k <= n!.

Original entry on oeis.org

0, 1, 1, 1, 9, 6, 1, 265, 150, 69, 18, 9, 0, 1, 27713, 13032, 10800, 4992, 4254, 1440, 1536, 576, 648, 24, 288, 96, 48, 0, 72, 0, 0, 0, 16, 0, 0, 0, 0, 0, 1, 10363361, 3513720, 4339440, 2626800, 3015450, 1451400, 1872800, 962400, 1295700, 425400, 873000

Offset: 0

Hugo Pfoertner, Nov 05 2003

The last element of each row is 1, corresponding to the n X n "all 1" matrix with permanent = n!. The first 4 rows were provided by Wouter Meeussen. The 6th row was computed by Gordon F. Royle: 13906734081, 2722682160, 4513642920, 3177532800, 4466769300, 2396826720, 3710999520, 2065521600, 3253760550, 1468314000, 2641593600, 1350475200, 2210277600, 1034061120,... .

			Triangle begins:
    0,     1;
    1,     1;
    9,     6,     1;
  265,   150,    69,   18,    9,    0,    1;
27713, 13032, 10800, 4992, 4254, 1440, 1536, 576, 648, 24, 288,
                   96, 48, 0, 72, 0, 0, 0, 16, 0, 0, 0, 0, 0, 1;
  ...

Hugo Pfoertner, Table of n, a(n) for n = 0..159 (rows 0..5, flattened)

T(n,0) = A088672(n), T(n,1) = A089482(n). The n-th row of the table contains A087983(n) nonzero entries. For n>2 A089477(n) gives the position of the first zero entry in the n-th row.
Cf. A089480 (occurrence counts for permanents of non-singular (0,1)-matrices), A089481 (occurrence counts for permanents of singular (0,1)-matrices).
Cf. A000290, A038507 (row lengths), A002416 (row sums).
Cf. A036781, A089478.

From Geoffrey Critzer, Dec 20 2023: (Start)
Sum_{k=1..n!} T(n,k) = A227414(n).
For n>2, T(n,n!-(n-1)!) = n^2, the number of matrices with exactly one 0 entry. (End)

Edited by Alois P. Heinz, Dec 20 2023

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

Original entry on oeis.org

1, 1, 6, 150, 13032, 3513720, 2722682160, 5739447495600, 31598877919109760, 440333998013384657280, 15150599165671354541318400, 1261508968034974650352062240000, 250009928097136435131869478983500800, 116299581308873767293693697630883742796800

Offset: 0

Hugo Pfoertner, Nov 05 2003

nonn

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

			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.

Alois P. Heinz, Table of n, a(n) for n = 0..73

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.

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

A003024[n_] := A003024[n] = If[n == 0 || n == 1, 1, Sum[-(-1)^k*
   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 *)

a(n) = n! * A003024(n). - Vladeta Jovovic, Oct 26 2009

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

A342811 Volume of the permutohedron obtained from the coordinates 1, 2, 4, ..., 2^(n-1), multiplied by (n-1)!.

Original entry on oeis.org

1, 13, 1009, 354161, 496376001, 2632501072321, 52080136110870785, 3872046158193220660993, 1099175272489026844687825921, 1210008580962784935280673680079873, 5225407816779297641534116390319222362113

Offset: 2

Andrey Zabolotskiy, Mar 22 2021

nonn

Here the volume is relative to the unit cell of the lattice which is the intersection of Z^n with the hyperplane spanning the polytope.

a(n) is the number of subgraphs of the complete bipartite graph K_{n-1,n} such that for any vertex from the 2nd part there is a matching that covers all other vertices; Postnikov calls the characterization of such subgraphs "the dragon marriage problem".

Alexander Postnikov, Permutohedra, Associahedra, and Beyond, International Mathematics Research Notices, 2009, 1026-1106; arXiv:math/0507163 [math.CO], 2005. See Example 5.5.

Cf. A066319 (analog for regular permutohedron), A087422, A227414, A342812.

a[n_] := Sum[(p.(2^Range[0, n-1]))^(n-1) / Times @@ Differences[p], {p, Permutations@Range@n}];
Table[a[n], {n, 2, 8}]

A342812 Volume of the (n-1)-dimensional associahedron in the Loday realization, multiplied by (n-1)!.

Original entry on oeis.org

1, 1, 7, 142, 5895, 417201, 45046558, 6891812712, 1417730229765, 377158121463025

Offset: 1

Andrey Zabolotskiy, Mar 22 2021

Here the volume is relative to the unit cell of the lattice which is the intersection of Z^n with the hyperplane spanning the polytope.

Alexander Postnikov, Permutohedra, Associahedra, and Beyond, International Mathematics Research Notices, 2009, 1026-1106; arXiv:math/0507163 [math.CO], 2005. See Example 10.3.

Cf. A087422, A227414, A342811.

a[n_] := With[{npr = Subsets[Span @@ Range@n, {2}]}, Sum[With[{ip = Ordering@p}, Total[-p[[Table[Min@ip[[ij]], {ij, npr}]]]]^(n - 1)] / Times @@ Differences[p], {p, Permutations@Range@n}]];
Table[a[n], {n, 8}]

cp's OEIS Frontend

A088672 Number of n X n (0,1)-matrices with zero permanent.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A089479 Triangle T(n,k) read by rows, where T(n,k) = number of times the permanent of a real n X n (0,1)-matrix takes the value k, for n >= 0, 0 <= k <= n!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A342811 Volume of the permutohedron obtained from the coordinates 1, 2, 4, ..., 2^(n-1), multiplied by (n-1)!.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A342812 Volume of the (n-1)-dimensional associahedron in the Loday realization, multiplied by (n-1)!.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica