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

1, 1, 3, 16, 139, 1750, 29388, 624889, 16255738, 504717929, 18353177160, 769917601384, 36803030137203, 1984024379014193, 119571835094300406, 7995677265437541258, 589356399302126773920, 47609742627231823142029, 4193665147256300117666879

Offset

0,3

Comments

Or, number of bicoverings of an n-set.

Or, number of 2-covers of [1,...,n].

Also the number of set multipartitions (multisets of sets) of {1, 1, 2, 2, 3, 3, ..., n, n}. - Gus Wiseman, Jul 18 2018

References

G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..100

Peter Cameron, Thomas Prellberg, Dudley Stark, Asymptotic enumeration of 2-covers and line graphs, Discrete Math. 310 (2010), no. 2, 230-240 (see s_n).

L. Comtet, Birecouvrements et birevêtements d’un ensemble fini, Studia Sci. Math. Hungar 3 (1968): 137-152. [Annotated scanned copy. Warning: the table of v(n,k) has errors.]

G. Labelle, Counting enriched multigraphs according to the number of their edges (or arcs), Discrete Math., 217 (2000), 237-248.

G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004. [Cached copy, with permission]

Formula

E.g.f.: exp(-3/2+exp(x)/2)*Sum(exp(binomial(n, 2)*x)/n!, n=0..infinity) [Comtet]. - Vladeta Jovovic, Apr 27 2004

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

E.g.f.: exp((exp(x)-1)/2)*Sum(A020556(n)*(x/2)^n/n!, n=0..infinity). - Vladeta Jovovic, May 02 2004

Stirling_2 transform of A014500.

The e.g.f.'s of A020554 (S(x)) and A014500 (U(x)) are related by S(x) = U(e^x-1).

Example

From Gus Wiseman, Jul 18 2018: (Start)
The a(3) = 16 set multipartitions of {1, 1, 2, 2, 3, 3}:
  (123)(123)
  (1)(23)(123) (2)(13)(123) (3)(12)(123) (12)(13)(23)
  (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)
  (1)(1)(2)(3)(23) (1)(2)(2)(3)(13) (1)(2)(3)(3)(12)
  (1)(1)(2)(2)(3)(3)
(End)

Mathematica

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 *)
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
Table[Length[Select[mps[Ceiling[Range[1/2, n, 1/2]]], And@@UnsameQ@@@#&]], {n, 5}] (* Gus Wiseman, Jul 18 2018 *)

Crossrefs

Row 2 of A188392.

Cf. A002718, A007716, A020555, A050535, A094574, A316974.

Sequence in context: A006057 A305472 A002719 * A062874 A321239 A349969

Adjacent sequences: A020551 A020552 A020553 * A020555 A020556 A020557

Keyword

nonn,nice,easy

Author

Gilbert Labelle (gilbert(AT)lacim.uqam.ca), Simon Plouffe

Status

approved