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

A132608 Self-convolution square-root of A062817 (offset 2); thus g.f. A(x) satisfies: A(x)^2 = Sum_{n>=2} A062817(n)x^n, where A062817(n) = Sum_{k=0..n} (n-k)^kk^(n-k).

Original entry on oeis.org

1, 2, 9, 58, 469, 4530, 50491, 634790, 8861043, 135750454, 2262315973, 40726646802, 787471241647, 16275700505510, 358103286781293, 8357593147404346, 206241859929682177, 5366082228239257410

Offset: 1

Paul D. Hanna, Aug 26 2007

nonn

			A(x) = x + 2x^2 + 9x^3 + 58x^4 + 469x^5 + 4530x^6 +...+ a(n)*x^n +...
A(x)^2 = x^2 + 4x^3 + 22x^4 + 152x^5 + 1251x^6 +...+ A062817(n)*x^n +...

Vaclav Kotesovec, Table of n, a(n) for n = 1..425

Cf. A062817, A132609.

nmax = 20; CoefficientList[Series[(Sum[x^(k-2) * Sum[(k-j)^j * j^(k-j), {j, 0, k}], {k, 1, 2*nmax}])^(1/2), {x, 0, nmax}], x] (* Vaclav Kotesovec, Nov 22 2021 *)

{a(n)=polcoeff((sum(m=2,n+1,sum(k=0,m,(m-k)^k*k^(m-k))*x^m +x*O(x^(n+1))))^(1/2),n)}

a(n) ~ exp(1) * sqrt(2*Pi/3) * n^(n + 3/2) / 2^(n+3). - Vaclav Kotesovec, Nov 22 2021

A381726 Number of minimum connected dominating sets in the n X n black bishop graph.

Original entry on oeis.org

1, 2, 1, 1, 2, 13, 83, 513, 4052, 41197, 462069, 5597201, 76094134, 1153902701, 18981358311, 336018968449, 6413439874792, 131386321421901, 2867812411156521, 66426533670738769, 1629082910078009770, 42175861619149917325, 1148999152027728530363, 32856688248674995989889

Offset: 1

Eric W. Weisstein, Mar 05 2025

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Black Bishop Graph.
Eric Weisstein's World of Mathematics, Connected Dominating Set.

Cf. A381727 (white bishop).

Cf. A072590, A132609, A289145, A303141, A323500.

Join[{1, 2}, Table[Sum[(2 k - 1)^(n - 2 k - 1) (n - 2 k)^(2 (k - 1)), {k, Floor[(n - 1)/2]}], {n, 3, 20}]] (* Eric W. Weisstein, Mar 22 2025 *)

\\ B(n,k) is A072590.
B(n,k) = n^(k-1) * k^(n-1)
a(n) = if(n <= 2, n, sum(k=1, (n-1)\2, B(n-2*k, 2*k-1))) \\ Andrew Howroyd, Mar 20 2025

a(n) = Sum_{k=1..floor((n-1)/2)} A072590(n-2*k, 2*k-1) for n >= 3. - Andrew Howroyd, Mar 20 2025

a(10) onwards from Andrew Howroyd, Mar 20 2025

A381727 Number of minimum connected dominating sets in the n X n white bishop graph.

Original entry on oeis.org

2, 4, 1, 4, 13, 64, 513, 4480, 41197, 444416, 5597201, 77253632, 1153902701, 18870222848, 336018968449, 6428081455104, 131386321421901, 2865273888571392, 66426533670738769, 1629643279560867840, 42175861619149917325, 1148845693539400548352, 32856688248674995989889

Offset: 2

Eric W. Weisstein, Mar 05 2025

nonn

Andrew Howroyd, Table of n, a(n) for n = 2..200
Eric Weisstein's World of Mathematics, Connected Dominating Set.
Eric Weisstein's World of Mathematics, White Bishop Graph.

Cf. A381726 (black bishop).

Cf. A072590, A132609, A289169, A303144, A323501.

Join[{2, 4}, Table[Sum[(2 k)^(n - 2 k - 2) (n - 2 k - 1)^(2 k - 1), {k, Floor[n/2] - 1}], {n, 4, 20}]] (* Eric W. Weisstein, Mar 22 2025 *)

\\ B(n, k) is A072590.
B(n,k) = n^(k-1) * k^(n-1)
a(n) = if(n <= 3, 2*n-2, sum(k=1, n\2-1, B(n-1-2*k, 2*k))) \\ Andrew Howroyd, Mar 20 2025

a(n) = Sum_{k=1..floor(n\2)-1} A072590(n-1-2*k, 2*k) for n >= 4. - Andrew Howroyd, Mar 20 2025

a(10) onwards from Andrew Howroyd, Mar 20 2025

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

A132608 Self-convolution square-root of A062817 (offset 2); thus g.f. A(x) satisfies: A(x)^2 = Sum_{n>=2} A062817(n)*x^n, where A062817(n) = Sum_{k=0..n} (n-k)^k*k^(n-k).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A381726 Number of minimum connected dominating sets in the n X n black bishop graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A381727 Number of minimum connected dominating sets in the n X n white bishop graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A132608 Self-convolution square-root of A062817 (offset 2); thus g.f. A(x) satisfies: A(x)^2 = Sum_{n>=2} A062817(n)x^n, where A062817(n) = Sum_{k=0..n} (n-k)^kk^(n-k).