login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A100070 Number a(n) of forests with two components in the complete bipartite graph K_{n,n}. 1
6, 117, 5632, 515625, 77262336, 17230990189, 5360119185408, 2219048868131217, 1180000000000000000, 783948341202404638821, 636404158746280870281216, 619884903445287035295372217, 713552333492738487958741450752 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,1

COMMENTS

This sequence (a(n)) appears to dominate the sequence (n^{2n-2}) of the number of spanning trees in K_{n,n} for n>1. This shows that the sequence of independent set numbers for the cycle matroid of K_{n,n} is not monotone increasing unlike the complete graph K_{n}.

LINKS

G. C. Greubel, Table of n, a(n) for n = 2..214

N. Eaton, W. Kook and L. Thoma, Monotonicity for complete graphs, preprint, 2004.

FORMULA

a(n) = 2*(n^2 - n)^(n-1) + (1/2)*Sum_{x=1..(n-1)} Sum_{y=1..(n-1)} b(n, x, y), where b(n, x, y) = binomial(n,x)*binomial(n,y)*x^(y-1)*y^(x-1)*(n-x)^(n-y-1)*(n-y)^(n-x-1).

EXAMPLE

a(2)=6 because K_{2,2} is C_{4} the cycle of length 4 and there are 6 forests with two components in C_{4}.

MATHEMATICA

a[n_]:=Sum[Binomial[n, x]*Binomial[n, y]*x^(y-1)*y^(x-1)*(n-x)^(n-y-1)*(n-y)^(n-x-1), {x, 1, n-1}, {y, 1, n-1}]/2 + (2*(n^2-n)^(n-1)); Table[a[n], {n, 2, 10}] (* This will generate a(n) from n=2 to 10. *)

CROSSREFS

Cf. A000272, A069087, A083483.

Sequence in context: A259064 A300733 A332627 * A135869 A218713 A054957

Adjacent sequences:  A100067 A100068 A100069 * A100071 A100072 A100073

KEYWORD

nonn

AUTHOR

Woong Kook (andrewk(AT)math.uri.edu), Nov 02 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 15 04:34 EDT 2020. Contains 335763 sequences. (Running on oeis4.)