login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A020555 Number of multigraphs on n labeled edges (with loops). Also number of genetically distinct states amongst n individuals. 23
1, 2, 9, 66, 712, 10457, 198091, 4659138, 132315780, 4441561814, 173290498279, 7751828612725, 393110572846777, 22385579339430539, 1419799938299929267, 99593312799819072788, 7678949893962472351181, 647265784993486603555551, 59357523410046023899154274 (list; graph; refs; listen; history; text; internal format)
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

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

Vincenzo Librandi, Table of n, a(n) for n = 0..100

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., Math.Stackexchange.com Set partitions of {1,1,2,2,...,n,n}

FORMULA

Lloyd's article gives a complicated explicit formula.

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

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.

Sequence in context: A196193 A331817 A118804 * 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 4 12:18 EDT 2020. Contains 335448 sequences. (Running on oeis4.)