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

1, 2, 4, 10, 30, 106, 426, 1930, 9690, 53578, 322650, 2106250, 14790810, 111327178, 893091930, 7614236170, 68695024410, 654301474378, 6557096219610, 69005893630090, 760519875693210, 8763511069234378, 105343011537811290, 1319139904954848010

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Old name was: Balanced labeled graphs. New name taken from Mar 06 2021 comment from Don Knuth.

References

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

Links

• C. Barrientos and S. M. Minion, Enumerating families of labeled graphs, J. Integer Seq., 18(2015), #15.1.7.
• Henryk Fuks and Kate Sullivan, Enumeration of number-conserving cellular automata rules with two inputs, arXiv:0711.1349 [nlin.CG], 2007; Journal of Cellular Automata 2 vol. 2 pp. 141-148 (2007).
• David A. Sheppard, The factorial representation of major balanced labelled graphs, Discrete Math., 15(1976), no. 4, 379-388.

Crossrefs

Cf. A034384, A342225.

Programs

Maple

A005193 := proc(q)
    2*add((j!)^2*j^(q-2*j),j=1..q/2) ;
    if type(q,'odd') then
        %+((q+1)/2)!*((q-1)/2)! ;
    else
        % ;
    end if;
end proc:
seq(A005193(n),n=1..40) ; # R. J. Mathar, Jul 13 2014

Mathematica

a[n_] := 2 Sum[(j!)^2*j^(n-2j), {j, 1, n/2}] + Boole[OddQ[n]]*((n+1)/2)! * ((n-1)/2)!;
Array[a, 24] (* Jean-François Alcover, Nov 20 2017 *)

Formula

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

Extensions

Renamed (using Comments entry from Don Knuth) by Jon E. Schoenfield, Oct 28 2023