login
a(n) is the number of alpha-labelings of graphs with n edges.
(Formerly M1231)
8

%I M1231 #57 Oct 28 2023 15:28:42

%S 1,2,4,10,30,106,426,1930,9690,53578,322650,2106250,14790810,

%T 111327178,893091930,7614236170,68695024410,654301474378,

%U 6557096219610,69005893630090,760519875693210,8763511069234378,105343011537811290,1319139904954848010

%N a(n) is the number of alpha-labelings of graphs with n edges.

%C Old name was: Balanced labeled graphs. New name taken from Mar 06 2021 comment from _Don Knuth_.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H C. Barrientos and S. M. Minion, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Minion/minion3.pdf">Enumerating families of labeled graphs</a>, J. Integer Seq., 18(2015), #15.1.7.

%H Henryk Fuks and Kate Sullivan, <a href="https://arxiv.org/abs/0711.1349">Enumeration of number-conserving cellular automata rules with two inputs</a>, arXiv:0711.1349 [nlin.CG], 2007; Journal of Cellular Automata 2 vol. 2 pp. 141-148 (2007).

%H David A. Sheppard, <a href="http://dx.doi.org/10.1016/0012-365X(76)90051-0">The factorial representation of major balanced labelled graphs</a>, Discrete Math., 15(1976), no. 4, 379-388.

%F If n is even then a(n) = 2*Sum_{j=1..floor(n/2)} j!^2*j^(n-2*j), otherwise a(n) = 2*Sum_{j=1..floor(n/2)} j!^2*j^(n-2*j) + ((n+1)/2)!*((n-1)/2)!. - _Jonathan Vos Post_, Nov 13 2007

%p A005193 := proc(q)

%p 2*add((j!)^2*j^(q-2*j),j=1..q/2) ;

%p if type(q,'odd') then

%p %+((q+1)/2)!*((q-1)/2)! ;

%p else

%p % ;

%p end if;

%p end proc:

%p seq(A005193(n),n=1..40) ; # _R. J. Mathar_, Jul 13 2014

%t a[n_] := 2 Sum[(j!)^2*j^(n-2j), {j, 1, n/2}] + Boole[OddQ[n]]*((n+1)/2)! * ((n-1)/2)!;

%t Array[a, 24] (* _Jean-François Alcover_, Nov 20 2017 *)

%Y Cf. A034384, A342225.

%K nonn

%O 1,2

%A _N. J. A. Sloane_

%E Renamed (using Comments entry from _Don Knuth_) by _Jon E. Schoenfield_, Oct 28 2023