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