|
| |
|
|
A100070
|
|
Number a(n) of forests with two components in the complete bipartite graph K_{n,n}.
|
|
0
| |
|
|
6, 117, 5632, 515625, 77262336, 17230990189, 5360119185408, 2219048868131217, 1180000000000000000, 783948341202404638821, 636404158746280870281216, 619884903445287035295372217, 713552333492738487958741450752
(list; graph; refs; listen; history; 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}.
|
|
|
REFERENCES
| 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, y\in [n-1]}b(n, x, y), where b(n, x, y)=binom{n}{x} binom{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. A069087, A083483, A000272.
Sequence in context: A052465 A113015 A024275 * A135869 A054957 A081537
Adjacent sequences: A100067 A100068 A100069 * A100071 A100072 A100073
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Woong Kook (andrewk(AT)math.uri.edu), Nov 02 2004
|
| |
|
|
