A020555 Number of multigraphs on n labeled edges (with loops). Also number of genetically distinct states amongst n individuals.

1, 2, 9, 66, 712, 10457, 198091, 4659138, 132315780, 4441561814, 173290498279, 7751828612725, 393110572846777, 22385579339430539, 1419799938299929267, 99593312799819072788, 7678949893962472351181, 647265784993486603555551, 59357523410046023899154274

Offset

0,2

Comments

Also the number of factorizations of (p_n#)^2. - David W. Wilson, Apr 30 2001

Also the number of multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n}. - Gus Wiseman, Jul 18 2018

a(n) gives the number of genetically distinct states for n diploid individuals in the case that maternal and paternal alleles transmitted to the individuals are not distinguished (if maternal and paternal alleles are distinguished, then the number of states is A000110(2n)). - Noah A Rosenberg, Aug 23 2022

References

D. E. Knuth, The Art of Computer Programming, Vol. 4A, Table A-1, page 778. - N. J. A. Sloane, Dec 30 2018

E. Keith Lloyd, Math. Proc. Camb. Phil. Soc., vol. 103 (1988), 277-284.

A. Murthy, Generalization of partition function, introducing Smarandache factor partitions. Smarandache Notions Journal, Vol. 11, No. 1-2-3, Spring 2000.

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..310 (first 101 terms from Vincenzo Librandi)

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]

Marko Riedel et al., Set partitions of {1,1,2,2,...,n,n}

E. A. Thompson, Gene identities and multiple relationships. Biometrics 30 (1974), 667-680. See Table 5.

Formula

Lloyd's article gives a complicated explicit formula.

E.g.f.: exp(-3/2 + exp(x)/2)*Sum_{n>=0} exp(binomial(n+1, 2)*x)/n! [probably in the Labelle paper]. - Vladeta Jovovic, Apr 27 2004

a(n) = A001055(A002110(n)^2). - Alois P. Heinz, Aug 23 2022

Example

From Gus Wiseman, Jul 18 2018: (Start)
The a(2) = 9 multiset partitions of {1, 1, 2, 2}:
  (1122),
  (1)(122), (2)(112), (11)(22), (12)(12),
  (1)(1)(22), (1)(2)(12), (2)(2)(11),
  (1)(1)(2)(2).
(End)

Maple

B := n -> combinat[bell](n):
P := proc(m, n) local k; global B; option remember;
if n = 0 then B(m)  else
(1/2)*( P(m+2, n-1) + P(m+1, n-1) + add( binomial(n-1, k)*P(m, k), k=0..n-1) ); fi; end;
r:=m->[seq(P(m, n), n=0..20)]; r(0); # N. J. A. Sloane, Dec 30 2018

Mathematica

max = 16; s = Series[Exp[-3/2 + Exp[x]/2]*Sum[Exp[Binomial[n+1, 2]*x]/n!, {n, 0, 3*max }], {x, 0, max}] // Normal; a[n_] := SeriesCoefficient[s, {x, 0, n}]*n!; Table[a[n] // Round, {n, 0, max} ] (* Jean-François Alcover, Apr 23 2014, after Vladeta Jovovic *)
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[mps[Ceiling[Range[1/2, n, 1/2]]]], {n, 5}] (* Gus Wiseman, Jul 18 2018 *)

Crossrefs

Row n=2 of A219727. - Alois P. Heinz, Nov 26 2012

Cf. A007716, A007717, A014500, A014501, A020554, A094574, A316974.

See also A322764. Row 0 of the array in A322765.

Main diagonal of A346500.

Cf. A001055, A002110.

Sequence in context: A331817 A118804 A365995 * A243281 A091795 A319286

Adjacent sequences: A020552 A020553 A020554 * A020556 A020557 A020558

Keyword

nonn

Author

Gilbert Labelle (gilbert(AT)lacim.uqam.ca), Simon Plouffe, N. J. A. Sloane

Status

approved