login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 3
1, 1, 1, 3, 8, 40, 180, 1260, 8064, 72576, 604800, 6652800, 68428800, 889574400, 10897286400, 163459296000, 2324754432000, 39520825344000, 640237370572800, 12164510040883200, 221172909834240000, 4644631106519040000, 93666727314800640000 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

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

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 1..450

Pierre-Alain Sallard, Coefficients of repeated integrals of hyperbolic cosine

FORMULA

a(n) = (n-1)!/floor((n+1)/2).

a(n+1) = n!/floor(n/2 + 1). - M. F. Hasler, Apr 21 2015

1/a(n+1) is the coefficient of the power series of 3*exp(x)/4 + 1/4*exp(-x) + x/2*exp(x) ; this function is the sum of f_n(x) where f_0(x)=cosh(x) and f_{n+1} is the primitive of f_n. - Pierre-Alain Sallard, Dec 15 2018

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);

MATHEMATICA

Function[x, 1/x] /@

CoefficientList[Series[3*Exp[x]/4 + 1/4*Exp[-x] + x/2*Exp[x], {x, 0, 10}], x] (* Pierre-Alain Sallard, Dec 15 2018 *)

Table[(n - 1)! / Floor[(n + 1) / 2], {n, 1, 30}] (* Vincenzo Librandi, Dec 15 2018 *)

PROG

(PARI) A107991(n)=(n-1)!/round(n/2) \\ M. F. Hasler, Apr 21 2015

(MAGMA) [Factorial(n-1)/Floor((n+1)/2): n in [1..25]]; // Vincenzo Librandi, Dec 15 2018

(GAP) List([1..20], n->Factorial(n-1)/Int((n+1)/2)); # Muniru A Asiru, Dec 15 2018

CROSSREFS

Sequence in context: A260817 A262126 A110561 * A007175 A152394 A168468

Adjacent sequences:  A107988 A107989 A107990 * A107992 A107993 A107994

KEYWORD

nonn

AUTHOR

Roland Bacher, Jun 13 2005

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 June 19 23:01 EDT 2019. Contains 324222 sequences. (Running on oeis4.)