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

Author

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

Keywords

• nonn

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

Examples

			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)
		

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.

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.

Programs

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

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