A068087 -id:A068087 - 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

A070968 Number of cycles in the complete bipartite graph K(n,n).

Original entry on oeis.org

0, 1, 15, 204, 3940, 113865, 4662231, 256485040, 18226108944, 1623855701385, 177195820499335, 23237493232953516, 3605437233380095620, 653193551573628900289, 136634950180317224866335, 32681589590709963123092160, 8863149183726257535369633856

Offset: 1

Sharon Sela (sharonsela(AT)hotmail.com), May 17 2002

nonn

Also the number of chordless cycles in the n X n rook graph. - Eric W. Weisstein, Nov 27 2017

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

Row sums of A291909.
Main diagonal of A360849.
Cf. A002807, A068087, A288035.

seq(simplify((1/4)*hypergeom([1, 2, 2-n, 2-n], [3], 1)*(n-1)^2*n^2), n=1..20); # Robert Israel, Jan 09 2018

Table[Sum[Binomial[n, k]^2*k!*(k - 1)!, {k, 2, n}]/2, {n, 1, 17}]
Table[n^2 (HypergeometricPFQ[{1, 1, 1 - n, 1 - n}, {2}, 1] - 1)/2, {n, 20}] (* Eric W. Weisstein, Dec 14 2017 *)

for(n=1,50,print1(sum(k=2,n,binomial(n,k)^2 * k! * (k-1)!/2),","))

a(n) = Sum_{k=2..n} C(n,k)^2 * k! * (k-1)! / 2.
Recurrence: (n-2)^2*(2*n^3 - 19*n^2 + 58*n - 59)*a(n) = 2*(2*n^7 - 31*n^6 + 200*n^5 - 700*n^4 + 1442*n^3 - 1764*n^2 + 1205*n - 363)*a(n-1) - (n-1)^2*(2*n^7 - 35*n^6 + 266*n^5 - 1139*n^4 + 2962*n^3 - 4671*n^2 + 4130*n - 1578)*a(n-2) + 2*(n-2)^2*(n-1)^2*(2*n^5 - 26*n^4 + 134*n^3 - 342*n^2 + 431*n - 217)*a(n-3) - (n-3)^2*(n-2)^2*(n-1)^2*(2*n^3 - 13*n^2 + 26*n - 18)*a(n-4). - Vaclav Kotesovec, Mar 08 2016
a(n) ~ c * n! * (n-1)!, where c = BesselI(0,2)/2 = 1.1397926511680336337186... . - Vaclav Kotesovec, Mar 08 2016

More terms from Benoit Cloitre and Robert G. Wilson v, May 20 2002

a(16)-a(17) from Andrew Howroyd, Jan 08 2018

A294360 G.f. A(x) satisfies: [x^(n-1)] A(x)^(n^2) = (n^2)^(n-1) for n>=1.

Original entry on oeis.org

1, 1, 5, 146, 9935, 1161399, 206499453, 52093726159, 17770811461875, 7903030237890371, 4450363873663943294, 3098938855124650814264, 2616552190721485829559668, 2635178871851323631797948230, 3121810359776427044817295874677, 4298670834657263815567279951080956, 6809336162211769799756516349665301635, 12296952422064277377043754761717448273557, 25116528778581121454413639996325045161219974

Offset: 0

Paul D. Hanna, Nov 01 2017

nonn

			G.f.: A(x) = 1 + x + 5*x^2 + 146*x^3 + 9935*x^4 + 1161399*x^5 + 206499453*x^6 + 52093726159*x^7 + 17770811461875*x^8 + 7903030237890371*x^9 + 4450363873663943294*x^10 + 3098938855124650814264*x^11 + 2616552190721485829559668*x^12 +...
such that the coefficient of x^(n-1) in A(x)^(n^2) equals (n^2)^(n-1) for n>=1.
The table of coefficients of x^k in A(x)^(n^2) begin:
n=1: [1, 1, 5, 146, 9935, 1161399, 206499453, ...];
n=2: [1, 4, 26, 648, 41703, 4775648, 840796570, ...];
n=3: [1, 9, 81, 1758, 102213, 11266209, 1949437539, ...];
n=4: [1, 16, 200, 4096, 207220, 21470032, 3617873616, ...];
n=5: [1, 25, 425, 8950, 390625, 36920005, 5985228975, ...];
n=6: [1, 36, 810, 18696, 723375, 60466176, 9272944890, ...];
n=7: [1, 49, 1421, 37338, 1347843, 97588547, 13841287201, ...];
n=8: [1, 64, 2336, 71168, 2535248, 159036480, 20303433408, 4398046511104, ...]; ...
in which the main diagonal begins:
[1, 4, 81, 4096, 390625, 60466176, 13841287201, 4398046511104, ..., (n^2)^(n-1), ...].

Paul D. Hanna, Table of n, a(n) for n = 0..200

Cf. A263190, A263075, A171791, A068087.

{a(n) = my(A=[1]); for(m=2,n+1, A = concat(A,0); A[m] = ( (m^2)^(m-1) - Vec( Ser(A)^(m^2) )[m] )/m^2);A[n+1]}
for(n=0,20,print1(a(n),", "))

a(n) ~ c * n^(2*n - 2), where c = exp(2 - exp(-2)) = 6.453771681742981632532303... - Vaclav Kotesovec, Aug 11 2021, updated Mar 18 2024

A070285 a(n) = n^(n-2) * (n-1)^(n-1).

Original entry on oeis.org

1, 12, 432, 32000, 4050000, 784147392, 215886856192, 80244904034304, 38742048900000000, 23579476910000000000, 17665746626579203620864, 15979082092619945289449472, 17171174753799627467382181888, 21626132883476724540000000000000, 31553580184752881664000000000000000

Offset: 2

Sharon Sela (sharonsela(AT)hotmail.com), May 10 2002

nonn

Number of spanning trees in the bipartite graph K(n,n-1).

J. J. Sylvester, On the change of systems of independent variables, Quarterly Journal of Mathematics, i. (1857), pp. 42-56; Collected Mathematical Papers, Volume 2, Cambridge (1908), pp. 65-85, see page 76.

Vincenzo Librandi, Table of n, a(n) for n = 2..100

Cf. A068087.

[n^(n-2) * (n-1)^(n-1): n in [2..20]]; // Vincenzo Librandi, Mar 04 2014

A070285:=n->n^(n-2) * (n-1)^(n-1); seq(A070285(n), n=2..15); # Wesley Ivan Hurt, Feb 26 2014

Table[n^(n - 2)*(n - 1)^(n - 1), {n, 2, 15}]

Edited by Robert G. Wilson v, May 14 2002

More terms from Vincenzo Librandi, Mar 04 2014

A328889 Number of acyclic edge covers of the complete bipartite graph K_{n,n}.

Original entry on oeis.org

1, 6, 132, 6728, 632970, 96208632, 21634786586, 6765592120576, 2811089200308642, 1498814096387846600, 997811910708863804202, 811362765374061475234464, 791392079095826028308709026, 912043721764132114072259699656, 1226095938791120621169019081161450

Offset: 1

Andrew Howroyd, Oct 29 2019

nonn

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

Main diagonal of A328888.
Cf. A068087 (spanning trees).
Cf. A297077 (not necessarily covering edge sets).

A255192 Triangle of number of connected subgraphs of K(n,n) with m edges.

Original entry on oeis.org

1, 4, 1, 81, 78, 36, 9, 1, 4096, 8424, 9552, 7464, 4272, 1812, 560, 120, 16, 1, 390625, 1359640, 2696200, 3880300, 4394600, 4059000, 3111140, 1994150, 1070150, 478800, 176900, 53120, 12650, 2300, 300, 25, 1, 60466176, 314452800, 939988800, 2075760000

Offset: 1

Thomas Dybdahl Ahle, Feb 16 2015

m ranges from 2n-1 to n^2.

First column is A068087.

			Triangle begins:
----|------------------------------------------------------------
n\m |  1 2 3 4  5  6    7    8    9   10   11   12  13  14 15 16
----|------------------------------------------------------------
1   |  1
2   |  - - 4 1
3   |  - - - - 81 78   36    9    1
4   |  - - - -  -  - 4096 8424 9552 7464 4272 1812 560 120 16  1

Cf. A005333 (row sums?).

from math import comb as binomial
def f(x, a, b, k):
    if b == k == 0:
        return 1
    if b == 0 or k == 0:
        return 0
    if x == a:
        return sum(binomial(a, n) * f(x, x, b - 1, k - n) for n in range(1, a + 1))
    return sum(binomial(b, n) * f(x, x, n, k2) * f(n, b, a - x, k - k2)
        for n in range(1, b + 1) for k2 in range(0, k + 1) )
def a(n, m):
    return f(1, n, n, m)
for n in range(1, 5):
    print([a(n, m) for m in range(1, n * n + 1)])

Sum(k>=0, T(n,k)*(-1)^k ) = A136126(2*n-1,n-1) = A092552(n+1), alternating row sums.

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

A070968 Number of cycles in the complete bipartite graph K(n,n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A294360 G.f. A(x) satisfies: [x^(n-1)] A(x)^(n^2) = (n^2)^(n-1) for n>=1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A070285 a(n) = n^(n-2) * (n-1)^(n-1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Extensions

A328889 Number of acyclic edge covers of the complete bipartite graph K_{n,n}.

Views

Author

Keywords

Links

Crossrefs

A255192 Triangle of number of connected subgraphs of K(n,n) with m edges.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula