cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

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

Original entry on oeis.org

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

Views

Author

Michael Somos, Jun 23 2002

Keywords

Examples

			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)

References

  • 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.

Links

Crossrefs

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

Programs

  • Mathematica
    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 *)
  • PARI
    {T(n, k) = if( n<1 || k<1, 0, n^(k-1) * k^(n-1))}

Formula

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

Extensions

Scoins reference from Philippe Deléham, Dec 22 2003

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

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 15, 8, 1, 1, 16, 54, 54, 16, 1, 1, 32, 189, 328, 189, 32, 1, 1, 64, 648, 1856, 1856, 648, 64, 1, 1, 128, 2187, 9984, 16145, 9984, 2187, 128, 1, 1, 256, 7290, 51712, 129000, 129000, 51712, 7290, 256, 1, 1, 512, 24057, 260096, 968125, 1475856, 968125, 260096, 24057, 512, 1
Offset: 0

Views

Author

Andrew Howroyd, Oct 29 2019

Keywords

Comments

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

Examples

			Array begins:
====================================================================
n\m | 0   1    2      3       4         5          6           7
----+---------------------------------------------------------------
  0 | 1   1    1      1       1         1          1           1 ...
  1 | 1   2    4      8      16        32         64         128 ...
  2 | 1   4   15     54     189       648       2187        7290 ...
  3 | 1   8   54    328    1856      9984      51712      260096 ...
  4 | 1  16  189   1856   16145    129000     968125     6925000 ...
  5 | 1  32  648   9984  129000   1475856   15450912   151201728 ...
  6 | 1  64 2187  51712  968125  15450912  219682183  2862173104 ...
  7 | 1 128 7290 260096 6925000 151201728 2862173104 48658878080 ...
  ...

Links

Crossrefs

Column k=2 is A006234.
Main diagonal is A297077.
Cf. A072590, A328888.

Programs

  • PARI
    \\ here U is A328888 as matrix.
U(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}
T(n, m=n)={my(M=U(n, m)); matrix(n+1, m+1, n, m, 1 + sum(i=1, n-1, sum(j=1, m-1, binomial(n-1,i)*binomial(m-1,j)*M[i,j])))}
{ my(A=T(7)); for(i=1, #A, print(A[i,])) }

Formula

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

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

Views

Author

Andrew Howroyd, Oct 29 2019

Keywords

Links

Crossrefs

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

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

Original entry on oeis.org

1, 6, 18, 46, 110, 254, 574, 1278, 2814, 6142, 13310, 28670, 61438, 131070, 278526, 589822, 1245182, 2621438, 5505022, 11534334, 24117246, 50331646, 104857598, 218103806, 452984830, 939524094, 1946157054, 4026531838, 8321499134, 17179869182, 35433480190, 73014444030
Offset: 1

Views

Author

Andrew Howroyd, Oct 29 2019

Keywords

Links

Crossrefs

Column 2 of A328888.
Cf. A000225, A001787.

Programs

  • PARI
    a(n) = {(2 + n)*2^(n-1) - 2}
  • PARI
    Vec(x*(1 + x - 4*x^2) / ((1 - x)*(1 - 2*x)^2) + O(x^30)) \\ Colin Barker, Nov 05 2019

Formula

a(n) = 2*A000225(n-1) + A001787(n).
a(n) = (2 + n)*2^(n-1) - 2.
From Colin Barker, Nov 05 2019: (Start)
G.f.: x*(1 + x - 4*x^2) / ((1 - x)*(1 - 2*x)^2).
a(n) = 5*a(n-1) - 8*a(n-2) + 4*a(n-3) for n>3.
(End)
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.