A014501 -id:A014501 - cp's OEIS frontend

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

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

nonn

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

			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)

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.

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.

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.

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

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

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

A014500 Number of graphs with unlabeled (non-isolated) nodes and n labeled edges.

Original entry on oeis.org

1, 1, 2, 9, 70, 794, 12055, 233238, 5556725, 158931613, 5350854707, 208746406117, 9315261027289, 470405726166241, 26636882237942128, 1678097862705130667, 116818375064650241036, 8932347052564257212796, 746244486452472386213939, 67796741482683128375533560

Offset: 0

Simon Plouffe, Gilbert Labelle (gilbert(AT)lacim.uqam.ca)

nonn

G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004.

Alois P. Heinz, Table of n, a(n) for n = 0..100
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Peter Cameron, Thomas Prellberg, Dudley Stark, Asymptotic enumeration of 2-covers and line graphs, Discrete Math. 310 (2010), no. 2, 230-240 (see u_n).
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]

Row n=2 of A331126.

Cf. A020554, A020555, A014501, A060053.

read("transforms") ;
A020556 := proc(n) local k; add((-1)^(n+k)*binomial(n, k)*combinat[bell](n+k), k=0..n) end proc:
A014500 := proc(n) local i,gexp,lexp;
gexp := [seq(1/2^i/i!,i=0..n+1)] ;
lexp := add( A020556(i)*((log(1+x))/2)^i/i!,i=0..n+1) ;
lexp := taylor(lexp,x=0,n+1) ;
lexp := gfun[seriestolist](lexp,'ogf') ;
CONV(gexp,lexp) ; op(n+1,%)*n! ; end proc:
seq(A014500(n),n=0..20) ; # R. J. Mathar, Jul 03 2011

max = 20; A020556[n_] := Sum[(-1)^(n+k)*Binomial[n, k]*BellB[n+k], {k, 0, n}]; egf = Exp[x/2]*Sum[A020556[n]*(Log[1+x]/2)^n/n!, {n, 0, max}] + O[x]^max; CoefficientList[egf, x]*Range[0, max-1]! (* Jean-François Alcover, Feb 19 2017, after Vladeta Jovovic *)

\\ here egf1 is A020556 as e.g.f.
egf1(n)={my(bell=serlaplace(exp(exp(x + O(x^(2*n+1)))-1))); sum(i=0, n, sum(k=0, i, (-1)^k*binomial(i,k)*polcoef(bell, 2*i-k))*x^i/i!) + O(x*x^n)}
seq(n)={my(B=egf1(n), L=log(1+x + O(x*x^n))/2); Vec(serlaplace(exp(x/2 + O(x*x^n))*sum(k=0, n, polcoef(B ,k)*L^k)))} \\ Andrew Howroyd, Jan 13 2020

E.g.f.: exp(-1+x/2)*Sum((1+x)^binomial(n, 2)/n!, n=0..infinity) [probably in the Labelle paper]. - Vladeta Jovovic, Apr 27 2004
E.g.f.: exp(x/2)*Sum(A020556(n)*(log(1+x)/2)^n/n!, n=0..infinity). - Vladeta Jovovic, May 02 2004
Binomial transform of A060053.
The e.g.f.'s of A020554 (S(x)) and A014500 (U(x)) are related by S(x) = U(e^x-1).
The e.g.f.'s of A014500 (U(x)) and A060053 (V(x)) are related by U(x) = e^x*V(x).

A331161 Array read by antidiagonals: A(n,k) is the number of nonnegative integer matrices with k distinct columns and any number of nonzero rows with column sums n and rows in nonincreasing lexicographic order.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 7, 3, 1, 0, 1, 43, 28, 5, 1, 0, 1, 403, 599, 104, 7, 1, 0, 1, 5245, 23243, 6404, 332, 11, 1, 0, 1, 89132, 1440532, 872681, 57613, 1032, 15, 1, 0, 1, 1898630, 131530132, 222686668, 26560747, 473674, 2983, 22, 1

Offset: 0

Andrew Howroyd, Jan 10 2020

The condition that the rows be in nonincreasing order is equivalent to considering nonequivalent matrices up to permutation of rows

			Array begins:
====================================================================
n\k | 0  1    2       3           4             5              6
----+---------------------------------------------------------------
  0 | 1  1    0       0           0             0              0 ...
  1 | 1  1    1       1           1             1              1 ...
  2 | 1  2    7      43         403          5245          89132 ...
  3 | 1  3   28     599       23243       1440532      131530132 ...
  4 | 1  5  104    6404      872681     222686668    95605470805 ...
  5 | 1  7  332   57613    26560747   26852940027 52296207431182 ...
  6 | 1 11 1032  473674   712725249 2776638423133 ...
  7 | 1 15 2983 3599384 17328777789 ...
  ...
The A(2,2) = 7 matrices are:
   [2 1]   [2 0]   [1 2]   [1 1]   [2 0]   [1 0]   [1 0]
   [0 1]   [0 2]   [1 0]   [1 0]   [0 1]   [1 0]   [1 0]
                           [0 1]   [0 1]   [0 2]   [0 1]
                                                   [0 1]

Andrew Howroyd, Table of n, a(n) for n = 0..209

Rows n=1..3 are A000012, A014501, A331196.
Columns k=0..2 are A000012, A000041, A331197.
Cf. A219727, A330158, A331039, A331126, A331160, A331315.

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
D(p, n, k)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); binomial(EulerT(v)[n], k)*k!/prod(i=1, #v, i^v[i]*v[i]!)}
T(n, k)={my(m=n*k, q=Vec(exp(O(x*x^m) + intformal((x^n-1)/(1-x)))/(1-x))); if(n==0, k<=1, sum(j=0, m, my(s=0); forpart(p=j, s+=D(p, n, k), [1, n]); s*q[#q-j]))}

A(n, k) = Sum_{j=0..k} Stirling1(k, j)*A219727(n, j).

A330158(n) = Sum_{d|n} A(n/d, d).

A020563 Number of cyclic multigraphs on n labeled edges (with loops).

Original entry on oeis.org

1, 2, 9, 68, 750, 11178, 213895, 5068102, 144746329, 4880572564, 191104219619, 8573780527428, 435844228476008, 24868815362420244, 1579939008182007447, 110981916769308996238, 8567134375799509782211

Offset: 0

Gilbert Labelle (gilbert(AT)lacim.uqam.ca), Simon Plouffe

nonn

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]

Cf. A014501.

a(n) = Sum_{k=0..n} (-1)^(n-k)*Stirling1(n, k)*A014501(k). - Sean A. Irvine, Apr 25 2019

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A014500 Number of graphs with unlabeled (non-isolated) nodes and n labeled edges.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A331161 Array read by antidiagonals: A(n,k) is the number of nonnegative integer matrices with k distinct columns and any number of nonzero rows with column sums n and rows in nonincreasing lexicographic order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A020563 Number of cyclic multigraphs on n labeled edges (with loops).

Views

Author

Keywords

Links

Crossrefs

Formula