|
Search: id:A107991
|
|
|
| A107991 |
|
Complexity (number of maximal spanning trees) in an unoriented simple graph with nodes {1,2,..,n} and edges {i,j} if i+j>n. |
|
+0
1
|
|
| 1, 1, 1, 3, 8, 40, 180, 1260, 8064, 72576, 604800, 6652800, 68428800, 889574400, 10897286400, 163459296000, 2324754432000, 39520825344000, 640237370572800, 12164510040883200
(list; graph; listen)
|
|
|
OFFSET
|
1,4
|
|
|
COMMENT
|
Proof of the formula: check that the associated combinatorial laplacian has eigenvalues {0,..n-1}\ {floor((n+1)/2)} by exhibiting a basis of eigenvectors (which are very simple).
|
|
REFERENCES
|
N. Biggs, Algebraic Graph Theory, Cambridge University Press (1974).
|
|
FORMULA
|
a(n)=(n-1)!/floor((n+1)/2)
|
|
EXAMPLE
|
a(1)=a(2)=a(3)=1 because the corresponding graphs are trees. a(4)=3 because
the corresponding graph is a is a triangle with one of its vertices adjacent
to a fourth vertex.
|
|
MAPLE
|
a:=n->(n-1)!/floor((n+1)/2);
|
|
CROSSREFS
|
Sequence in context: A034892 A072687 A110561 this_sequence A007175 A128322 A038048
Adjacent sequences: A107988 A107989 A107990 this_sequence A107992 A107993 A107994
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Roland Bacher (roland.bacher(AT)ujf-grenoble.fr), Jun 13 2005
|
|
|
Search completed in 0.002 seconds
|
