A089479 -id:A089479 - cp's OEIS frontend

A087983 Number of different values taken by permanent of n X n (0,1)-matrix.

1, 2, 3, 6, 16, 51, 220, 1179, 7980

Offset: 0

Wouter Meeussen, Oct 29 2003

			For a 4 X 4 matrix the 16 possible permanents and their multiplicieties are:
{{0, 27713}, {1, 13032}, {2, 10800}, {3, 4992}, {4, 4254}, {5, 1440}, {6, 1536}, {7, 576}, {8, 648}, {9, 24}, {10, 288}, {11, 96}, {12, 48}, {14, 72}, {18, 16}, {24, 1}}

Index entries for sequences related to binary matrices

Cf. A089477, A089479, A089472.

a(6)=220 from Gordon F. Royle, Nov 05 2003
a(7) from Giovanni Resta, Mar 29 2006
a(0)=1 prepended by Alois P. Heinz, Apr 28 2020
a(8) from Minfeng Wang, Oct 04 2024

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

Original entry on oeis.org

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

Cf. A089479, A089482, A227414.

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

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

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

Original entry on oeis.org

1, 6, 150, 6, 18, 13032, 1440, 4992, 672, 1440, 288, 576, 0, 24, 0, 96, 3513720, 693840, 2626800, 604200, 1451400, 468000, 962400, 252000, 425400, 190800, 379200, 97200, 205440, 100800, 132000, 28800, 108000, 28800, 44400, 33600, 61200, 9600, 14400, 0

Offset: 1

Hugo Pfoertner, Nov 04 2003

This sequence was first provided by Jaap Spies.

T(n, A000255(n)) = A052655(n). The n-th row of the table contains A089475(n) nonzero entries. Cf. A089479 occurrence counts for permanents of all (0, 1)-matrices, A089481 occurrence counts for permanents of singular (0, 1)-matrices.

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

A089477 Smallest positive integer not the permanent of a real {0,1}-matrix of order n.

Original entry on oeis.org

2, 3, 5, 13, 27, 119, 737, 5153

Offset: 1

Hugo Pfoertner, Nov 05 2003

a(6) from Gordon F. Royle.

			a(2)=3 because {0,1,2} are expressible as permanents of (0, 1)-matrices.

Swee Hong Chan and Igor Pak, Computational complexity of counting coincidences, arXiv:2308.10214 [math.CO], 2023. See p. 4.

Cf. A089479 occurrence counts for permanents of (0, 1)-matrices, A087983 number of different values taken by permanent of (0, 1)-matrix, A013588 smallest number not expressible as determinant of (0, 1)-matrix.

a(7) from Giovanni Resta, Mar 29 2006

a(8) from Minfeng Wang, Oct 04 2024

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

Original entry on oeis.org

0, 1, 1, 1, 10, 3, 338, 84, 3, 42976, 10020, 1200, 60, 21040112, 4851360, 1213920, 144720, 43560, 3600, 39882864736, 9240051240, 3868663680, 768723480, 418703040, 63612360, 46569600, 6438600, 5014800, 529200, 292604283435872

Offset: 0

Hugo Pfoertner, Nov 04 2003

The first 4 rows were provided by Wouter Meeussen.

			a(4) = T(2,1) = 3 because there are 3 different (0,1)-matrices with determinant=1:
  ((1,0),(0,1)), ((1,1),(0,1)), ((1,0),(1,1)).
Triangle T(n,k) begins:
         0,       1;
         1,       1;
        10,       3;
       338,      84,       3;
     42976,   10020,    1200,     60;
  21040112, 4851360, 1213920, 144720, 43560, 3600;
  ...

Minfeng Wang, Table of n, a(n) for n = 0..118

Cf. T(n,0) = A046747(n), T(n,1) = A086264(n), T(n,A003432(n)) = A051752(n).
The n-th row of the table contains A089472(n) nonzero entries.
Cf. A089479.

Fortran
```
c See link in A086264.
```

Edited by Alois P. Heinz, Dec 20 2023

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.

cp's OEIS Frontend

A087983 Number of different values taken by permanent of n X n (0,1)-matrix.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Crossrefs

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

A089477 Smallest positive integer not the permanent of a real {0,1}-matrix of order n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Fortran

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