A088672 -id:A088672 - cp's OEIS frontend

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!.

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

A119010 Number of symmetric n X n (+1,-1)-matrices over the reals with zero permanent.

Original entry on oeis.org

0, 4, 0, 192, 8960, 371200, 0, 4081029120, 1414035671040

Offset: 1

Giovanni Resta, May 08 2006

Cf. A086906, A088672, A118988, A118989, A118990, A118993, A118995, A118999, A119001.

a(8)-a(9) from Max Alekseyev, Jun 18 2025

A089006 Number of distinct n X n (0,1) matrices after double sorting: by row, by column, by row .. until reaching a fixed point.

Original entry on oeis.org

1, 2, 7, 45, 650, 24520, 2625117, 836488618, 818230288201, 2513135860300849, 24686082394548211147, 787959836124458000837941, 82905574521614049485027140026

Offset: 0

Wouter Meeussen, Nov 03 2003

Also, number of n X n binary matrices with both rows and columns, considered as binary numbers, in nondecreasing order. (Ordering only rows gives A060690.) - R. H. Hardin, May 08 2008
A result of Adolf Mader and Otto Mutzbauer shows that the two definitions are equivalent. - Victor S. Miller, Feb 03 2009
For n=5, only 0.07% remain distinct. Sorting columns and\or rows does not change the permanent of the matrix and leaves the absolute value of the determinant unchanged.
Diagonal of A180985.

			The 7 (2 X 2)-matrices are {{0,0},{0,0}}, {{0,0},{0,1}}, {{0,0},{1,1}}, {{0,1},{0,1}}, {{0,1},{1,0}}, {{0,1},{1,1}} and {{1,1},{1,1}}.

Adolf Mader and Otto Mutzbauer, "Double Orderings of (0,1) Matrices", Ars Combinatoria v. 61 (2001) pp 81-95.

R. H. Hardin, Binary arrays with both rows and cols sorted, symmetries
M. Werner, An Algorithmic Approach for the Zarankiewicz Problem, Slides, 2012. - From _N. J. A. Sloane_, Jan 01 2013

Cf. A088672, A087981, A180985.

Column 0 of A374525.

baseform[li_List] := FixedPoint[Sort[Transpose[Sort[Transpose[Sort[ #1]]]]]&, li]; Table[Length@Split[Sort[baseform/@(Partition[ #, n]&/@(IntegerDigits[Range[0, -1+2^n^2], 2, n^2]))]], {n, 4}]

a(6)-a(12) found by R. H. Hardin, May 08 2008. These terms were found using bdd's (binary decision diagrams), just setting up the logical relations between bits in a gigantic bdd expression and using that to count the satisfying states.

Edited by N. J. A. Sloane, Feb 05 2009 at the suggestion of Victor S. Miller

A227414 Number of ordered n-tuples of subsets of {1,2,...,n} which satisfy the conditions in Hall's Marriage Problem.

Original entry on oeis.org

1, 1, 7, 247, 37823, 23191071, 54812742655, 494828369491583

Offset: 0

Geoffrey Critzer, Jul 10 2013

In a group of n women and n men, each woman selects a subset of men that she would happily marry.  Hall's marriage problem gives the conditions on the subsets so that every woman can become happily married.
a(n)/2^(n^2) is the probability that if the subsets are selected at random then all the women can be happy.
Equivalently, a(n) is the number of n x n {0,1} matrices such that if in any arbitrarily selected r rows we note the columns that have at least one 1 in the selected rows then the number of such columns must not be less than r.

			a(2) = 7 because we have:
1: ({1}, {2});
2: ({1}, {1,2});
3: ({2}, {1});
4: ({2}, {1,2});
5: ({1,2}, {1});
6: ({1,2}, {2});
7: ({1,2}, {1,2}).

F. Hivert, J. D. Mitchell, F. L. Smith, and W. A. Wilson, Minimal generating sets for matrix monoids, arXiv:2012.10323 [math.RA], 2020, p. 2.
Alexander Postnikov, Permutohedra, associahedra, and beyond, 2005, arXiv:math/0507163 [math.CO], 2005.
Stefan Schwarz, The semigroup of fully indecomposable relations and Hall relations, Czechoslovak Mathematical Journal, 23 (1973), 151-163.
Wikipedia, Hall's marriage theorem

Cf. A002416, A088672, A089482, A089479.

f[list_]:=Apply[And,Flatten[Table[Map[Length[#]>=n&,Map[Apply[Union,#]&, Subsets[list,{n}]]],{n,1,Length[list]}]]]; Table[Total[Boole[Map[f, Tuples[Subsets[n],n]]]],{n,1,4}]

a(n) = A002416(n) - A088672(n).

a(n) = Sum_{k=1..n!} A089479(n,k). - Geoffrey Critzer, Dec 20 2023

a(5) from James Mitchell, Nov 13 2015
a(6) from James Mitchell, Nov 16 2015
a(7) from Noam Zeilberger, Jun 04 2019
a(0)=1 prepended by Alois P. Heinz, Dec 19 2023

A118989 Number of symmetric n X n (0,1)-matrices over the reals with zero permanent.

Original entry on oeis.org

1, 3, 25, 271, 6881, 254911, 20903681, 2725061631, 771426498049

Offset: 1

Giovanni Resta, May 08 2006

Cf. A086906, A088672, A118986, A118991, A119009, A119010.

a(n) = 2^(n*(n+1)/2) - A118991(n) = 2^A000217(n) - A118991(n) = A006125(n+1) - A118991(n). - Max Alekseyev, Apr 22 2010; corrected by Herman Jamke (hermanjamke(AT)fastmail.fm), Sep 26 2010

a(8)-a(9) from Max Alekseyev, Jun 18 2025

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

Original entry on oeis.org

9, 0, 1, 265, 0, 63, 0, 9, 0, 1, 27713, 0, 9360, 0, 3582, 0, 1248, 0, 648, 0, 288, 0, 48, 0, 72, 0, 0, 0, 16, 0, 0, 0, 0, 0, 1, 10363361, 0, 3645600, 0, 2411250, 0, 1404800, 0, 1043700, 0, 682200, 0, 417100, 0, 336600, 0, 177750, 0, 183400, 0, 85950, 0, 60000, 0

Offset: 2

Hugo Pfoertner, Nov 09 2003

Seok-Zun Song et al., Extremes of permanents of (0,1)-matrices, Lin. Algebra and its Applic. 373 (2003), pp. 197-210.

T(n, 0)=A088672(n). The n-th row of the table contains A089476(n) nonzero entries. Cf. A089479 occurrence counts for permanents of all (0, 1)-matrices.

T(n, n!) = 1.

A192892 Number of n X n binary matrices whose determinants equal their permanents.

Original entry on oeis.org

1, 2, 12, 343, 34997, 12515441, 15749457081, 72424550598849, 1282759836215548737

Offset: 0

John M. Campbell, Jul 11 2011

Lower bounded by A088672.

Similar to A145675 and A145676.

			a(2) equals 12 because there are exactly twelve 2 X 2 binary matrices whose determinants equal their permanents; these matrices are:
|0 0|  |1 0|  |0 1|  |1 1|  |0 0|  |1 0|  |0 0|  |1 0|
|0 0|  |0 0|  |0 0|  |0 0|  |1 0|  |1 0|  |0 1|  |0 1|
.
|0 1|  |1 1|  |0 0|  |1 0|
|0 1|  |0 1|  |1 1|  |1 1|

Christopher Culter, C++ code to compute large terms
Math StackExchange, What is the number of n X n binary matrices A such that det(A)=perm(A)?

Cf. A046747, A087983, A089472, A089477, A145675, A145676.

Sum[KroneckerDelta[Det[Array[Mod[Floor[k/(2^(n*(#1 - 1) + #2 - 1))], 2] &, {n, n}]], Permanent[Array[Mod[Floor[k/(2^(n*(#1 - 1) + #2 - 1))], 2] &, {n, n}]]], {k, 0, (2^(n^2)) - 1}]

from itertools import product
from sympy import Matrix
def A192892(n): return 1 if n == 0 else sum(1 for m in product([0,1],repeat=n**2) if (lambda x:x.det()==x.per())(Matrix(n,n,m))) # Chai Wah Wu, Oct 01 2021

a(n) <= 2^(n^2), with equality for n<=1.

a(0)=1 prepended and a(5)-a(8) from Christopher Culter, Apr 13 2016

Definition and example slightly modified by Harvey P. Dale, Feb 24 2017

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

Original entry on oeis.org

1, 33, 7555, 13482049, 186481694371, 19733690332538577

Offset: 1

Hongyang Cao, Dec 02 2019

Code Golf Stack Exchange, Find the number of n-by-n (-1, 0, 1) matrices with zero permanent as quickly as possible

Cf. A088672, A057981.

a[n_] := Sum[Boole[Permanent[m] == 0], {m, Tuples[{-1, 0, 1}, {n, n}]}];

a(6) from Peter J. Taylor, Dec 16 2019

cp's OEIS Frontend

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

A119010 Number of symmetric n X n (+1,-1)-matrices over the reals with zero permanent.

Views

Author

Keywords

Crossrefs

Extensions

A089006 Number of distinct n X n (0,1) matrices after double sorting: by row, by column, by row .. until reaching a fixed point.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A227414 Number of ordered n-tuples of subsets of {1,2,...,n} which satisfy the conditions in Hall's Marriage Problem.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A118989 Number of symmetric n X n (0,1)-matrices over the reals with zero permanent.

Views

Author

Keywords

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Formula

A192892 Number of n X n binary matrices whose determinants equal their permanents.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula