A094574 -id:A094574 - cp's OEIS frontend

A053419 Number of graphs with loops (symmetric relations) with n edges.

1, 2, 5, 14, 38, 107, 318, 972, 3111, 10410, 36371, 132656, 504636, 1998361, 8224448, 35112342, 155211522, 709123787, 3342875421, 16234342515, 81102926848, 416244824068, 2192018373522, 11831511359378, 65387590986455, 369661585869273, 2135966349269550, 12604385044890628

Offset: 0

Vladeta Jovovic, Jan 10 2000

nonn

In a multiset partition, two vertices are equivalent if in every block the multiplicity of the first is equal to the multiplicity of the second. a(n) is the number of non-isomorphic multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n} with no equivalent vertices. For example, non-isomorphic representatives of the a(2) = 5 multiset partitions are (1)(122), (11)(22), (1)(1)(22), (1)(2)(12), (1)(1)(2)(2). - Gus Wiseman, Jul 18 2018

a(n) is the number of unlabeled simple graphs with n edges rooted at one vertex. - Andrew Howroyd, Nov 22 2020

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

Cf. A000664, A000666, A007716, A007717, A020555, A050535, A053419, A094574, A191970 (multisets), A316974, A339063.

seq[n_] := Module[{A = O[x]^n}, G[2n, x+A, {1}] // CoefficientList[#, x]&]; (* Jean-François Alcover, Dec 03 2020, using Andrew Howroyd's code for g.f. G in A339063 *)

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

Euler transform of A191970. - Andrew Howroyd, Oct 22 2019

a(16)-a(24) from Max Alekseyev, Jan 22 2010

Terms a(25) and beyond from Andrew Howroyd, Oct 22 2019

A322770 Array read by upwards antidiagonals: T(m,n) = number of set partitions into distinct parts of the multiset consisting of one copy each of x_1, x_2, ..., x_m, and two copies each of y_1, y_2, ..., y_n, for m >= 0, n >= 0.

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 5, 9, 18, 40, 15, 31, 70, 172, 457, 52, 120, 299, 801, 2295, 6995, 203, 514, 1393, 4025, 12347, 40043, 136771, 877, 2407, 7023, 21709, 70843, 243235, 875936, 3299218, 4140, 12205, 38043, 124997, 431636, 1562071, 5908978, 23308546, 95668354

Offset: 0

N. J. A. Sloane, Dec 30 2018

			The array begins:
     1,    1,     5,     40,      457,      6995,      136771, ...
     1,    3,    18,    172,     2295,     40043,      875936, ...
     2,    9,    70,    801,    12347,    243235,     5908978, ...
     5,   31,   299,   4025,    70843,   1562071,    41862462, ...
    15,  120,  1393,  21709,   431636,  10569612,   310606617, ...
    52,  514,  7023, 124997,  2781372,  75114998,  2407527172, ...
   203, 2407, 38043, 764538, 18885177, 559057663, 19449364539, ...
   ...

D. E. Knuth, The Art of Computer Programming, Vol. 4A, Table A-1, page 778. (Background information.)

Alois P. Heinz, Antidiagonals n = 0..140, flattened
D. E. Knuth, Partitioning a multiset into submultisets, Email to N. J. A. Sloane, Dec 29 2018.

Rows include A094574, A322771, A322772.
Columns include A000110, A087648, A322773, A322774.
Main diagonal is A322775.

B := n -> combinat[bell](n):
Q := proc(m,n) local k; global B; option remember;
if n = 0 then B(m)  else
(1/2)*( Q(m+2,n-1) + Q(m+1,n-1) - add( binomial(n-1,k)*Q(m,k), k=0..n-1) ); fi; end;  # Q(m,n) (which is Knuth's notation) is T(m,n)

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}])];
Table[Q[m-n, n], {m, 0, 8}, {n, 0, m}] // Flatten (* Jean-François Alcover, Jan 02 2019, from Maple *)

Knuth gives a recurrence using the Bell numbers A000110 (see Maple program).

A316972 Number of connected multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n}.

Original entry on oeis.org

1, 2, 5, 28, 277, 3985, 76117, 1833187, 53756682, 1871041538, 75809298105, 3521419837339, 185235838688677, 10923147890901151, 715989783027216302, 51793686238309903860, 4109310551278549543317, 355667047514571431358297, 33422937748872646130124797

Offset: 0

Gus Wiseman, Jul 17 2018

nonn

Note that all connected multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n} are strict except for (123...n)(123...n).

			The a(2) = 5 connected multiset partitions of {1, 1, 2, 2} are (1122), (1)(122), (2)(112), (12)(12), (1)(2)(12). The multiset partitions (11)(22), (1)(1)(22), (2)(2)(11), (1)(1)(2)(2) are not connected.

Cf. A001055, A007716, A007717, A007719, A020555, A045778, A061742, A094574, A162247, A316974.

nn=10;
ser=Exp[-3/2+Exp[x]/2]*Sum[Exp[Binomial[n+1,2]*x]/n!,{n,0,3*nn}];
Round/@(CoefficientList[Series[1+Log[ser],{x,0,nn}],x]*Array[Factorial,nn+1,0]) (* based on Jean-François Alcover after Vladeta Jovovic *)
(*second program *)
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
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]]]];
Length/@Table[Select[mps[Ceiling[Range[1/2,n,1/2]]],Length[csm[#]]==1&],{n,4}]

Logarithmic transform of A020555.

A178165 Number of unordered collections of distinct nonempty subsets of an n-element set where each element appears in at most 2 subsets.

Original entry on oeis.org

1, 2, 8, 59, 652, 9736, 186478, 4421018, 126317785, 4260664251, 166884941780, 7489637988545, 380861594219460, 21739310882945458, 1381634777325000263, 97089956842985393297, 7497783115765911443879, 632884743974716421132084

Offset: 0

Daniel E. Loeb, Dec 16 2010

nonn

If each element must appear in exactly 1 subset, then we get the Bell numbers A000110.

If each element must appear in exactly 2 subsets, then we get A002718.

Alois P. Heinz, Table of n, a(n) for n = 0..300

Row n=2 of A330964.

Cf. A094574, A000110, A002718, A178171, A178173.

terms = m = 30;
a094577[n_] := Sum[Binomial[n, k]*BellB[2n-k], {k, 0, n}];
egf = Exp[(1 - Exp[x])/2]*Sum[a094577[n]*(x/2)^n/n!, {n, 0, m}] + O[x]^m;
A094574 = CoefficientList[egf + O[x]^m, x]*Range[0, m-1]!;
a[n_] := Sum[Binomial[n, k]*A094574[[k+1]], {k, 0, n}];
Table[a[n], {n, 0, m-1}] (* Jean-François Alcover, May 24 2019 *)

from numpy import array
def toBinary(n, k):
    ans=[]
    for i in range(k):
        ans.insert(0, n%2)
        n=n>>1
    return array(ans)
def powerSet(k): return [toBinary(n,k) for n in range(1,2**k)]
def courcelle(maxUses, remainingSets, exact=False):
    if exact and not all(maxUses<=sum(remainingSets)): ans=0
    elif len(remainingSets)==0: ans=1
    else:
        set0=remainingSets[0]
        if all(set0<=maxUses): ans=courcelle(maxUses-set0,remainingSets[1:],exact=exact)
        else: ans=0
        ans+=courcelle(maxUses,remainingSets[1:],exact=exact)
    return ans
for i in range(10):
    print(i, courcelle(array([2]*i),powerSet(i),exact=False))

Binomial transform of A094574: a(n) = Sum_{k=0..n} C(n,k)*A094574(k).

Edited and corrected by Max Alekseyev, Dec 19 2010

A331316 Number of nonnegative integer matrices with n distinct columns and any number of distinct nonzero rows with each column sum being 2 and rows in decreasing lexicographic order.

Original entry on oeis.org

1, 1, 4, 27, 266, 3599, 62941, 1372117, 36248765, 1135864306, 41501271477, 1743624004536, 83268125043937, 4476101995389591, 268589319338401864, 17860954789864760357, 1307982591075162739660, 104895999816356419875935, 9166919404389461922512723

Offset: 0

Andrew Howroyd, Jan 13 2020

nonn

The condition that the rows be in decreasing order is equivalent to considering nonequivalent matrices with distinct rows up to permutation of rows.

			The a(2) = 4 matrices are:
   [2 1]   [2 0]   [1 2]   [1 1]
   [0 1]   [0 2]   [1 0]   [1 0]
                           [0 1]

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

Row n=2 of A331160.

Cf. A094574.

a(n) = Sum_{k=0..n} Stirling1(n,k)*A094574(k).

A094573 Triangle T(n,k) giving number of (<=2)-covers of an n-set with k blocks.

Original entry on oeis.org

1, 1, 1, 3, 1, 1, 12, 20, 7, 1, 39, 169, 186, 59, 3, 1, 120, 1160, 2755, 2243, 661, 55, 1, 363, 7381, 33270, 52060, 33604, 9167, 910, 15, 1, 1092, 45500, 367087, 988750, 1126874, 601262, 151726, 16401, 525, 1, 3279, 276529, 3873786, 17005149

Offset: 0

Goran Kilibarda, Vladeta Jovovic, May 12 2004

Cover of a set is (<=2)-cover if every element of the set is covered with at most two blocks of the cover.

			Triangle T(n,k) begins:
  1;
  1;
  1,   3,    1;
  1,  12,   20,    7;
  1,  39,  169,  186,   59,   3;
  1, 120, 1160, 2755, 2243, 661, 55;
  ...

Row sums give A094574.

Cf. A059443, A060052.

rows = 9; m = rows + 2;
egf = Exp[-x - (x^2/2)*(Exp[y]-1)]*Sum[Exp[y*Binomial[n+1, 2]]*(x^n/n!), {n, 0, m}];
cc = CoefficientList[# + O[x]^m, x]& /@ CoefficientList[egf + O[y]^m, y];
(Range[0, Length[cc]-1]! * cc)[[1 ;; rows]] /. {0, a__} :> {a} // Flatten (* Jean-François Alcover, May 13 2019 *)

E.g.f.: exp(-x-x^2/2*(exp(y)-1))*(Sum_{n>=0} exp(y*binomial(n+1, 2))*x^n/n!).

A316892 Number of non-isomorphic strict multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n} with no equivalent vertices.

Original entry on oeis.org

1, 1, 3, 9, 24, 69, 211, 654

Offset: 0

Gus Wiseman, Jul 18 2018

Also the number of unlabeled graphs with n edges, allowing loops, 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) = 3 multigraphs are {(1,2),(1,3)}, {(1,1),(1,2)}, {(1,1),(2,2)}.

			Non-isomorphic representatives of the a(3) = 9 strict multiset partitions:
  (112)(233)
  (1)(2)(1233)
  (1)(12)(233)
  (2)(11)(233)
  (11)(22)(33)
  (12)(13)(23)
  (1)(2)(3)(123)
  (1)(2)(12)(33)
  (1)(2)(13)(23)

Cf. A007716, A007717, A020555, A050535, A053419, A094574, A316974.

a(6)-a(7) from Andrew Howroyd, Feb 07 2020

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

A053419 Number of graphs with loops (symmetric relations) with n edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A322770 Array read by upwards antidiagonals: T(m,n) = number of set partitions into distinct parts of the multiset consisting of one copy each of x_1, x_2, ..., x_m, and two copies each of y_1, y_2, ..., y_n, for m >= 0, n >= 0.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A316972 Number of connected multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A178165 Number of unordered collections of distinct nonempty subsets of an n-element set where each element appears in at most 2 subsets.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A331316 Number of nonnegative integer matrices with n distinct columns and any number of distinct nonzero rows with each column sum being 2 and rows in decreasing lexicographic order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A094573 Triangle T(n,k) giving number of (<=2)-covers of an n-set with k blocks.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A316892 Number of non-isomorphic strict multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n} with no equivalent vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples