A028657 -id:A028657 - cp's OEIS frontend

A363846 Number of connected bipartite graphs on 2n nodes with a marked bipartite set of size n.

1, 1, 2, 13, 150, 3529, 194203, 29350896, 13668966399, 20662731749804, 103588456044907944, 1744955436868541083098, 99859125842603176324368784, 19611138475504485904873456937288, 13340730475029359536419515017040194246, 31706419735128559894860278029259121951682970, 265351742295121848168241791689670791068746978140331

Offset: 0

Max Alekseyev, Jun 24 2023

nonn

Also, number of n X n binary matrices up to permutations of rows and columns, representing the reduced adjacency matrices of connected bipartite graphs (cf. A002724).

Max Alekseyev, Table of n, a(n) for n = 0..50

Diagonal of the rectangular array described in A363845.

Cf. A002724, A028657, A123549.

a(n) = A363845(2n, n).

A327913 Array read by antidiagonals: T(n,m) is the number of distinct unordered row and column sums of n X m binary matrices.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 7, 4, 1, 1, 5, 13, 13, 5, 1, 1, 6, 22, 34, 22, 6, 1, 1, 7, 34, 76, 76, 34, 7, 1, 1, 8, 50, 152, 221, 152, 50, 8, 1, 1, 9, 70, 280, 557, 557, 280, 70, 9, 1, 1, 10, 95, 482, 1264, 1736, 1264, 482, 95, 10, 1, 1, 11, 125, 787, 2630, 4766, 4766, 2630, 787, 125, 11, 1

Offset: 0

Andrew Howroyd, Oct 30 2019

Only matrices in which both row and columns sums are weakly increasing need to be considered. If order is also considered then the number of possibilities is given by A328887(n, m).

			Array begins:
=============================================
n\m | 0 1  2   3    4     5     6      7
----+----------------------------------------
  0 | 1 1  1   1    1     1     1      1 ...
  1 | 1 2  3   4    5     6     7      8 ...
  2 | 1 3  7  13   22    34    50     70 ...
  3 | 1 4 13  34   76   152   280    482 ...
  4 | 1 5 22  76  221   557  1264   2630 ...
  5 | 1 6 34 152  557  1736  4766  11812 ...
  6 | 1 7 50 280 1264  4766 15584  45356 ...
  7 | 1 8 70 482 2630 11812 45356 153228 ...
  ...
T(2,2) = 7. The following 7 matrices each have different row/column sums.
  [0 0]  [0 0]  [0 1]  [0 0]  [0 1]  [0 1]  [1 1]
  [0 0]  [0 1]  [1 0]  [1 1]  [0 1]  [1 1]  [1 1]

Andrew Howroyd, Table of n, a(n) for n = 0..1325
Manfred Krause, A simple proof of the Gale-Ryser theorem, American Mathematical Monthly, 1996.
Wikipedia, Gale-Ryser theorem

Main diagonal is A029894.
Cf. A028657 (nonequivalent binary n X m matrices).
Cf. A318396, A328887.

T(n,m)={local(Cache=Map());
  my(F(b, c, t, w)=my(hk=Vecsmall([b, c, t, w]), z);
     if(!mapisdefined(Cache, hk, &z),
       z = if(w&&c, sum(i=0, b, sum(j=ceil((t+i)/w), min(t+i, c), self()(i, j, t+i-j, w-1))), !t);
     mapput(Cache, hk, z)); z);
   F(n, n, 0, m)
}

# After PARI implementation.
from functools import cache
@cache
def F(b, c, t, w):
    if w == 0:
        return 1 if t == 0 else 0
    return sum(
        sum(
            F(i, j, t + i - j, w - 1)
            for j in range((t + i - 1) // w, min(t + i, c) + 1)
        )
        for i in range(b + 1)
    )
A327913 = lambda n, m: F(n, n, 0, m)
for n in range(10):
    print([A327913(n, m) for m in range(0, 8)]) # Peter Luschny, Apr 09 2021

A363845 Triangle read by rows: T(n,k) = number of connected n-node graphs with k nodes in distinguished bipartite block, k = 0..n.

Original entry on oeis.org

1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 1, 0, 0, 1, 4, 4, 1, 0, 0, 1, 6, 13, 6, 1, 0, 0, 1, 9, 34, 34, 9, 1, 0, 0, 1, 12, 76, 150, 76, 12, 1, 0, 0, 1, 16, 155, 558, 558, 155, 16, 1, 0, 0, 1, 20, 290, 1824, 3529, 1824, 290, 20, 1, 0, 0, 1, 25, 510, 5375, 19687, 19687, 5375, 510, 25, 1, 0, 0, 1, 30, 853, 14549, 98726, 194203, 98726, 14549, 853, 30, 1, 0

Offset: 0

Max Alekseyev, Jun 24 2023

Also, rectangular array read by antidiagonals: A(m,n) = number of distinct m X n binary matrices M up to permutations of rows or columns such that M represents the reduced adjacency matrix of a connected bipartite graph.

			n=0: 1,
n=1: 1, 1,
n=2: 0, 1, 0,
n=3: 0, 1, 1, 0,
n=4: 0, 1, 2, 1, 0,
n=5: 0, 1, 4, 4, 1, 0,
n=6: 0, 1, 6, 13, 6, 1, 0,
n=7: 0, 1, 9, 34, 34, 9, 1, 0,
n=8: 0, 1, 12, 76, 150, 76, 12, 1, 0,
n=9: 0, 1, 16, 155, 558, 558, 155, 16, 1, 0,
...

Max Alekseyev, Rows n = 0..45, flattened

Inverse bivariate Euler transform of A028657.

Cf. A002724, A363846.

cp's OEIS Frontend

A363846 Number of connected bipartite graphs on 2n nodes with a marked bipartite set of size n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A327913 Array read by antidiagonals: T(n,m) is the number of distinct unordered row and column sums of n X m binary matrices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

A363845 Triangle read by rows: T(n,k) = number of connected n-node graphs with k nodes in distinguished bipartite block, k = 0..n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs