cp's OEIS Frontend

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.

%I A107991 #43 Aug 15 2025 10:38:32
%S A107991 1,1,1,3,8,40,180,1260,8064,72576,604800,6652800,68428800,889574400,
%T A107991 10897286400,163459296000,2324754432000,39520825344000,
%U A107991 640237370572800,12164510040883200,221172909834240000,4644631106519040000,93666727314800640000
%N 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.
%C A107991 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).
%D A107991 N. Biggs, Algebraic Graph Theory, Cambridge University Press (1974).
%H A107991 Vincenzo Librandi, <a href="/A107991/b107991.txt">Table of n, a(n) for n = 1..450</a>
%H A107991 Niall Byrnes, Gary R. W. Greaves, and Matthew R. Foreman, <a href="https://arxiv.org/abs/2405.02541">Bootstrapping cascaded random matrix models: correlations in permutations of matrix products</a>, arXiv:2405.02541 [math-ph], 2024. See p. 7.
%H A107991 Pierre-Alain Sallard, <a href="/A107991/a107991_1.pdf">Coefficients of repeated integrals of hyperbolic cosine</a>.
%F A107991 a(n) = (n-1)!/floor((n+1)/2).
%F A107991 a(n+1) = n!/floor(n/2 + 1). - _M. F. Hasler_, Apr 21 2015
%F A107991 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
%F A107991 Sum_{n>=1} 1/a(n) = (e + sinh(1))/2 + cosh(1). - _Amiram Eldar_, Aug 15 2025
%e A107991 a(1)=a(2)=a(3)=1 because the corresponding graphs are trees.
%e A107991 a(4)=3 because the corresponding graph is a triangle with one of its vertices adjacent to a fourth vertex.
%p A107991 a:=n->(n-1)!/floor((n+1)/2);
%t A107991 Function[x, 1/x] /@
%t A107991 CoefficientList[Series[3*Exp[x]/4 + 1/4*Exp[-x] + x/2*Exp[x], {x, 0, 10}], x] (* _Pierre-Alain Sallard_, Dec 15 2018 *)
%t A107991 Table[(n - 1)! / Floor[(n + 1) / 2], {n, 1, 30}] (* _Vincenzo Librandi_, Dec 15 2018 *)
%o A107991 (PARI) A107991(n)=(n-1)!/round(n/2) \\ _M. F. Hasler_, Apr 21 2015
%o A107991 (Magma) [Factorial(n-1)/Floor((n+1)/2): n in [1..25]]; // _Vincenzo Librandi_, Dec 15 2018
%o A107991 (GAP) List([1..20],n->Factorial(n-1)/Int((n+1)/2)); # _Muniru A Asiru_, Dec 15 2018
%o A107991 (SageMath) [factorial(n-1)/floor((n+1)/2) for n in range(1,24)] # _Stefano Spezia_, May 10 2024
%Y A107991 Cf. A001113, A073742, A073743.
%K A107991 nonn
%O A107991 1,4
%A A107991 _Roland Bacher_, Jun 13 2005