A328887 -id:A328887 - cp's OEIS frontend

A072590 Table T(n,k) giving number of spanning trees in complete bipartite graph K(n,k), read by antidiagonals.

1, 1, 1, 1, 4, 1, 1, 12, 12, 1, 1, 32, 81, 32, 1, 1, 80, 432, 432, 80, 1, 1, 192, 2025, 4096, 2025, 192, 1, 1, 448, 8748, 32000, 32000, 8748, 448, 1, 1, 1024, 35721, 221184, 390625, 221184, 35721, 1024, 1, 1, 2304, 139968, 1404928, 4050000, 4050000

Offset: 1

Michael Somos, Jun 23 2002

			From _Andrew Howroyd_, Oct 29 2019: (Start)
Array begins:
============================================================
n\k | 1   2     3       4        5         6           7
----+-------------------------------------------------------
  1 | 1   1     1       1        1         1           1 ...
  2 | 1   4    12      32       80       192         448 ...
  3 | 1  12    81     432     2025      8748       35721 ...
  4 | 1  32   432    4096    32000    221184     1404928 ...
  5 | 1  80  2025   32000   390625   4050000    37515625 ...
  6 | 1 192  8748  221184  4050000  60466176   784147392 ...
  7 | 1 448 35721 1404928 37515625 784147392 13841287201 ...
  ...
(End)

J. W. Moon, Counting Labeled Trees, Issue 1 of Canadian mathematical monographs, Canadian Mathematical Congress, 1970.
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Exercise 5.66.

T. D. Noe, Antidiagonals d=1..50, flattened
Taylor Brysiewicz and Aida Maraj, Lawrence Lifts, Matroids, and Maximum Likelihood Degrees, arXiv:2310.13064 [math.CO], 2023. See p. 13.
H. I. Scoins, The number of trees with nodes of alternate parity, Proc. Cambridge Philos. Soc. 58 (1962) 12-16.
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Eric Weisstein's World of Mathematics, Spanning Tree

Columns 2..3 are A001787, A069996.
Main diagonal is A068087.
Antidiagonal sums are A132609.
Cf. A070285, A328887, A328888.

t[n_, k_] := n^(k-1) * k^(n-1); Table[ t[n-k+1, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Feb 21 2013 *)

{T(n, k) = if( n<1 || k<1, 0, n^(k-1) * k^(n-1))}

T(n, k) = n^(k-1) * k^(n-1).

E.g.f.: A(x,y) - 1, where: A(x,y) = exp( x*exp( y*A(x,y) ) ) = Sum_{n>=0} Sum_{k=0..n} (n-k)^k * (k+1)^(n-k-1) * x^(n-k)/(n-k)! * y^k/k!. - Paul D. Hanna, Jan 22 2019

Scoins reference from Philippe Deléham, Dec 22 2003

A328888 Array read by antidiagonals: T(n,m) is the number of acyclic edge covers of the complete bipartite graph K_{n,m}.

Original entry on oeis.org

1, 1, 1, 1, 6, 1, 1, 18, 18, 1, 1, 46, 132, 46, 1, 1, 110, 696, 696, 110, 1, 1, 254, 3150, 6728, 3150, 254, 1, 1, 574, 13086, 51760, 51760, 13086, 574, 1, 1, 1278, 51492, 348048, 632970, 348048, 51492, 1278, 1, 1, 2814, 195180, 2143736, 6466980, 6466980, 2143736, 195180, 2814, 1

Offset: 1

Andrew Howroyd, Oct 29 2019

In other words, the number of spanning forests of the complete bipartite graph K_{n,m} without isolated vertices.

			Array begins:
=============================================================
n\m | 1   2     3       4        5          6           7
----+--------------------------------------------------------
  1 | 1   1     1       1        1          1           1 ...
  2 | 1   6    18      46      110        254         574 ...
  3 | 1  18   132     696     3150      13086       51492 ...
  4 | 1  46   696    6728    51760     348048     2143736 ...
  5 | 1 110  3150   51760   632970    6466980    58620030 ...
  6 | 1 254 13086  348048  6466980   96208632  1231832364 ...
  7 | 1 574 51492 2143736 58620030 1231832364 21634786586 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Eric Weisstein's World of Mathematics, Complete Bipartite Graph

Column 2 is A328890.
Main diagonal is A328889.
Cf. A072590, A328887.

T(n, m=n)={my(M=matrix(n, m), N=matrix(n, m, n, m, n^(m-1) * m^(n-1))); for(n=1, n, for(m=1, m, M[n,m] = N[n,m] + sum(i=1, n-1, sum(j=1, m-1, binomial(n-1, i-1)*binomial(m, j)*N[i,j]*M[n-i, m-j])))); M}
{ my(A=T(7)); for(i=1, #A, print(A[i,])) }

T(n,m) = A072590(n, m) + Sum_{i=1..n-1} Sum_{j=1, m-1} binomial(n-1, i-1) * binomial(m, j) * A072590(i, j) * T(n-i, m-j).

A297077 Number of distinct row and column sums for n X n (0, 1)-matrices.

Original entry on oeis.org

1, 2, 15, 328, 16145, 1475856, 219682183, 48658878080, 15047189968833, 6199170628499200, 3283463201858585471, 2174417430787021427712, 1760550428764505109190225, 1711145965399957937819322368, 1966168979042910307305159432375, 2636533865690624357354875499216896

Offset: 0

Peter Kagey, Dec 25 2017

nonn

a(n) is bounded above by 2^(n^2) and bounded below by A048163(n + 1).
Also the number of acyclic edge sets of the complete bipartite graph K_{n,n}. See proof by David E. Speyer at the Mathematics Stack Exchange link below.
It is also the number of n X n binary matrices that can be completed to the all-ones matrix by repeatedly changing an element from a zero to a one if that element is the only zero in its row or column. (Proof idea: Every acyclic edge set can be reduced to the empty set by removing one leaf edge at a time.) This can be interpreted as the number of ways of turning off storage nodes in an n X n array so that data remains restorable in the "full scheme" RAID (Redundant Array of Inexpensive Disks) design described by Nagel, Süß.- Jair Taylor, Jul 29 2019

			For n = 3, both of the following 3 X 3 (0,1)-matrices have identical row and column sums:
[1 0 1]     [1 1 0]
[0 1 0] and [0 1 0]
[0 1 0]     [0 0 1]
have row sums of [2 1 1] and column sums of [1 2 1].
So ([2 1 1], [1 2 1]) is one of the 328 possible row/column sums for a 3 X 3 matrix.

Andrew Howroyd, Table of n, a(n) for n = 0..100
Mathematics Stack Exchange, Spanning forests of bipartite graphs and distinct row/column sums of binary matrices
Lars Nagel & Tim Süß, Computing the Probability for Data Loss in Two-Dimensional Parity RAIDs, 2017 13th European Dependable Computing Conference (EDCC), 58-65.
Rebecca J. Stones, Computing the number of h-edge spanning forests in complete bipartite graphs, Discrete Mathematics & Theoretical Computer Science, vol. 16, no. 1, pp. 313-326, 2014.

Main diagonal of A328887.

Cf. A048163 gives the number of row/column sums that uniquely identify a matrix.

{1}~Join~Array[Length@ Union@ Map[Total /@ {Transpose@ #, #} &, Tuples[{0, 1}, {#, #}]] &, 4] (* Michael De Vlieger, Jan 11 2018 *)

Terms a(6) and beyond from Andrew Howroyd, Oct 29 2019

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

A329052 Array read by antidiagonals: T(n,m) is the number of unlabeled bicolored acyclic graphs with n nodes of one color and m of the other.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 10, 10, 5, 1, 1, 6, 15, 21, 15, 6, 1, 1, 7, 21, 38, 38, 21, 7, 1, 1, 8, 28, 62, 82, 62, 28, 8, 1, 1, 9, 36, 95, 158, 158, 95, 36, 9, 1, 1, 10, 45, 138, 278, 356, 278, 138, 45, 10, 1, 1, 11, 55, 192, 459, 724, 724, 459, 192, 55, 11, 1

Offset: 0

Andrew Howroyd, Nov 02 2019

The two color classes are not interchangeable. Adjacent nodes cannot have the same color.

			Array begins:
=======================================================
n\m | 0  1   2    3    4     5     6      7      8
----+--------------------------------------------------
  0 | 1, 1,  1,   1,   1,    1,    1,     1,     1, ...
  1 | 1, 2,  3,   4,   5,    6,    7,     8,     9, ...
  2 | 1, 3,  6,  10,  15,   21,   28,    36,    45, ...
  3 | 1, 4, 10,  21,  38,   62,   95,   138,   192, ...
  4 | 1, 5, 15,  38,  82,  158,  278,   459,   716, ...
  5 | 1, 6, 21,  62, 158,  356,  724,  1359,  2388, ...
  6 | 1, 7, 28,  95, 278,  724, 1690,  3612,  7143, ...
  7 | 1, 8, 36, 138, 459, 1359, 3612,  8731, 19404, ...
  8 | 1, 9, 45, 192, 716, 2388, 7143, 19404, 48213, ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325

Main diagonal is A329055.
Antidiagonal sums are A329053.
The equivalent array for labeled nodes is A328887.
Cf. A329054.

EulerXY(A)={my(j=serprec(A,x)); exp(sum(i=1, j, 1/i * subst(subst(A + x * O(x^(j\i)), x, x^i), y, y^i)))}
R(n)={my(A=O(x)); for(j=1, 2*n, A = if(j%2, 1, y)*x*EulerXY(A)); A};
P(n)={my(r1=R(n), r2=x*EulerXY(r1), s=r1+r2-r1*r2); Vec(EulerXY(s))}
{ my(A=P(10)); for(n=0, #A\2, for(k=0, #A\2, print1(polcoef(A[n+k+1], k), ", ")); print) }

cp's OEIS Frontend

A072590 Table T(n,k) giving number of spanning trees in complete bipartite graph K(n,k), read by antidiagonals.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A328888 Array read by antidiagonals: T(n,m) is the number of acyclic edge covers of the complete bipartite graph K_{n,m}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A297077 Number of distinct row and column sums for n X n (0, 1)-matrices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

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

A329052 Array read by antidiagonals: T(n,m) is the number of unlabeled bicolored acyclic graphs with n nodes of one color and m of the other.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI