cp's OEIS Frontend

A020554 Number of multigraphs on n labeled edges (without loops).

%I A020554 #48 May 08 2025 22:55:08
%S A020554 1,1,3,16,139,1750,29388,624889,16255738,504717929,18353177160,
%T A020554 769917601384,36803030137203,1984024379014193,119571835094300406,
%U A020554 7995677265437541258,589356399302126773920,47609742627231823142029,4193665147256300117666879
%N A020554 Number of multigraphs on n labeled edges (without loops).
%C A020554 Or, number of bicoverings of an n-set.
%C A020554 Or, number of 2-covers of [1,...,n].
%C A020554 Also the number of set multipartitions (multisets of sets) of {1, 1, 2, 2, 3, 3, ..., n, n}. - _Gus Wiseman_, Jul 18 2018
%D A020554 G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004.
%H A020554 Alois P. Heinz, <a href="/A020554/b020554.txt">Table of n, a(n) for n = 0..100</a>
%H A020554 Peter Cameron, Thomas Prellberg, and Dudley Stark, <a href="http://dx.doi.org/10.1016/j.disc.2008.09.008">Asymptotic enumeration of 2-covers and line graphs</a>, Discrete Math. 310 (2010), no. 2, 230-240 (see s_n).
%H A020554 L. Comtet, <a href="/A002718/a002718.pdf">Birecouvrements et birevêtements d'un ensemble fini</a>, Studia Sci. Math. Hungar 3 (1968): 137-152. [Annotated scanned copy. Warning: the table of v(n,k) has errors.]
%H A020554 G. Labelle, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00265-4">Counting enriched multigraphs according to the number of their edges (or arcs)</a>, Discrete Math., 217 (2000), 237-248.
%H A020554 G. Paquin, <a href="/A038205/a038205.pdf">Dénombrement de multigraphes enrichis</a>, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004. [Cached copy, with permission]
%F A020554 E.g.f.: exp(-3/2+exp(x)/2) * Sum_{n>=0} exp(binomial(n, 2)*x)/n! [Comtet]. - _Vladeta Jovovic_, Apr 27 2004
%F A020554 E.g.f. (an equivalent version in Maple format): G:=exp(-1+(exp(z)-1)/2)*sum(exp(s*(s-1)*z/2)/s!, s=0..infinity);
%F A020554 E.g.f.: exp((exp(x)-1)/2)*Sum_{n>=0} A020556(n)*(x/2)^n/n!. - _Vladeta Jovovic_, May 02 2004
%F A020554 Stirling_2 transform of A014500.
%F A020554 The e.g.f.'s of A020554 (S(x)) and A014500 (U(x)) are related by S(x) = U(e^x-1).
%e A020554 From _Gus Wiseman_, Jul 18 2018: (Start)
%e A020554 The a(3) = 16 set multipartitions of {1, 1, 2, 2, 3, 3}:
%e A020554   (123)(123)
%e A020554   (1)(23)(123) (2)(13)(123) (3)(12)(123) (12)(13)(23)
%e A020554   (1)(1)(23)(23) (1)(2)(3)(123) (1)(2)(13)(23) (1)(3)(12)(23) (2)(2)(13)(13) (2)(3)(12)(13) (3)(3)(12)(12)
%e A020554   (1)(1)(2)(3)(23) (1)(2)(2)(3)(13) (1)(2)(3)(3)(12)
%e A020554   (1)(1)(2)(2)(3)(3)
%e A020554 (End)
%t A020554 Ceiling[ CoefficientList[ Series[ Exp[ -1 + (Exp[ z ] - 1)/2 ]Sum[ Exp[ s(s - 1)z/2 ]/s!, {s, 0, 21} ], {z, 0, 9} ], z ] Table[ n!, {n, 0, 9} ] ] (* _Mitch Harris_, May 01 2004 *)
%t A020554 sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];
%t A020554 mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
%t A020554 Table[Length[Select[mps[Ceiling[Range[1/2,n,1/2]]],And@@UnsameQ@@@#&]],{n,5}] (* _Gus Wiseman_, Jul 18 2018 *)
%Y A020554 Row 2 of A188392.
%Y A020554 Cf. A002718, A007716, A020555, A050535, A094574, A316974.
%K A020554 nonn,nice,easy
%O A020554 0,3
%A A020554 Gilbert Labelle (gilbert(AT)lacim.uqam.ca) and _Simon Plouffe_