cp's OEIS Frontend

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

%I A020555 #73 Aug 25 2022 08:32:26
%S A020555 1,2,9,66,712,10457,198091,4659138,132315780,4441561814,173290498279,
%T A020555 7751828612725,393110572846777,22385579339430539,1419799938299929267,
%U A020555 99593312799819072788,7678949893962472351181,647265784993486603555551,59357523410046023899154274
%N A020555 Number of multigraphs on n labeled edges (with loops). Also number of genetically distinct states amongst n individuals.
%C A020555 Also the number of factorizations of (p_n#)^2. - _David W. Wilson_, Apr 30 2001
%C A020555 Also the number of multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n}. - _Gus Wiseman_, Jul 18 2018
%C A020555 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
%D A020555 D. E. Knuth, The Art of Computer Programming, Vol. 4A, Table A-1, page 778. - _N. J. A. Sloane_, Dec 30 2018
%D A020555 E. Keith Lloyd, Math. Proc. Camb. Phil. Soc., vol. 103 (1988), 277-284.
%D A020555 A. Murthy, Generalization of partition function, introducing Smarandache factor partitions. Smarandache Notions Journal, Vol. 11, No. 1-2-3, Spring 2000.
%D A020555 G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004.
%H A020555 Alois P. Heinz, <a href="/A020555/b020555.txt">Table of n, a(n) for n = 0..310</a> (first 101 terms from Vincenzo Librandi)
%H A020555 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 A020555 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]
%H A020555 Marko Riedel et al., <a href="http://math.stackexchange.com/questions/1381495/">Set partitions of {1,1,2,2,...,n,n}</a>
%H A020555 E. A. Thompson, <a href="https://doi.org/10.2307/2529231">Gene identities and multiple relationships</a>. Biometrics 30 (1974), 667-680. See Table 5.
%F A020555 Lloyd's article gives a complicated explicit formula.
%F A020555 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
%F A020555 a(n) = A001055(A002110(n)^2). - _Alois P. Heinz_, Aug 23 2022
%e A020555 From _Gus Wiseman_, Jul 18 2018: (Start)
%e A020555 The a(2) = 9 multiset partitions of {1, 1, 2, 2}:
%e A020555   (1122),
%e A020555   (1)(122), (2)(112), (11)(22), (12)(12),
%e A020555   (1)(1)(22), (1)(2)(12), (2)(2)(11),
%e A020555   (1)(1)(2)(2).
%e A020555 (End)
%p A020555 B := n -> combinat[bell](n):
%p A020555 P := proc(m,n) local k; global B; option remember;
%p A020555 if n = 0 then B(m)  else
%p A020555 (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;
%p A020555 r:=m->[seq(P(m,n),n=0..20)]; r(0); # _N. J. A. Sloane_, Dec 30 2018
%t A020555 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_ *)
%t A020555 sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];
%t A020555 mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
%t A020555 Table[Length[mps[Ceiling[Range[1/2,n,1/2]]]],{n,5}] (* _Gus Wiseman_, Jul 18 2018 *)
%Y A020555 Row n=2 of A219727. - _Alois P. Heinz_, Nov 26 2012
%Y A020555 Cf. A007716, A007717, A014500, A014501, A020554, A094574, A316974.
%Y A020555 See also A322764. Row 0 of the array in A322765.
%Y A020555 Main diagonal of A346500.
%Y A020555 Cf. A001055, A002110.
%K A020555 nonn
%O A020555 0,2
%A A020555 Gilbert Labelle (gilbert(AT)lacim.uqam.ca), _Simon Plouffe_, _N. J. A. Sloane_