A094574 -id:A094574 - cp's OEIS frontend

A007717 Number of symmetric polynomial functions of degree n of a symmetric matrix (of indefinitely large size) under joint row and column permutations. Also number of multigraphs with n edges (allowing loops) on an infinite set of nodes.

1, 2, 7, 23, 79, 274, 1003, 3763, 14723, 59663, 250738, 1090608, 4905430, 22777420, 109040012, 537401702, 2723210617, 14170838544, 75639280146, 413692111521, 2316122210804, 13261980807830, 77598959094772, 463626704130058, 2826406013488180, 17569700716557737

Offset: 0

Colin Mallows

nonn

Euler transform of A007719.
Also the number of non-isomorphic multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n}. - Gus Wiseman, Jul 18 2018
Number of distinct n X 2n matrices with integer entries and rows sums 2, up to row and column permutations. - Andrew Howroyd, Sep 06 2018
a(n) is the number of unlabeled loopless multigraphs with n edges rooted at one vertex. - Andrew Howroyd, Nov 22 2020

			a(2) = 7 (here - denotes an edge, = denotes a pair of parallel edges and o is a loop):
  oo
  o o
  o-
  o -
  =
  --
  - -
From _Gus Wiseman_, Jul 18 2018: (Start)
Non-isomorphic representatives of the a(2) = 7 multiset partitions of {1, 1, 2, 2}:
  (1122),
  (1)(122), (11)(22), (12)(12),
  (1)(1)(22), (1)(2)(12),
  (1)(1)(2)(2).
(End)
From _Gus Wiseman_, Jan 08 2024: (Start)
Non-isomorphic representatives of the a(1) = 1 through a(3) = 7 rooted loopless multigraphs (root shown as singleton):
  {{1}}  {{1},{1,2}}  {{1},{1,2},{1,2}}
         {{1},{2,3}}  {{1},{1,2},{1,3}}
                      {{1},{1,2},{2,3}}
                      {{1},{1,2},{3,4}}
                      {{1},{2,3},{2,3}}
                      {{1},{2,3},{2,4}}
                      {{1},{2,3},{4,5}}
(End)

Huaien Li and David C. Torney, Enumerations of Multigraphs, 2002.

Andrew Howroyd, Table of n, a(n) for n = 0..50
Mateo Díaz, Dmitriy Drusvyatskiy, Jack Kendrick, and Rekha R. Thomas, Invariant Kernels: Rank Stabilization and Generalization Across Dimensions, arXiv:2502.01886 [math.OC], 2025. See p. 43.
Huaien Li and David C. Torney, Enumeration of unlabelled multigraphs, Ars Combin. 75 (2005) 171-188. MR2133219.
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 [math.CO] (2017) table 67.

Row n=2 of A331485.

Cf. A000664, A002620, A007716, A007719, A020555, A050531, A050532, A050535, A052171, A053418, A053419, A094574, A316972, A316974, A318951, A339065.

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t k; s += t]; s!/m];
Kq[q_, t_, k_] := SeriesCoefficient[1/Product[g = GCD[t, q[[j]]]; (1 - x^(q[[j]]/g))^g, {j, 1, Length[q]}], {x, 0, k}];
RowSumMats[n_, m_, k_] := Module[{s=0}, Do[s += permcount[q]* SeriesCoefficient[Exp[Sum[Kq[q, t, k]/t x^t, {t, 1, n}]], {x, 0, n}], {q, IntegerPartitions[m]}]; s/m!];
a[n_] := RowSumMats[n, 2n, 2];
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 0, 25}] (* Jean-François Alcover, Oct 27 2018, after Andrew Howroyd *)

\\ See A318951 for RowSumMats
a(n)=RowSumMats(n, 2*n, 2); \\ Andrew Howroyd, Sep 06 2018

\\ See A339065 for G.
seq(n)={my(A=O(x*x^n)); Vec(G(2*n, x+A, [1]))} \\ Andrew Howroyd, Nov 22 2020

More terms from Vladeta Jovovic, Jan 26 2000

a(0)=1 prepended and a(16)-a(25) added by Max Alekseyev, Jun 21 2011

A050535 Number of loopless multigraphs on infinite set of nodes with n edges.

Original entry on oeis.org

1, 1, 3, 8, 23, 66, 212, 686, 2389, 8682, 33160, 132277, 550835, 2384411, 10709827, 49782637, 238998910, 1182772364, 6023860266, 31525780044, 169316000494, 932078457785, 5253664040426, 30290320077851, 178480713438362, 1073918172017297

Offset: 0

Vladeta Jovovic, Dec 29 1999

nonn

Also, a(n) is the number of n-rowed binary matrices with all row sums equal to 2, up to row and column permutation (see Jovovic's formula). Also, a(n) is the limit of A192517(m,n) as m grows. - Max Alekseyev, Oct 18 2017
Row sums of the triangle defined by the Multiset Transformation of A076864,
;
1;
2 1;
5 2 1;
12 8 2 1;
33 22 8 2 1;
103 72 26 8 2 1;
333 229 87 26 8 2 1;
1183 782 295 92 26 8 2 1;
4442 2760 1036 315 92 26 8 2 1;
17576 10270 3735 1129 321 92 26 8 2 1;
72810 39770 13976 4117 1154 321 92 26 8 2 1;
314595 160713 54132 15547 4237 1161 321 92 26 8 2 1;
- R. J. Mathar, Jul 18 2017
Also the number of non-isomorphic set multipartitions (multisets of sets) of {1, 1, 2, 2, 3, 3, ..., n, n}. - Gus Wiseman, Jul 18 2018

			From _Gus Wiseman_, Jul 18 2018: (Start)
Non-isomorphic representatives of the a(3) = 8 set multipartitions of {1, 1, 2, 2, 3, 3}:
  (123)(123)
  (1)(23)(123)
  (12)(13)(23)
  (1)(1)(23)(23)
  (1)(2)(3)(123)
  (1)(2)(13)(23)
  (1)(1)(2)(3)(23)
  (1)(1)(2)(2)(3)(3)
(End)

Frank Harary and Edgar M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 88, Eq. (4.1.18).

Andrew Howroyd, Table of n, a(n) for n = 0..50
George Barnes, Sanjaye Ramgoolam, and Michael Stephanou, Permutation invariant Gaussian matrix models for financial correlation matrices, arXiv:2306.04569 [q-fin.ST], 2023.
Frank Harary, The number of linear, directed, rooted, and connected graphs, Trans. Am. Math. Soc. 78 (1955) 445-463, eq. (24).
Vladeta Jovovic, Number of m-rowed binary matrices with all row sums equal to n, up to row and column permutation
Patrick T. Komiske, Eric M. Metodiev, and Jesse Thaler, Energy flow polynomials: A complete linear basis for jet substructure, arXiv:1712.07124 [hep-ph], 2017.
Tsuyoshi Miezaki, Akihiro Munemasa, Yusaku Nishimura, Tadashi Sakuma, and Shuhei Tsujie, Universal graph series, chromatic functions, and their index theory, arXiv:2403.09985 [math.CO], 2024. See p. 23.

Cf. A001399, A003082, A014395, A014396, A014397, A014398.
Cf. A058389, A050913, A058783, A058390, A058784, A058785, A058391, A058392, A001501, A058528.
Cf. A007716, A007717, A020555, A050535, A076864 (inverse Euler transf.), A076867 (Euler transform) A094574, A316974.

seq[n_] := G[2n, x+O[x]^n, {}] // CoefficientList[#, x]&;
seq[15] (* Jean-François Alcover, Dec 02 2020, using Andrew Howroyd's code for G in A339065 *)

a(n) = A192517(2*n,n) = A192517(m,n) for any m>=2*n. - Max Alekseyev, Oct 18 2017

Euler transform of A076864. - Andrew Howroyd, Oct 23 2019

More terms from Sean A. Irvine, Oct 02 2011

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

Original entry on oeis.org

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

A278990 Number of loopless linear chord diagrams with n chords.

Original entry on oeis.org

1, 0, 1, 5, 36, 329, 3655, 47844, 721315, 12310199, 234615096, 4939227215, 113836841041, 2850860253240, 77087063678521, 2238375706930349, 69466733978519340, 2294640596998068569, 80381887628910919255, 2976424482866702081004, 116160936719430292078411

Offset: 0

N. J. A. Sloane, Dec 07 2016

nonn

See the signed version of these numbers, A000806, for much more information about these numbers.
From Gus Wiseman, Feb 27 2019: (Start)
Also the number of 2-uniform set partitions of {1..2n} containing no two successive vertices in the same block. For example, the a(3) = 5 set partitions are:
  {{1,3},{2,5},{4,6}}
  {{1,4},{2,5},{3,6}}
  {{1,4},{2,6},{3,5}}
  {{1,5},{2,4},{3,6}}
  {{1,6},{2,4},{3,5}}
(End)
From Gus Wiseman, Jul 05 2020: (Start)
Also the number of permutations of the multiset {1,1,2,2,...,n,n} with no two consecutive terms equal and where the first i appears before the first j for i < j. For example, the a(3) = 5 permutations are the following.
  (1,2,3,1,2,3)
  (1,2,3,1,3,2)
  (1,2,3,2,1,3)
  (1,2,3,2,3,1)
  (1,2,1,3,2,3)
(End)

Seiichi Manyama, Table of n, a(n) for n = 0..404 (terms 0..200 from Gheorghe Coserea)
Dmitry Efimov, The hafnian of Toeplitz matrices of a special type, perfect matchings and Bessel polynomials, arXiv:1904.08651 [math.CO], 2019.
H. Eriksson and A. Martin, Enumeration of Carlitz multipermutations, arXiv:1702.04177 [math.CO], 2017.
E. Krasko, I. Labutin, and A. Omelchenko, Enumeration of labelled and unlabelled Hamiltonian Cycles in complete k-partite graphs, arXiv:1709.03218 [math.CO], 2017, Table 1.
E. Krasko and A. Omelchenko, Enumeration of Chord Diagrams without Loops and Parallel Chords, arXiv:1601.05073 [math.CO], 2016.
E. Krasko and A. Omelchenko, Enumeration of Chord Diagrams without Loops and Parallel Chords, The Electronic Journal of Combinatorics, 24(3) (2017), #P3.43.
Gus Wiseman, The a(4) = 36 loopless linear chord diagrams.
Donovan Young, Counting Bubbles in Linear Chord Diagrams, arXiv:2311.01569 [math.CO], 2023.
Donovan Young, Bubbles in Linear Chord Diagrams: Bridges and Crystallized Diagrams, arXiv:2408.17232 [math.CO], 2024.

Column k=0 of A079267.
Column k=2 of A293157.
Row n=2 of A322013.
Cf. A000110, A000699 (topologically connected 2-uniform), A000806, A001147 (2-uniform), A003436 (cyclical version), A005493, A170941, A190823 (distance 3+ version), A322402, A324011, A324172.
Anti-run compositions are A003242.
Separable partitions are A325534.
Cf. A007716, A292884, A333489.
Other sequences involving the multiset {1,1,2,2,...,n,n}: A001147, A007717, A020555, A094574, A316972.

[n le 2 select 2-n else (2*n-3)*Self(n-1) + Self(n-2): n in [1..30]]; // G. C. Greubel, Sep 26 2023

RecurrenceTable[{a[n]== (2n-1)a[n-1] +a[n-2], a[0]==1, a[1]==0}, a, {n,0,20}] (* Vaclav Kotesovec, Sep 15 2017 *)
FullSimplify[Table[-I*(BesselI[1/2+n,-1] BesselK[3/2,1] - BesselI[3/2,-1] BesselK[1/2+ n,1]), {n,0,20}]] (* Vaclav Kotesovec, Sep 15 2017 *)
Table[(2 n-1)!! Hypergeometric1F1[-n,-2 n,-2], {n,0,20}] (* Eric W. Weisstein, Nov 14 2018 *)
Table[Sqrt[2/Pi]/E ((-1)^n Pi BesselI[1/2+n,1] +BesselK[1/2+n,1]), {n,0,20}] // FunctionExpand // FullSimplify (* Eric W. Weisstein, Nov 14 2018 *)
twouniflin[{}]:={{}};twouniflin[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@twouniflin[Complement[set,s]]]/@Table[{i,j},{j,Select[set,#>i+1&]}];
Table[Length[twouniflin[Range[n]]],{n,0,14,2}] (* Gus Wiseman, Feb 27 2019 *)

seq(N) = {
  my(a = vector(N)); a[1] = 0; a[2] = 1;
  for (n = 3, N, a[n] = (2*n-1)*a[n-1] + a[n-2]);
  concat(1, a);
};
seq(20) \\ Gheorghe Coserea, Dec 09 2016

def A278990_list(prec):
    P. = PowerSeriesRing(QQ, prec)
    return P( exp(-1+sqrt(1-2*x))/sqrt(1-2*x) ).egf_to_ogf().list()
A278990_list(30) # G. C. Greubel, Sep 26 2023

From Gheorghe Coserea, Dec 09 2016: (Start)
D-finite with recurrence a(n) = (2*n-1)*a(n-1) + a(n-2), with a(0) = 1, a(1) = 0.
E.g.f. y satisfies: 0 = (1-2*x)*y'' - 3*y' - y.
a(n) - a(n-1) = A003436(n) for all n >= 2. (End)
From Vaclav Kotesovec, Sep 15 2017: (Start)
a(n) = sqrt(2)*exp(-1)*(BesselK(1/2 + n, 1)/sqrt(Pi) - i*sqrt(Pi)*BesselI(1/2 + n, -1)), where i is the imaginary unit.
a(n) ~ 2^(n+1/2) * n^n  / exp(n+1). (End)
a(n) = A114938(n)/n! - Gus Wiseman, Jul 05 2020 (from Alexander Burstein's formula at A114938).
From G. C. Greubel, Sep 26 2023: (Start)
a(n) = (-1)^n * (i/e)*Sqrt(2/Pi) * BesselK(n + 1/2, -1).
G.f.: sqrt(Pi/(2*x)) * exp(-(1+x)^2/(2*x)) * Erfi((1+x)/sqrt(2*x)).
E.g.f.: exp(-1 + sqrt(1-2*x))/sqrt(1-2*x). (End)

a(0)=1 prepended by Gheorghe Coserea, Dec 09 2016

A114938 Number of permutations of the multiset {1,1,2,2,...,n,n} with no two consecutive terms equal.

Original entry on oeis.org

1, 0, 2, 30, 864, 39480, 2631600, 241133760, 29083420800, 4467125013120, 851371260364800, 197158144895712000, 54528028997584665600, 17752366094818747392000, 6720318485119046923315200, 2927066537906697348594432000, 1453437879238150456164433920000

Offset: 0

Hugo Pfoertner, Jan 08 2006

a(n) is also the number of (0,1)-matrices A=(a_ij) of size n X 2n such that each row has exactly two 1's and each column has exactly one 1 and with the restriction that no 1 stands on the line from a_11 to a_22. - Shanzhen Gao, Feb 24 2010
a(n) is the number of permutations of the multiset {1,1,2,2,...,n,n} with no fixed points. - Alexander Burstein, May 16 2020
Also the number of 2-uniform ordered set partitions of {1...2n} containing no two successive vertices in the same block. - Gus Wiseman, Jul 04 2020

			a(2) = 2 because there are two permutations of {1,1,2,2} avoiding equal consecutive terms: 1212 and 2121.

R. P. Stanley, Enumerative Combinatorics Volume I, Cambridge University Press, 1997. Chapter 2, Sieve Methods, Example 2.2.3, page 68.

Seiichi Manyama, Table of n, a(n) for n = 0..238 (terms 1..100 from Andrew Woods)
H. Eriksson and A. Martin, Enumeration of Carlitz multipermutations, arXiv:1702.04177 [math.CO], 2017.

Cf. A114939 = preferred seating arrangements of n couples.
Cf. A007060 = arrangements of n couples with no adjacent spouses; A007060(n) = 2^n * A114938(n) (this sequence).
Cf. A104548, A193638.
Cf. A278990 = number of loopless linear chord diagrams with n chords.
Cf. A000806 = Bessel polynomial y_n(-1).
The version for multisets with prescribed multiplicities is A335125.
The version for prime indices is A335452.
Anti-run compositions are counted by A003242.
Anti-run compositions are ranked by A333489.
Inseparable partitions are counted by A325535.
Inseparable partitions are ranked by A335448.
Separable partitions are counted by A325534.
Separable partitions are ranked by A335433.
Cf. A007716, A128695, A292884, A335126, A335434, A335451.
Other sequences involving the multiset {1,1,2,2,...,n,n}: A001147, A007717, A020555, A094574, A316972.
Row n=2 of A322093.

[1] cat [n le 2 select 2*(n-1) else n*(2*n-1)*Self(n-1) + (n-1)*n*Self(n-2): n in [1..20]]; // Vincenzo Librandi, Aug 10 2015

Table[Sum[Binomial[n,i](2n-i)!/2^(n-i) (-1)^i,{i,0,n}],{n,0,20}]  (* Geoffrey Critzer, Jan 02 2013, and adapted to the extension by Stefano Spezia, Nov 15 2018 *)
Table[Length[Select[Permutations[Join[Range[n],Range[n]]],!MatchQ[#,{_,x_,x_,_}]&]],{n,0,5}] (* Gus Wiseman, Jul 04 2020 *)
A114938[n_] := ((2 n)! Hypergeometric1F1[-n, -2 n, -2]) / 2^n;
Array[A114938, 17, 0]  (* Peter Luschny, Sep 04 2025 *)

A114938(n)=sum(k=0, n, binomial(n, k)*(-1)^(n-k)*(n+k)!/2^k);
vector(20, n, A114938(n-1)) \\ Michel Marcus, Aug 10 2015

def A114938(n): return (-1)^n*sum(binomial(n,k)*factorial(n+k)//(-2)^k for k in range(n+1))
[A114938(n) for n in range(31)] # G. C. Greubel, Sep 26 2023

a(n) = Sum_{k=0..n} ((binomial(n, k)*(-1)^(n-k)*(n+k)!)/2^k).
a(n) = (-1)^n * n! * A000806(n), n>0. - Vladeta Jovovic, Nov 19 2009
a(n) = n*(2*n-1)*a(n-1) + (n-1)*n*a(n-2). - Vaclav Kotesovec, Aug 07 2013
a(n) ~ 2^(n+1)*n^(2*n)*sqrt(Pi*n)/exp(2*n+1). - Vaclav Kotesovec, Aug 07 2013
a(n) = n! * A278990(n). - Alexander Burstein, May 16 2020
From G. C. Greubel, Sep 26 2023: (Start)
a(n) = (-1)^n * (i/e)*sqrt(2/Pi) * n! * BesselK(n+1/2, -1).
a(n) = [n! * (1/x) * p_{n+1}(x)]|A104548%20for%20p">{x= -1} (See A104548 for p{n}(x)).
E.g.f.: sqrt(Pi/(2*x)) * exp(-(1+x)^2/(2*x)) * erfi((1+x)/sqrt(2*x)).
Sum_{n >= 0} a(n)*x^n/(n!)^2 = exp(sqrt(1-2*x))/sqrt(1-2*x).
Sum_{n >= 0} a(n)*x^n/(n!*(n+1)!) = ( 1 - exp(-1 + sqrt(1-2*x)) )/x. (End)
a(n) = ((2*n)!/2^n) * hypergeom([-n], [-2*n], -2]) = A007060(n) / 2^n. - Peter Luschny, Sep 04 2025

a(0)=1 prepended by Seiichi Manyama, Nov 15 2018

A316974 Number of non-isomorphic strict multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n}.

Original entry on oeis.org

1, 1, 4, 14, 49, 173, 652, 2494

Offset: 0

Gus Wiseman, Jul 17 2018

Also the number of unlabeled multigraphs with n edges, allowing loops, spanning an initial interval of positive integers with no equivalent vertices (two vertices are equivalent if in every edge the multiplicity of the first is equal to the multiplicity of the second). For example, non-isomorphic representatives of the a(2) = 4 multigraphs are {(1,2),(1,3)}, {(1,1),(1,2)}, {(1,1),(2,2)}, {(1,1),(1,1)}.

			Non-isomorphic representatives of the a(3) = 14 strict multiset partitions:
  (112233),
  (1)(12233), (11)(2233), (12)(1233), (112)(233),
  (1)(2)(1233), (1)(12)(233), (1)(23)(123), (2)(11)(233), (11)(22)(33), (12)(13)(23),
  (1)(2)(3)(123), (1)(2)(12)(33), (1)(2)(13)(23).

Cf. A001055, A007716, A007717, A007719, A020554, A020555, A045778, A050535, A053419, A061742, A094574, A162247, A316892, A316972.

a(7) from Andrew Howroyd, Feb 07 2020

A346517 Number A(n,k) of partitions of the (n+k)-multiset {1,2,...,n,1,2,...,k} into distinct multisets; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 5, 3, 3, 5, 15, 9, 5, 9, 15, 52, 31, 18, 18, 31, 52, 203, 120, 70, 40, 70, 120, 203, 877, 514, 299, 172, 172, 299, 514, 877, 4140, 2407, 1393, 801, 457, 801, 1393, 2407, 4140, 21147, 12205, 7023, 4025, 2295, 2295, 4025, 7023, 12205, 21147

Offset: 0

Alois P. Heinz, Jul 21 2021

Also number A(n,k) of factorizations of Product_{i=1..n} prime(i) * Product_{i=1..k} prime(i) into distinct factors; A(2,2) = 5: 2*3*6, 4*9, 3*12, 2*18, 36.

			A(2,2) = 5: 1122, 11|22, 1|122, 112|2, 1|12|2.
Square array A(n,k) begins:
    1,    1,    2,     5,    15,     52,    203,     877, ...
    1,    1,    3,     9,    31,    120,    514,    2407, ...
    2,    3,    5,    18,    70,    299,   1393,    7023, ...
    5,    9,   18,    40,   172,    801,   4025,   21709, ...
   15,   31,   70,   172,   457,   2295,  12347,   70843, ...
   52,  120,  299,   801,  2295,   6995,  40043,  243235, ...
  203,  514, 1393,  4025, 12347,  40043, 136771,  875936, ...
  877, 2407, 7023, 21709, 70843, 243235, 875936, 3299218, ...
  ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns (or rows) k=0-10 give: A000110, A087648, A322773, A322774, A346897, A346898, A346899, A346900, A346901, A346902, A346903.
Main diagonal gives A094574.
First upper (or lower) diagonal gives A322771.
Second upper (or lower) diagonal gives A322772.
Antidiagonal sums give A346518.
Cf. A002110, A045778, A322770, A346500.

g:= proc(n, k) option remember; uses numtheory; `if`(n>k, 0, 1)+
     `if`(isprime(n), 0, add(`if`(d>k or max(factorset(n/d))>d, 0,
        g(n/d, d-1)), d=divisors(n) minus {1, n}))
    end:
p:= proc(n) option remember; `if`(n=0, 1, p(n-1)*ithprime(n)) end:
A:= (n, k)-> g(p(n)*p(k)$2):
seq(seq(A(n, d-n), n=0..d), d=0..10);
# second Maple program:
b:= proc(n) option remember; `if`(n=0, 1,
      add(b(n-j)*binomial(n-1, j-1), j=1..n))
    end:
A:= proc(n, k) option remember; `if`(n

(* Q is A322770 *)
Q[m_, n_] := Q[m, n] = If[n == 0, BellB[m], (1/2)(Q[m+2, n-1] + Q[m+1, n-1] - Sum[Binomial[n-1, k] Q[m, k], {k, 0, n-1}])];
A[n_, k_] := Q[Abs[n-k], Min[n, k]];
Table[A[n, d-n], {d, 0, 10}, {n, 0, d}] // Flatten (* Jean-François Alcover, Aug 19 2021 *)

A(n,k) = A045778(A002110(n)*A002110(k)).
A(n,k) = A(k,n).
A(n,k) = A322770(abs(n-k),min(n,k)).

A020554 Number of multigraphs on n labeled edges (without loops).

Original entry on oeis.org

1, 1, 3, 16, 139, 1750, 29388, 624889, 16255738, 504717929, 18353177160, 769917601384, 36803030137203, 1984024379014193, 119571835094300406, 7995677265437541258, 589356399302126773920, 47609742627231823142029, 4193665147256300117666879

Offset: 0

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

Or, number of bicoverings of an n-set.
Or, number of 2-covers of [1,...,n].
Also the number of set multipartitions (multisets of sets) of {1, 1, 2, 2, 3, 3, ..., n, n}. - Gus Wiseman, Jul 18 2018

			From _Gus Wiseman_, Jul 18 2018: (Start)
The a(3) = 16 set multipartitions of {1, 1, 2, 2, 3, 3}:
  (123)(123)
  (1)(23)(123) (2)(13)(123) (3)(12)(123) (12)(13)(23)
  (1)(1)(23)(23) (1)(2)(3)(123) (1)(2)(13)(23) (1)(3)(12)(23) (2)(2)(13)(13) (2)(3)(12)(13) (3)(3)(12)(12)
  (1)(1)(2)(3)(23) (1)(2)(2)(3)(13) (1)(2)(3)(3)(12)
  (1)(1)(2)(2)(3)(3)
(End)

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
Peter Cameron, Thomas Prellberg, and Dudley Stark, Asymptotic enumeration of 2-covers and line graphs, Discrete Math. 310 (2010), no. 2, 230-240 (see s_n).
L. Comtet, Birecouvrements et birevêtements d'un ensemble fini, Studia Sci. Math. Hungar 3 (1968): 137-152. [Annotated scanned copy. Warning: the table of v(n,k) has errors.]
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 2 of A188392.

Cf. A002718, A007716, A020555, A050535, A094574, A316974.

Ceiling[ CoefficientList[ Series[ Exp[ -1 + (Exp[ z ] - 1)/2 ]Sum[ Exp[ s(s - 1)z/2 ]/s!, {s, 0, 21} ], {z, 0, 9} ], z ] Table[ n!, {n, 0, 9} ] ] (* Mitch Harris, May 01 2004 *)
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[Select[mps[Ceiling[Range[1/2,n,1/2]]],And@@UnsameQ@@@#&]],{n,5}] (* Gus Wiseman, Jul 18 2018 *)

E.g.f.: exp(-3/2+exp(x)/2) * Sum_{n>=0} exp(binomial(n, 2)*x)/n! [Comtet]. - Vladeta Jovovic, Apr 27 2004
E.g.f. (an equivalent version in Maple format): G:=exp(-1+(exp(z)-1)/2)*sum(exp(s*(s-1)*z/2)/s!, s=0..infinity);
E.g.f.: exp((exp(x)-1)/2)*Sum_{n>=0} A020556(n)*(x/2)^n/n!. - Vladeta Jovovic, May 02 2004
Stirling_2 transform of A014500.
The e.g.f.'s of A020554 (S(x)) and A014500 (U(x)) are related by S(x) = U(e^x-1).

A219585 Number A(n,k) of k-partite partitions of {n}^k into distinct k-tuples; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 5, 5, 2, 1, 1, 15, 40, 17, 2, 1, 1, 52, 457, 364, 46, 3, 1, 1, 203, 6995, 14595, 2897, 123, 4, 1, 1, 877, 136771, 937776, 407287, 21369, 323, 5, 1, 1, 4140, 3299218, 88507276, 107652681, 10200931, 148257, 809, 6, 1

Offset: 0

Alois P. Heinz, Nov 23 2012

A(n,k) is the number of factorizations of m^n into distinct factors where m is a product of k distinct primes. A(2,2) = 5: (2*3)^2 = 36 has 5 factorizations into distinct factors: 36, 3*12, 4*9, 2*18, 2*3*6.

			A(1,3) = 5: [(1,1,1)], [(1,1,0),(0,0,1)], [(1,0,1),(0,1,0)], [(1,0,0),(0,1,0),(0,0,1)], [(0,1,1),(1,0,0)].
A(3,2) = 17: [(3,3)], [(3,0),(0,3)], [(3,2),(0,1)], [(2,3),(1,0)], [(3,1),(0,2)], [(2,2),(1,1)], [(1,3),(2,0)], [(2,1),(1,2)], [(2,1),(1,1),(0,1)], [(3,0),(0,2),(0,1)], [(2,2),(1,0),(0,1)], [(2,1),(0,2),(1,0)], [(1,2),(2,0),(0,1)], [(1,2),(1,1),(1,0)], [(0,3),(2,0),(1,0)], [(2,0),(1,1),(0,2)], [(2,0),(0,2),(1,0),(0,1)].
Square array A(n,k) begins:
  1,  1,   1,      1,          1,            1,         1, ...
  1,  1,   2,      5,         15,           52,       203, ...
  1,  1,   5,     40,        457,         6995,    136771, ...
  1,  2,  17,    364,      14595,       937776,  88507276, ...
  1,  2,  46,   2897,     407287,    107652681,  ...
  1,  3, 123,  21369,   10200931,  10781201973,  ...
  1,  4, 323, 148257,  233051939,  ...
  1,  5, 809, 970246, 4909342744,  ...

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

Columns k=0..5 give: A000012, A000009, A219554, A219560, A219561, A219565.
Rows n=0..3 give: A000012, A000110, A094574, A319591.
Cf. A188445, A219727 (partitions of {n}^k into k-tuples), A318286.

f[n_, k_] := f[n, k] = 1/2 Product[Sum[O[x[j]]^(n+1), {j, 1, k}]+1+ Product[x[j]^i[j], {j, 1, k}], Evaluate[Sequence @@ Table[{i[j], 0, n}, {j, 1, k}]]];
a[0, ] = a[, 0] = 1; a[n_, k_] := SeriesCoefficient[f[n, k], Sequence @@ Table[{x[j], 0, n}, {j, 1, k}]];
Table[Print[a[n-k, k]]; a[n-k, k], {n, 0, 9}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Dec 11 2013, updated Sep 16 2019 *)

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]]++); EulerT(v)[n]^k/prod(i=1, #v, i^v[i]*v[i]!)}
T(n, k)={my(m=n*k+1, q=Vec(exp(intformal(O(x^m) - x^n/(1-x)))/(1+x))); if(n==0, 1, (-1)^m*sum(j=0, m, my(s=0); forpart(p=j, s+=(-1)^#p*D(p, n, k), [1, n]); s*q[#q-j])/2)} \\ Andrew Howroyd, Dec 16 2018

A(n,k) = [(Product_{j=1..k} x_j)^n] 1/2 * Product_{i_1,...,i_k>=0} (1+Product_{j=1..k} x_j^i_j).

A094577 Central Peirce numbers. Number of set partitions of {1,2,..,2n+1} in which n+1 is the smallest of its block.

Original entry on oeis.org

1, 3, 27, 409, 9089, 272947, 10515147, 501178937, 28773452321, 1949230218691, 153281759047387, 13806215066685433, 1408621900803060705, 161278353358629226675, 20555596673435403499083, 2896227959507289559616217, 448371253145121338801335489

Offset: 0

Vladeta Jovovic, May 12 2004

nonn

Let P(n,k) be the number of set partitions of {1,2,..,n} in which k is the smallest of its block. These numbers were introduced by C. S. Peirce (see reference, page 48). If this triangle is displayed as in A123346 (or A011971) then a(n) = A011971(2n, n) are the central Pierce numbers. - Peter Luschny, Jan 18 2011

Named after the American philosopher, logician, mathematician and scientist Charles Sanders Peirce (1839-1914). - Amiram Eldar, Jun 11 2021

			n = 1, S = {1, 2, 3}. k = n+1 = 2. Thus a(1) = card { 13|2, 1|23, 1|2|3 } = 3. - _Peter Luschny_, Jan 18 2011

Donald E. Knuth, The Art of Computer Programming, Vol. 4, Section 7.2.1.5.

Alois P. Heinz, Table of n, a(n) for n = 0..288
Charles Sanders Peirce, On the Algebra of Logic, American Journal of Mathematics, Vol. 3 (1880), pp. 15-57.

Cf. A094574, A020556, A216078.

Main diagonal of array in A011971.

seq(add(binomial(n, k)*(bell(n+k)), k=0..n), n=0..14); # Zerinvary Lajos, Dec 01 2006
# The objective of this implementation is efficiency.
# m -> [a(0), a(1), ..., a(m-1)] for m > 0.
A094577_list := proc(m)
   local A, R, M, n, k, j;
   M := m+m-1; A := array(1..M);
   j := 1; R := 1; A[1] := 1;
   for n from 2 to M do
      A[n] := A[1];
      for k from n by -1 to 2 do
         A[k-1] := A[k-1] + A[k]
      od;
      if is(n,odd) then
         j := j+1; R := R,A[j] fi
   od;
[R] end:
A094577_list(100); # example call - Peter Luschny, Jan 17 2011

f[n_] := Sum[Binomial[n, k]*BellB[2 n - k], {k, 0, n}]; Array[f, 15, 0]

# requires python 3.2 or higher. Otherwise use def'n of accumulate in python docs.
from itertools import accumulate
A094577_list, blist, b = [1], [1], 1
for n in range(2,502):
    blist = list(accumulate([b]+blist))
    b = blist[-1]
    blist = list(accumulate([b]+blist))
    b = blist[-1]
    A094577_list.append(blist[-n])
# Chai Wah Wu, Sep 02 2014, updated Chai Wah Wu, Sep 20 2014

a(n) = Sum_{k=0..n} binomial(n,k)*Bell(2*n-k).
a(n) = Sum_{k=0..n} (-1)^k*binomial(n, k)*Bell(2*n-k+1).
a(n) = exp(-1)*Sum_{k>=0} (k(k+1))^n/k!. - Benoit Cloitre, Dec 30 2005
a(n) = Sum_{k=0..n} binomial(n,k)*Bell(n+k). - Vaclav Kotesovec, Jul 29 2022

cp's OEIS Frontend

A007717 Number of symmetric polynomial functions of degree n of a symmetric matrix (of indefinitely large size) under joint row and column permutations. Also number of multigraphs with n edges (allowing loops) on an infinite set of nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

A050535 Number of loopless multigraphs on infinite set of nodes with n edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

A278990 Number of loopless linear chord diagrams with n chords.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A114938 Number of permutations of the multiset {1,1,2,2,...,n,n} with no two consecutive terms equal.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A316974 Number of non-isomorphic strict multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A346517 Number A(n,k) of partitions of the (n+k)-multiset {1,2,...,n,1,2,...,k} into distinct multisets; square array A(n,k), n>=0, k>=0, read by antidiagonals.