A293510 -id:A293510 - cp's OEIS frontend

A317635 Number of connected vertex sets of clutters (connected antichains) spanning n vertices.

1, 0, 1, 14, 486, 71428

Offset: 0

Gus Wiseman, Aug 02 2018

A connected vertex set in a clutter is any union of a connected subset of the edges.

			There are four connected vertex sets of {{1,2},{1,3},{2,3}}, namely {1,2,3}, {1,2}, {1,3}, {2,3}; there are three connected vertex sets of {{1,2},{1,3}}, {{1,2},{2,3}}, and {{1,3},{2,3}} each; and there is one connected vertex set of {{1,2,3}}. So we have a total of a(3) = 4 + 3 * 3 + 1 = 14 connected vertex sets.

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

Cf. A001187, A006126, A030019, A048143, A134954, A275307, A286520, A293510, A304717, A317631, A317632, A317634.

nn=5;
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]]],multijoin@@s[[c[[1]]]]]]]]];
clutQ[eds_]:=And[UnsameQ@@eds,!Apply[Or,Outer[#1=!=#2&&Complement[#1,#2]=={}&,eds,eds,1],{0,1}],Length[csm[eds]]==1];
stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
swell[c_]:=Union@@FixedPointList[Union[ReplaceList[#1,{_,a:{_,x_,_},_,b:{_,x_,_},_}:>Union[a,b]]]&,c]
Table[Sum[Length[swell[c]],{c,Select[stableSets[Select[Subsets[Range[n]],Length[#]>1&],Complement[#1,#2]=={}&],And[Union@@#==Range[n],clutQ[#]]&]}],{n,nn}]

A317674 Regular triangle where T(n,k) is the number of antichains covering n vertices with k connected components.

Original entry on oeis.org

1, 1, 1, 5, 3, 1, 84, 23, 6, 1, 6348, 470, 65, 10, 1, 7743728, 39598, 1575, 145, 15, 1, 2414572893530, 54354104, 144403, 4095, 280, 21, 1, 56130437190053299918162, 19316801997024, 218033088, 402073, 9100, 490, 28, 1

Offset: 1

Gus Wiseman, Aug 03 2018

			Triangle begins:
        1
        1       1
        5       3       1
       84      23       6       1
     6348     470      65      10       1
  7743728   39598    1575     145      15       1

Gus Wiseman, Sequences enumerating clutters, antichains, hypertrees, and hyperforests, organized by labeling, spanning, and allowance of singletons.

First column is A048143. Row sums are A006126.
Cf. A000272, A001187, A013922, A030019, A134954, A143543, A275307, A293510.
Cf. A317634, A317635, A317671, A317672, A317677.

blg={1,1,5,84,6348,7743728,2414572893530,56130437190053299918162} (*A048143*);
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Sum[Product[blg[[Length[s]]],{s,spn}],{spn,Select[sps[Range[n]],Length[#]==k&]}],{n,Length[blg]},{k,n}]

A323817 Number of connected set-systems covering n vertices with no singletons.

Original entry on oeis.org

1, 0, 1, 12, 1990, 67098648, 144115187673201808, 1329227995784915871895000743748659792, 226156424291633194186662080095093570015284114833799899656335137245499581360

Offset: 0

Gus Wiseman, Jan 30 2019

nonn

			The a(3) = 12 set-systems:
  {{1, 2, 3}}
  {{1, 2}, {1, 3}}
  {{1, 2}, {2, 3}}
  {{1, 3}, {2, 3}}
  {{1, 2}, {1, 2, 3}}
  {{1, 3}, {1, 2, 3}}
  {{2, 3}, {1, 2, 3}}
  {{1, 2}, {1, 3}, {2, 3}}
  {{1, 2}, {1, 3}, {1, 2, 3}}
  {{1, 2}, {2, 3}, {1, 2, 3}}
  {{1, 3}, {2, 3}, {1, 2, 3}}
  {{1, 2}, {1, 3}, {2, 3},{1, 2, 3}}
The A323816(4) - a(4) = 3 disconnected set-systems covering n vertices with no singletons:
  {{1, 2}, {3, 4}}
  {{1, 3}, {2, 4}}
  {{1, 4}, {2, 3}}

G. C. Greubel, Table of n, a(n) for n = 0..11

Cf. A001187, A016031, A048143, A092918, A293510, A317795, A323816 (not necessarily connected), A323818 (with singletons), A323819, A323820 (unlabeled case).

m:=10;
A323816:= func< n | (&+[(-1)^(n-j)*Binomial(n,j)*2^(2^j -j-1): j in [0..n]]) >;
f:= func< x | 1 + Log((&+[A323816(j)*x^j/Factorial(j): j in [0..m+2]])) >;
R:=PowerSeriesRing(Rationals(), m+1);
Coefficients(R!(Laplace( f(x) ))); // G. C. Greubel, Oct 05 2022

b:= n-> add(2^(2^(n-j)-n+j-1)*binomial(n, j)*(-1)^j, j=0..n):
a:= proc(n) option remember; b(n)-`if`(n=0, 0, add(
       k*binomial(n, k)*b(n-k)*a(k), k=1..n-1)/n)
    end:
seq(a(n), n=0..8);  # Alois P. Heinz, Jan 30 2019

nn=10;
ser=Sum[Sum[(-1)^(n-k)*Binomial[n,k]*2^(2^k-k-1),{k,0,n}]*x^n/n!,{n,0,nn}];
Table[SeriesCoefficient[1+Log[ser],{x,0,n}]*n!,{n,0,nn}]

m=10
def A323816(n): return sum((-1)^j*binomial(n,j)*2^(2^(n-j) -n+j-1) for j in range(n+1))
def A323817_list(prec):
    P. = PowerSeriesRing(QQ, prec)
    return P( 1 + log(sum(A323816(j)*x^j/factorial(j) for j in range(m+2))) ).egf_to_ogf().list()
A323817_list(m) # G. C. Greubel, Oct 05 2022

Logarithmic transform of A323816.

A317677 Fixed point of a shifted hypertree transform.

Original entry on oeis.org

1, 1, 4, 32, 402, 7038, 160114, 4522578, 153640590, 6132546770, 282517271694, 14812447505646, 873934551644074, 57486823088667270, 4183353479821220130, 334572221351085006242, 29242220614539638127294, 2779426070382982579163202, 286058737295150226682469518

Offset: 1

Gus Wiseman, Aug 04 2018

The hypertree transform H(a) of a sequence a is given by H(a)(n) = Sum_p n^(k-1) Prod_i a(|p_i|+1), where the sum is over all set partitions U(p_1, ..., p_k) = {1, ..., n-1}.

Alois P. Heinz, Table of n, a(n) for n = 1..305

Cf. A000272, A030019, A048143, A134954, A275307, A293510, A317631, A317632, A317634, A317635, A317671.

b:= proc(n, k) option remember; `if`(n=0, 1/k, add(
      a(j)*b(n-j, k)*binomial(n-1, j-1)*k, j=1..n))
    end:
a:= n-> b(n-1, n):
seq(a(n), n=1..20);  # Alois P. Heinz, Aug 21 2019

numSetPtnsOfType[ptn_]:=Total[ptn]!/Times@@Factorial/@ptn/Times@@Factorial/@Length/@Split[ptn];
a[n_]:=a[n]=Sum[n^(Length[ptn]-1)*numSetPtnsOfType[ptn]*Product[a[s],{s,ptn}],{ptn,IntegerPartitions[n-1]}];
Array[a,20]
(* Second program: *)
b[n_, k_] := b[n, k] = If[n == 0, 1/k, Sum[
     a[j]*b[n - j, k]*Binomial[n - 1, j - 1]*k, {j, 1, n}]];
a[n_] := b[n - 1, n];
Array[a, 20] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)

A326573 Number of connected antichains of subsets of {1..n}, all having different sums.

Original entry on oeis.org

1, 1, 1, 5, 59, 2689, 787382

Offset: 0

Gus Wiseman, Jul 18 2019

An antichain is a finite set of finite sets, none of which is a subset of any other. It is covering if its union is {1..n}. The edge-sums are the sums of vertices in each edge, so for example the edge sums of {{1,3},{2,5},{3,4,5}} are {4,7,12}.

			The a(3) = 5 antichains:
  {{1,2,3}}
  {{1,3},{2,3}}
  {{1,2},{2,3}}
  {{1,2},{1,3}}
  {{1,2},{1,3},{2,3}}
The a(4) = 59 antichains:
  {1234}  {12}{134}   {12}{13}{14}   {12}{13}{14}{24}   {12}{13}{14}{24}{34}
          {12}{234}   {12}{13}{24}   {12}{13}{14}{34}   {12}{13}{23}{24}{34}
          {13}{124}   {12}{13}{34}   {12}{13}{23}{24}
          {13}{234}   {12}{14}{34}   {12}{13}{23}{34}
          {14}{123}   {12}{23}{24}   {12}{13}{24}{34}
          {14}{234}   {12}{23}{34}   {12}{14}{24}{34}
          {23}{124}   {12}{24}{34}   {12}{23}{24}{34}
          {23}{134}   {13}{14}{24}   {13}{14}{24}{34}
          {24}{134}   {13}{23}{24}   {13}{23}{24}{34}
          {34}{123}   {13}{23}{34}   {12}{13}{14}{234}
          {123}{124}  {13}{24}{34}   {12}{23}{24}{134}
          {123}{134}  {14}{24}{34}   {123}{124}{134}{234}
          {123}{234}  {12}{13}{234}
          {124}{134}  {12}{14}{234}
          {124}{234}  {12}{23}{134}
          {134}{234}  {12}{24}{134}
                      {13}{14}{234}
                      {13}{23}{124}
                      {14}{34}{123}
                      {23}{24}{134}
                      {12}{134}{234}
                      {13}{124}{234}
                      {14}{123}{234}
                      {23}{124}{134}
                      {123}{124}{134}
                      {123}{124}{234}
                      {123}{134}{234}
                      {124}{134}{234}

Antichain covers are A006126.
Connected antichains are A048143.
Set partitions with different block-sums are A275780.
MM-numbers of multiset partitions with different part-sums are A326535.
Antichain covers with equal edge-sums are A326566.
The non-connected case is A326572.
Cf. A000372, A293510, A307249, A321469, A323818, A326519, A326565, A326569, A326570, A326571.

A317671 Regular triangle where T(n,k) is the number of labeled connected graphs on n + 1 vertices with k maximal blobs (2-connected components).

Original entry on oeis.org

1, 1, 3, 10, 12, 16, 238, 215, 150, 125, 11368, 7740, 4140, 2160, 1296, 1014888, 509446, 205065, 84035, 36015, 16807, 166537616, 59409952, 17393152, 5393920, 1863680, 688128, 262144, 50680432112, 12321597708, 2516756508, 563570217, 148803480, 45467730

Offset: 1

Gus Wiseman, Aug 03 2018

			Triangle begins:
        1
        1       3
       10      12      16
      238     215     150     125
    11368    7740    4140    2160    1296
  1014888  509446  205065   84035   36015   16807

Row sums are A001187. First column is A013922. Last column is A000272.

Cf. A002218, A030019, A048143, A134954, A275307, A293510, A317631, A317632, A317634, A317635, A317672, A317677.

blg={0,1,1,10,238,11368,1014888,166537616,50680432112,29107809374336} (*A013922*);
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Sum[n^(k-1)*Product[blg[[Length[s]+1]],{s,spn}],{spn,Select[sps[Range[n-1]],Length[#]==k&]}],{n,Length[blg]},{k,n-1}]

A305194 Number of z-forests summing to n. Number of strict integer partitions of n with pairwise indivisible parts and all connected components having clutter density -1.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 2, 3, 4, 5, 4, 6, 7, 7, 9, 11, 12, 13, 15, 17, 20, 23, 25, 27, 32, 35, 40, 45, 49, 54, 58, 67, 78, 82, 95, 99, 111, 123, 135, 150, 164, 177, 194, 214, 236, 260, 282, 309, 330

Offset: 1

Gus Wiseman, May 27 2018

Given a finite set S of positive integers greater than 1, let G(S) be the simple labeled graph with vertex set S and edges between any two vertices that have a common divisor greater than 1. For example, G({6,14,15,35}) is a 4-cycle. A set S is said to be connected if G(S) is a connected graph. The clutter density of S is defined to be Sum_{s in S} (omega(s) - 1) - omega(lcm(S)), where omega = A001221 and lcm is least common multiple. Then a z-forest is a strict integer partition with pairwise indivisible parts greater than 1 such that all connected components have clutter density -1.

			The a(17) = 11 z-forests together with the corresponding multiset systems:
       (17): {{7}}
     (15,2): {{2,3},{1}}
     (14,3): {{1,4},{2}}
     (13,4): {{6},{1,1}}
     (12,5): {{1,1,2},{3}}
     (11,6): {{5},{1,2}}
     (10,7): {{1,3},{4}}
      (9,8): {{2,2},{1,1,1}}
   (10,4,3): {{1,3},{1,1},{2}}
    (7,6,4): {{4},{1,2},{1,1}}
  (7,5,3,2): {{4},{3},{2},{1}}

Roland Bacher, On the enumeration of labelled hypertrees and of labelled bipartite trees, arXiv:1102.2708 [math.CO], 2011.

Cf. A030019, A048143, A134954, A275307, A285572, A293510, A293993, A293994, A303362, A303837, A303838, A304118, A304382, A305078, A305195.

zsm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[Less@@#,GCD@@s[[#]]]>1&]},If[c=={},s,zsm[Union[Append[Delete[s,List/@c[[1]]],LCM@@s[[c[[1]]]]]]]]];
zensity[s_]:=Total[(PrimeNu[#]-1&)/@s]-PrimeNu[LCM@@s];
zreeQ[s_]:=And[Length[s]>=2,zensity[s]==-1];
Table[Length[Select[IntegerPartitions[n],Function[s,UnsameQ@@s&&And@@(Length[#]==1||zreeQ[#]&)/@Table[Select[s,Divisible[m,#]&],{m,zsm[s]}]&&Select[Tuples[s,2],UnsameQ@@#&&Divisible@@#&]=={}]]],{n,50}]

A305195 Number of z-blobs summing to n. Number of connected strict integer partitions of n, with pairwise indivisible parts, that cannot be capped by a z-tree.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 3, 2, 1, 1, 1, 3, 2, 2, 2, 1, 1, 3, 3, 3, 1, 1, 1, 4, 5, 6, 2, 1, 1, 4, 6, 7, 2, 2, 6

Offset: 1

Gus Wiseman, May 27 2018

nonn

Caps of a clutter are defined in the link, and the generalization to "multiclutters," where edges can be multisets, is straightforward.

			The a(30) = 2 z-blobs together with the corresponding multiset systems:
     (30): {{1,2,3}}
  (18,12): {{1,2,2},{1,1,2}}
The a(47) = 3 z-blobs together with the corresponding multiset systems:
        (47): {{15}}
  (21,14,12): {{2,4},{1,4},{1,1,2}}
  (20,15,12): {{1,1,3},{2,3},{1,1,2}}
The a(60) = 5 z-blobs together with the corresponding multiset systems:
           (60): {{1,1,2,3}}
        (42,18): {{1,2,4},{1,2,2}}
        (36,24): {{1,1,2,2},{1,1,1,2}}
     (30,18,12): {{1,2,3},{1,2,2},{1,1,2}}
  (21,15,14,10): {{2,4},{2,3},{1,4},{1,3}}
The a(67) = 7 z-blobs together with the corresponding multiset systems:
           (67): {{19}}
     (45,12,10): {{2,2,3},{1,1,2},{1,3}}
     (42,15,10): {{1,2,4},{2,3},{1,3}}
     (40,15,12): {{1,1,1,3},{2,3},{1,1,2}}
     (33,22,12): {{2,5},{1,5},{1,1,2}}
     (28,21,18): {{1,1,4},{2,4},{1,2,2}}
  (24,18,15,10): {{1,1,1,2},{1,2,2},{2,3},{1,3}}

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

Cf. A030019, A048143, A275307, A285572, A293510, A303362, A303837, A303838, A304118, A304382, A304887, A305028, A305078, A305194.

A323820 Number of non-isomorphic connected set-systems covering n vertices with no singletons.

Original entry on oeis.org

1, 0, 1, 6, 171, 611846, 200253853704319, 263735716028826427334553304608242, 5609038300883759793482640992086670066496449147691597380632107520565546

Offset: 0

Gus Wiseman, Jan 30 2019

nonn

The labeled case is A323817.

			Non-isomorphic representatives of the a(3) = 6 set-systems:
  {{1,2,3}}
  {{1,3},{2,3}}
  {{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3}}
  {{1,3},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}

Cf. A000295, A003465, A016031, A048143, A055621, A293510, A305001, A317795 (not necessarily connected), A323817 (unlabeled case), A323819 (with singletons).

Inverse Euler transform of A317795.

A303674 Number of connected integer partitions of n > 1 whose distinct parts are pairwise indivisible and whose z-density is -1.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 3, 2, 4, 1, 4, 1, 6, 4, 5, 1, 8, 2, 7, 5, 11, 3, 11, 5, 13, 6, 14, 7, 19, 6, 19, 15, 24, 13, 28, 15, 33, 20, 34, 22, 46, 30, 48, 32, 57, 39, 67, 48, 76, 63, 88, 62, 104, 88, 110, 94, 130, 115, 164, 121, 172, 152, 198, 176, 229, 203, 270, 235, 293, 272, 341, 311, 375, 349, 453, 420, 506, 452, 570, 547

Offset: 1

Gus Wiseman, Jun 04 2018

nonn

The z-density of a multiset S is defined to be Sum_{s in S} (omega(s) - 1) - omega(lcm(S)), where omega = A001221 and lcm is least common multiple.

Given a finite multiset S of positive integers greater than 1, let G(S) be the simple labeled graph with vertex set S and edges between any two vertices that have a common divisor greater than 1. For example, G({6,14,15,35}) is a 4-cycle. A multiset S is said to be connected if G(S) is a connected graph.

			The a(18) = 8 integer partitions are (18), (14,4), (10,8), (9,9), (10,4,4), (6,4,4,4), (3,3,3,3,3,3), (2,2,2,2,2,2,2,2,2).
The a(20) = 7 integer partitions are (20), (14,6), (12,8), (10,6,4), (5,5,5,5), (4,4,4,4,4), (2,2,2,2,2,2,2,2,2,2).

Cf. A030019, A035053, A048143, A134954, A286520, A293510, A293994, A303837, A303838, A304382.

zsm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[Less@@#,GCD@@s[[#]]]>1&]},If[c=={},s,zsm[Union[Append[Delete[s,List/@c[[1]]],LCM@@s[[c[[1]]]]]]]]];
zensity[s_]:=Total[(PrimeNu[#]-1&)/@s]-PrimeNu[LCM@@s];
Table[Length[Select[IntegerPartitions[n],And[zensity[#]==-1,Length[zsm[#]]==1,Select[Tuples[#,2],UnsameQ@@#&&Divisible@@#&]=={}]&]],{n,30}]

a(51)-a(81) from Robert Price, Sep 15 2018

cp's OEIS Frontend

A317635 Number of connected vertex sets of clutters (connected antichains) spanning n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A317674 Regular triangle where T(n,k) is the number of antichains covering n vertices with k connected components.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A323817 Number of connected set-systems covering n vertices with no singletons.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A317677 Fixed point of a shifted hypertree transform.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A326573 Number of connected antichains of subsets of {1..n}, all having different sums.

Views

Author

Keywords

Comments

Examples

Crossrefs

A317671 Regular triangle where T(n,k) is the number of labeled connected graphs on n + 1 vertices with k maximal blobs (2-connected components).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A305194 Number of z-forests summing to n. Number of strict integer partitions of n with pairwise indivisible parts and all connected components having clutter density -1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A305195 Number of z-blobs summing to n. Number of connected strict integer partitions of n, with pairwise indivisible parts, that cannot be capped by a z-tree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A323820 Number of non-isomorphic connected set-systems covering n vertices with no singletons.

Views

Author

Keywords