A099947 -id:A099947 - cp's OEIS frontend

A326349 Number of non-nesting, topologically connected simple graphs covering {1..n}.

1, 0, 1, 0, 1, 11, 95, 797

Offset: 0

Gus Wiseman, Jun 30 2019

Covering means there are no isolated vertices. Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d. A graph with positive integer vertices is topologically connected if the graph whose vertices are the edges and whose edges are crossing pairs of edges is connected.

			The a(5) = 11 edge-sets:
  {13,14,25}
  {13,24,25}
  {13,24,35}
  {14,24,35}
  {14,25,35}
  {13,14,24,25}
  {13,14,24,35}
  {13,14,25,35}
  {13,24,25,35}
  {14,24,25,35}
  {13,14,24,25,35}

Gus Wiseman, The a(6) = 95 non-nesting, topologically connected, covering simple graphs.

The binomial transform is the non-covering case A326293.
Topologically connected, covering simple graphs are A324327.
Non-crossing, covering simple graphs are A324169.
Cf. A000108, A000699, A006125, A054726, A099947, A117662.
Cf. A324323, A324328, A326329, A326330, A326339, A326341.

croXQ[eds_]:=MatchQ[eds,{_,{x_,y_},_,{z_,t_},_}/;x_,{x_,y_},_,{z_,t_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&!nesXQ[#]&&Length[csm[Union[Subsets[#,{1}],Select[Subsets[#,{2}],croXQ]]]]<=1&]],{n,0,5}]

A324325 Number of non-crossing multiset partitions of a multiset whose multiplicities are the prime indices of n.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 5, 5, 9, 7, 7, 11, 11, 12, 16, 14, 15, 26, 22, 21, 29, 19, 30, 33, 31, 30, 66, 38, 42, 52, 56, 42, 47, 45, 57, 82, 77, 67, 77, 67, 101, 98, 135, 64, 137, 97, 176, 104, 109, 109, 118, 105, 231, 213, 97, 127, 181, 139, 297, 173, 385, 195, 269

Offset: 1

Gus Wiseman, Feb 22 2019

nonn

This multiset (row n of A305936) is generally not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.

A multiset partition is crossing if it contains two blocks of the form {{...x...y...},{...z...t...}} where x < z < y < t or z < x < t < y.

			The a(16) = 14 non-crossing multiset partitions of the multiset {1,2,3,4}:
  {{1,2,3,4}}
  {{1},{2,3,4}}
  {{2},{1,3,4}}
  {{3},{1,2,4}}
  {{4},{1,2,3}}
  {{1,2},{3,4}}
  {{1,4},{2,3}}
  {{1},{2},{3,4}}
  {{1},{3},{2,4}}
  {{1},{4},{2,3}}
  {{2},{3},{1,4}}
  {{2},{4},{1,3}}
  {{3},{1,2},{4}}
  {{1},{2},{3},{4}}
Missing from this list is {{1,3},{2,4}}.

Cf. A000108, A001055, A001970, A016098, A054726, A099947, A181821, A305936, A306438, A318284, A318285.

Cf. A324167, A324168, A324169, A324170, A324171, A324324, A324326.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
nonXQ[stn_]:=!MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

a(n) + A324326(n) = A318284(n).

A224786 G.f. satisfies: A(x) = Sum_{n>=0} x^n / (A(x) - n*x)^n.

Original entry on oeis.org

1, 1, 1, 2, 6, 23, 110, 607, 3742, 25324, 185566, 1457998, 12195992, 108010446, 1008224881, 9883048933, 101418491070, 1086613660608, 12126900841444, 140682966122152, 1693340044490513, 21111988598271746, 272228110567491910, 3625334790162237116

Offset: 0

Paul D. Hanna, Apr 17 2013

nonn

			G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 6*x^4 + 23*x^5 + 110*x^6 + 607*x^7 +...
where, by definition,
A(x) = 1 + x/(A(x) - x) + x^2/(A(x) - 2*x)^2 + x^3/(A(x) - 3*x)^3 + x^4/(A(x) - 4*x)^4 + x^5/(A(x) - 5*x)^5 +....
Also, the g.f. satisfies:
A(x) = 1 + x/A(x) + 2*x^2/A(x)^2 + 6*x^3/A(x)^3 + 23*x^4/A(x)^4 + 104*x^5/A(x)^5 + 537*x^6/A(x)^6 +...+ A080108(n)*x^n/A(x)^n +...

Cf. A211207, A099947, A080108.

{a(n)=local(A=1+x); for(i=1, n, A=sum(m=0, n, x^m/(A-m*x+x*O(x^n))^m)); polcoeff(A, n)}
for(n=0, 30, print1(a(n), ", "))

G.f. satisfies: A(x) = 1 + G(x/A(x)) where G(x) is the g.f. of A080108, where A080108(n) = Sum_{k=1..n} k^(n-k)*C(n-1,k-1).

A306551 Number of non-double-crossing set partitions of {1,...,n}.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 202, 863, 3999, 19880, 105134, 587479, 3449505

Offset: 0

Gus Wiseman, Feb 23 2019

Two blocks of a set partitions double-cross each other if they are of the form {{...a...b...c...},{...x...y...z...}} for some a < x < b < y < c < z or x < a < y < b < z < c.

			Most small set partitions are not double-crossing. The smallest that is double-crossing is {{1,3,5},{2,4,6}}.

Kenneth J. Dykema, Generating functions for purely crossing partitions, arXiv:1602.03469 [math.CO], 2016.

Cf. A000108, A000110, A001263, A002061, A005493, A007297, A016098, A054726, A099947, A324166, A324167, A324172, A324324.

nonXXQ[stn_]:=!MatchQ[stn,{_,{_,a_,_,b_,_,c_,_},_,{_,x_,_,y_,_,z_,_},_}/;a_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],nonXXQ]],{n,0,8}]

A306558 Number of double-crossing set partitions of {1,...,n}.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 14, 141, 1267, 10841, 91091, 764092

Offset: 0

Gus Wiseman, Feb 23 2019

Two blocks of a set partitions double-cross each other if they are of the form {{...a...b...c...},{...x...y...z...}} for some a < x < b < y < c < z or x < a < y < b < z < c.

			The a(7) = 14 double-crossing set partitions:
  {{1,3,5},{2,4,6,7}}
  {{1,3,6},{2,4,5,7}}
  {{1,4,6},{2,3,5,7}}
  {{1,2,4,6},{3,5,7}}
  {{1,3,4,6},{2,5,7}}
  {{1,3,5,6},{2,4,7}}
  {{1,3,5,7},{2,4,6}}
  {{1},{2,4,6},{3,5,7}}
  {{1,3,5},{2,4,6},{7}}
  {{1,3,5},{2,4,7},{6}}
  {{1,3,6},{2,4,7},{5}}
  {{1,3,6},{2,5,7},{4}}
  {{1,4,6},{2},{3,5,7}}
  {{1,4,6},{2,5,7},{3}}

Kenneth J. Dykema, Generating functions for purely crossing partitions, arXiv:1602.03469 [math.CO], 2016.

Cf. A000108, A000110, A001263, A002061, A005493, A007297, A016098 (crossing set partitions), A054726, A099947, A324166, A324172, A324324.

croXXQ[stn_]:=MatchQ[stn,{_,{_,a_,_,b_,_,c_,_},_,{_,x_,_,y_,_,z_,_},_}/;a_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],croXXQ]],{n,0,8}]

cp's OEIS Frontend

A326349 Number of non-nesting, topologically connected simple graphs covering {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A324325 Number of non-crossing multiset partitions of a multiset whose multiplicities are the prime indices of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A224786 G.f. satisfies: A(x) = Sum_{n>=0} x^n / (A(x) - n*x)^n.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A306551 Number of non-double-crossing set partitions of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A306558 Number of double-crossing set partitions of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica