

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^{2n2}) 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



FORMULA

a(n) = 2*(n^2  n)^(n1) + (1/2)*Sum_{x=1..(n1)} Sum_{y=1..(n1)} b(n, x, y), where b(n, x, y) = binomial(n,x)*binomial(n,y)*x^(y1)*y^(x1)*(nx)^(ny1)*(ny)^(nx1).


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^(y1)*y^(x1)*(nx)^(ny1)*(ny)^(nx1), {x, 1, n1}, {y, 1, n1}]/2 + (2*(n^2n)^(n1)); Table[a[n], {n, 2, 10}] (* This will generate a(n) from n=2 to 10. *)


CROSSREFS



KEYWORD

nonn


AUTHOR

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


STATUS

approved



