A316972 -id:A316972 - 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

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

A007719 Number of independent polynomial invariants of symmetric matrix of order n.

Original entry on oeis.org

1, 2, 4, 11, 30, 95, 328, 1211, 4779, 19902, 86682, 393072, 1847264, 8965027, 44814034, 230232789, 1213534723, 6552995689, 36207886517, 204499421849, 1179555353219, 6942908667578, 41673453738272, 254918441681030, 1588256152307002, 10073760672179505

Offset: 0

Colin Mallows

Also, number of connected multigraphs with n edges (allowing loops) and any number of nodes.

Also the number of non-isomorphic connected multiset partitions 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) = 11 connected multiset partitions of {1, 1, 2, 2, 3, 3}:
  (112233),
  (1)(12233), (12)(1233), (112)(233), (123)(123),
  (1)(2)(1233), (1)(12)(233), (1)(23)(123), (12)(13)(23),
  (1)(2)(3)(123), (1)(2)(13)(23).
(End)

Andrew Howroyd, Table of n, a(n) for n = 0..50
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 [math.CO] (2017) Table 63.

Row sums of A322115.

Cf. A002905, A007716, A007717, A007719, A020555, A050535, A053419, A076864, A191970, A316972, A316974.

mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++,
  c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {};
  For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
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!];
A007717 = Table[Print[n]; RowSumMats[n, 2 n, 2], {n, 0, 20}];
Join[{1}, EULERi[Rest[A007717]]] (* Jean-François Alcover, Oct 29 2018, using Andrew Howroyd's code for A007717 *)

Inverse Euler transform of A007717.

a(0)=1 added by Alberto Tacchella, Jun 20 2011

a(7)-a(25) from Franklin T. Adams-Watters, Jun 21 2011

A316977 Number of series-reduced rooted trees whose leaves are {1, 1, 2, 2, 3, 3, ..., n, n}.

Original entry on oeis.org

1, 12, 575, 66080, 13830706, 4566898564, 2181901435364, 1422774451251512, 1213875872220833664, 1312273759143855989808, 1752860078230602866012288, 2834766624822130489716563008, 5458358420687156358967526721408, 12339106957086349462329140342122112

Offset: 1

Gus Wiseman, Jul 17 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches.

			The a(2) = 12 trees are (1(1(22))), (1(2(12))), (1(122)), (2(1(12))), (2(2(11))), (2(112)), ((11)(22)), ((12)(12)), (11(22)), (12(12)), (22(11)), (1122).

Cf. A000081, A000669, A007717, A020555, A050535, A094574, A292504, A316655, A316972, A316974.

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]]]];
gro[m_]:=If[Length[m]==1,m,Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])]];
Table[Length[gro[Ceiling[Range[1/2,n,1/2]]]],{n,4}]

\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(2*n), vars=vector(2*n-2,i,sv(2+i))); v[1]=sv(1); for(n=2, #v, v[n] = substvec(polcoef( sExp(x*Ser(v[1..n])), n ), vars[1..n-2], vector(n-2))); sCartProd(x*Ser(v), 1/(1-x^2*symGroupCycleIndex(2)) + O(x*x^(2*n)))}
seq(n)={my(p=substvec(cycleIndexSeries(n), [sv(1), sv(2)], [1,1])); vector(n, n, polcoef(p,2*n))} \\ Andrew Howroyd, Jan 02 2021

a(n) = A292505(A061742(n)). - Andrew Howroyd, Nov 19 2018

Terms a(6) and beyond from Andrew Howroyd, Jan 02 2021

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

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

A007719 Number of independent polynomial invariants of symmetric matrix of order n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A316977 Number of series-reduced rooted trees whose leaves are {1, 1, 2, 2, 3, 3, ..., n, n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions