A048143 -id:A048143 - cp's OEIS frontend

A326752 BII-numbers of hypertrees.

0, 1, 2, 4, 8, 16, 20, 32, 36, 48, 64, 128, 256, 260, 272, 276, 292, 304, 320, 512, 516, 532, 544, 548, 560, 576, 768, 784, 800, 1024, 1040, 1056, 2048, 2064, 2068, 2080, 2084, 2096, 2112, 2304, 2308, 2336, 2560, 2564, 2576, 2816, 3072, 4096, 4100, 4128, 4608

Offset: 1

Gus Wiseman, Jul 23 2019

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18.

Elements of a set-system are sometimes called edges. In an antichain, no edge is a subset or superset of any other edge. A hypertree is a connected antichain of nonempty sets with density -1, where density is the sum of sizes of the edges minus the number of edges minus the number of vertices.

			The sequence of all hypertrees together with their BII-numbers begins:
    0: {}
    1: {{1}}
    2: {{2}}
    4: {{1,2}}
    8: {{3}}
   16: {{1,3}}
   20: {{1,2},{1,3}}
   32: {{2,3}}
   36: {{1,2},{2,3}}
   48: {{1,3},{2,3}}
   64: {{1,2,3}}
  128: {{4}}
  256: {{1,4}}
  260: {{1,2},{1,4}}
  272: {{1,3},{1,4}}
  276: {{1,2},{1,3},{1,4}}
  292: {{1,2},{2,3},{1,4}}
  304: {{1,3},{2,3},{1,4}}
  320: {{1,2,3},{1,4}}

Cf. A000120, A000272, A030019 (spanning hypertrees), A035053, A048143, A048793, A052888, A070939, A134954, A275307, A326031, A326702, A326753.

Other BII-numbers: A309314 (hyperforests), A326701 (set partitions), A326703 (chains), A326704 (antichains), A326749 (connected), A326750 (clutters), A326751 (blobs), A326754 (covers).

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
density[c_]:=Total[(Length[#1]-1&)/@c]-Length[Union@@c];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Select[Range[0,1000],#==0||stableQ[bpe/@bpe[#],SubsetQ]&&Length[csm[bpe/@bpe[#]]]<=1&&density[bpe/@bpe[#]]==-1&]

A371452 Number of connected components of the prime indices of the binary indices of n.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 3, 1, 2, 1, 2, 2, 3, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 4, 3, 4, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 4, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5

Offset: 1

Gus Wiseman, Apr 01 2024

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

			The prime indices of binary indices of 281492156579880 are {{1,1},{1,2},{3,4},{4,4}}, with 2 connected components {{1,1},{1,2}} and {{3,4},{4,4}}, so a(281492156579880) = 2.

Positions of first appearances are A080355, opposite A325782.
For prime indices of prime indices we have A305079, ones A305078.
For binary indices of binary indices we have A326753, ones A326749.
Positions of ones are A371291.
For binary indices of prime indices we have A371451, ones A325118.
A001187 counts connected graphs.
A007718 counts non-isomorphic connected multiset partitions.
A048143 counts connected antichains of sets.
A048793 lists binary indices, reverse A272020, length A000120, sum A029931.
A070939 gives length of binary expansion.
A112798 lists prime indices, reverse A296150, length A001222, sum A056239.
A326964 counts connected set-systems, covering A323818.
Cf. A000720, A019565, A087086, A096111, A325097, A326782, A368109, A371292, A371294, A371445, A371447.

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}], Length[Intersection@@s[[#]]]>0&]},If[c=={},s, csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
bix[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n], {p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Length[csm[prix/@bix[n]]],{n,100}]

A134959 Number of spanning hypertrees with n unlabeled vertices: analog of A035053 when edges of size 1 are allowed (with no two equal edges).

Original entry on oeis.org

1, 2, 3, 10, 35, 150, 707, 3700, 20470, 119260, 719341, 4466316, 28367118, 183620874, 1207563011, 8049914664, 54295152117, 369981325578, 2544017965638, 17633790542978, 123108792874528, 865045359778662, 6114040341515978, 43443726772579152, 310195170229429300

Offset: 0

Don Knuth, Jan 26 2008

nonn

			From _Gus Wiseman_, May 20 2018: (Start)
Non-isomorphic representatives of the a(3) = 10 hypertrees are the following:
  {{1,2,3}}
  {{3},{1,2,3}}
  {{1,3},{2,3}}
  {{2},{3},{1,2,3}}
  {{2},{1,3},{2,3}}
  {{3},{1,3},{2,3}}
  {{1},{2},{3},{1,2,3}}
  {{1},{2},{1,3},{2,3}}
  {{2},{3},{1,3},{2,3}}
  {{1},{2},{3},{1,3},{2,3}}
(End)

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

Cf. A030019, A035053, A048143, A054921, A134955, A134957, A144959, A304867, A304911, A318494.

etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*p[d], {d, Divisors[j]}]*b[n - j], {j, 1, n}]/n]; b];
EulerT[v_List] := With[{q = etr[v[[#]] &]}, q /@ Range[Length[v]]];
ser[v_] := Sum[v[[i]] x^(i - 1), {i, 1, Length[v]}] + O[x]^Length[v];
b[n_] := Module[{v = {1}}, For[i = 2, i <= n, i++, v = Join[{1}, EulerT[EulerT[2 v]]]]; v];
seq[n_] := Module[{u = 2 b[n]}, 1 + x*ser[EulerT[u]]*(1 - x*ser[u]) + O[x]^n // CoefficientList[#, x]&];
seq[25] (* Jean-François Alcover, Feb 10 2020, after Andrew Howroyd *)

\\ here b(n) is A318494 as vector
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
b(n)={my(v=[1]); for(i=2, n, v=concat([1], EulerT(EulerT(2*v)))); v}
seq(n)={my(u=2*b(n)); Vec(1 + x*Ser(EulerT(u))*(1-x*Ser(u)))} \\ Andrew Howroyd, Aug 27 2018

Inverse Euler transform of A134957. - Gus Wiseman, May 20 2018

Terms a(7) and beyond from Andrew Howroyd, Aug 27 2018

A299353 Number of labeled connected uniform hypergraphs spanning n vertices.

Original entry on oeis.org

1, 1, 1, 5, 50, 1713, 1101990, 68715891672, 1180735735356264714926, 170141183460507906731293351306487161569, 7237005577335553223087828975127304177495735363998991435497132228228565768846

Offset: 0

Gus Wiseman, Jun 18 2018

nonn

A hypergraph is uniform if all edges have the same size.

Let T be the regular triangle A299354, where column k is the logarithmic transform of the inverse binomial transform of c(d) = 2^binomial(d,k). Then a(n) is the sum of row n.

			The a(3) = 5 hypergraphs:
{{1,2,3}}
{{1,2},{1,3}}
{{1,2},{2,3}}
{{1,3},{2,3}}
{{1,2},{1,3},{2,3}}

Wikipedia, Hypergraph

Cf. A000005, A001315, A006126, A006129, A038041, A048143, A298422, A299354, A299471, A306020, A306021.

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

A305193 Number of connected factorizations of n.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 5, 1, 2, 1, 2, 1, 1, 1, 4, 2, 1, 3, 2, 1, 1, 1, 7, 1, 1, 1, 5, 1, 1, 1, 4, 1, 1, 1, 2, 2, 1, 1, 7, 2, 2, 1, 2, 1, 4, 1, 4, 1, 1, 1, 3, 1, 1, 2, 11, 1, 1, 1, 2, 1, 1, 1, 10, 1, 1, 2, 2, 1, 1, 1, 7, 5, 1, 1, 3, 1, 1, 1, 4, 1, 3, 1, 2, 1, 1, 1, 12, 1, 2, 2, 5, 1, 1, 1, 4, 1

Offset: 1

Gus Wiseman, May 27 2018

nonn

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

a(n) depends only on prime signature of n (cf. A025487). - Antti Karttunen, Nov 07 2018

			The a(72) = 10 factorizations:
(72),
(2*2*18), (2*3*12), (2*6*6), (3*4*6),
(2*36), (3*24), (4*18), (6*12),
(2*2*3*6).

Antti Karttunen, Table of n, a(n) for n = 1..20736
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000
Index entries for sequences computed from exponents in factorization of n

Cf. A048143, A281116, A286518, A286520, A290103, A303837, A304118, A304714, A304716, A305078, A305079, A319786.

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]]]]]]]]];
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n],Length[zsm[#]]==1&]],{n,100}]

is_connected(facs) = { my(siz=length(facs)); if(1==siz,1,my(m=matrix(siz,siz,i,j,(gcd(facs[i],facs[j])!=1))^siz); for(n=1,siz,if(0==vecmin(m[n,]),return(0))); (1)); };
A305193aux(n, m, facs) = if(1==n, is_connected(Set(facs)), my(s=0, newfacs); fordiv(n, d, if((d>1)&&(d<=m), newfacs = List(facs); listput(newfacs,d); s += A305193aux(n/d, d, newfacs))); (s)); \\ Antti Karttunen, Nov 07 2018
A305193(n) = if(1==n,0,A305193aux(n, n, List([]))); \\ Antti Karttunen, Nov 07 2018

More terms from Antti Karttunen, Nov 07 2018

A309314 BII-numbers of hyperforests.

Original entry on oeis.org

0, 1, 2, 3, 4, 8, 9, 10, 11, 12, 16, 18, 20, 32, 33, 36, 48, 64, 128, 129, 130, 131, 132, 136, 137, 138, 139, 140, 144, 146, 148, 160, 161, 164, 176, 192, 256, 258, 260, 264, 266, 268, 272, 274, 276, 288, 292, 304, 320, 512, 513, 516, 520, 521, 524, 528, 532

Offset: 1

Gus Wiseman, Jul 23 2019

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18.

Elements of a set-system are sometimes called edges. In an antichain, no edge is a subset or superset of any other edge. A hyperforest is an antichain of nonempty sets whose connected components are hypertrees, meaning they have density -1, where density is the sum of sizes of the edges minus the number of edges minus the number of vertices.

			The sequence of all hyperforests together with their BII-numbers begins:
    0: {}
    1: {{1}}
    2: {{2}}
    3: {{1},{2}}
    4: {{1,2}}
    8: {{3}}
    9: {{1},{3}}
   10: {{2},{3}}
   11: {{1},{2},{3}}
   12: {{1,2},{3}}
   16: {{1,3}}
   18: {{2},{1,3}}
   20: {{1,2},{1,3}}
   32: {{2,3}}
   33: {{1},{2,3}}
   36: {{1,2},{2,3}}
   48: {{1,3},{2,3}}
   64: {{1,2,3}}
  128: {{4}}
  129: {{1},{4}}
  130: {{2},{4}}
  131: {{1},{2},{4}}
  132: {{1,2},{4}}
  136: {{3},{4}}
  137: {{1},{3},{4}}

Cf. A000120, A030019, A035053, A048143, A048793, A052888, A070939, A134954, A275307, A326031, A326702, A326753.

Other BII-numbers: A326701 (set partitions), A326703 (chains), A326704 (antichains), A326749 (connected), A326750 (clutters), A326751 (blobs), A326752 (hypertrees), A326754 (covers).

A134956 Number of hyperforests with n labeled vertices: analog of A134954 when edges of size 1 are allowed (with no two equal edges).

Original entry on oeis.org

1, 2, 8, 64, 880, 17984, 495296, 17255424, 728771584, 36208782336, 2069977144320, 133869415030784, 9664049202221056, 770400218809384960, 67219977066339008512, 6372035504466437079040, 652103070162164448952320, 71656927837957783339925504

Offset: 0

Don Knuth, Jan 26 2008

nonn

			From _Gus Wiseman_, May 21 2018: (Start)
The a(2) = 8 hyperforests are the following:
  {{1},{2},{1,2}}
  {{1},{1,2}}
  {{2},{1,2}}
  {{1,2}}
  {{1},{2}}
  {{1}}
  {{2}}
  {}
(End)

D. E. Knuth: The Art of Computer Programming, Volume 4, Generating All Combinations and Partitions Fascicle 3, Section 7.2.1.4. Generating all partitions. Page 38, Algorithm H. - Washington Bomfim, Sep 25 2008

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

Cf. A134958. - Washington Bomfim, Sep 25 2008

Cf. A030019, A035053, A048143, A054921, A134954, A134955, A134957, A144959, A304716, A304717, A304867, A304911.

with(combinat): p:= proc(n) option remember; add(stirling2(n-1, i) *n^(i-1), i=0..n-1) end: g:= proc(n) option remember; p(n) +add(binomial(n-1, k-1) *p(k) *g(n-k), k=1..n-1) end: a:= n-> `if`(n=0, 1, 2^n * g(n)): seq(a(n), n=0..30); # Alois P. Heinz, Oct 07 2008

p[n_] := p[n] = Sum[ StirlingS2[n-1, i]*n^(i-1), {i, 0, n-1}]; g[n_] := g[n] = p[n] + Sum[Binomial[n-1, k-1]*p[k]*g[n-k], {k, 1, n-1}]; a[n_] := If[n == 0, 1, 2^n* g[n]]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 13 2015, after Alois P. Heinz *)

Equals 2^n*A134954(n).

a(n) = Sum of n!prod_{k=1}^n\{ frac{ A134958(k)^{c_k} }{ k!^{c_k} c_k! } } over all the partitions of n, c_1 + 2c_2 + ... + nc_n; c_1, c_2, ..., c_n >= 0. - Washington Bomfim, Sep 25 2008

A293607 Number of unlabeled clutters of weight n.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 7, 8, 23, 42

Offset: 0

Gus Wiseman, Oct 13 2017

A clutter is a connected antichain of finite sets. The weight of a clutter is the sum of cardinalities of its edges.

			Non-isomorphic representatives of the a(7) = 8 clutters are:
((1234567)),
((12)(13456)), ((123)(1245)), ((123)(1456)),
((12)(13)(145)), ((12)(13)(234)), ((12)(13)(245)), ((13)(24)(125)).

Cf. A006126, A007716, A048143, A049311, A283877, A293606.

A120338 Number of disconnected antichain covers of a labeled n-set.

Original entry on oeis.org

0, 1, 4, 30, 546, 41334, 54502904, 19317020441804

Offset: 1

Greg Huber, Jun 22 2006

nonn

An antichain is a set of sets, none of which is a subset of any other. It is covering if there are no isolated vertices. - Gus Wiseman, Sep 26 2019

			a(3)=4: the four disconnected covers are {{1},{2,3}}, {{2},{1,3}}, {{3},{1,2}} and {{1},{2},{3}}.

Cf. A006126, A007153, A048143, A327355.
Column k = 0 of A327351, if we assume a(0) = 1.
Column k = 0 of A327357, if we assume a(0) = 1.
The non-covering version is A327354.
The unlabeled version is A327426.

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[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]]]];
Table[Length[Select[stableSets[Subsets[Range[n]],SubsetQ],Union@@#==Range[n]&&Length[csm[#]]!=1&]],{n,4}] (* Gus Wiseman, Sep 26 2019 *)

A304382 Number of z-trees summing to n. Number of connected strict integer partitions of n with pairwise indivisible parts and clutter density -1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 2, 1, 3, 2, 4, 3, 5, 2, 5, 4, 6, 3, 7, 6, 8, 4, 9, 8, 13, 9, 15, 8, 14, 12, 16, 12, 20, 20, 24, 15, 27, 20, 33, 27, 35

Offset: 1

Gus Wiseman, May 21 2018

Given a finite set S of positive integers greater than one, let G(S) be the simple labeled graph with vertex set S and edges between any two vertices with a common divisor. 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 clutter density of a multiset S of positive integers is Sum_{s in S} (omega(s) - 1) - omega(LCM(S)).

			The a(30) = 8 z-trees together with the corresponding multiset systems are the following.
       (30): {{1,2,3}}
     (26,4): {{1,6},{1,1}}
     (22,8): {{1,5},{1,1,1}}
     (21,9): {{2,4},{2,2}}
    (16,14): {{1,1,1,1},{1,4}}
   (15,9,6): {{2,3},{2,2},{1,2}}
  (14,10,6): {{1,4},{1,3},{1,2}}
  (12,10,8): {{1,1,2},{1,3},{1,1,1}}

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

Cf. A000009, A006126, A048143, A054921, A112798, A285572, A286518, A286520, A293993, A303362, A303837, A304714, A304716, A305194, 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];
strConnAnti[n_]:=Select[IntegerPartitions[n],UnsameQ@@#&&Length[zsm[#]]==1&&Select[Tuples[#,2],UnsameQ@@#&&Divisible@@#&]=={}&];
Table[Length[Select[strConnAnti[n],Length[#]==1||zreeQ[#]&]],{n,20}]

cp's OEIS Frontend

A326752 BII-numbers of hypertrees.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A371452 Number of connected components of the prime indices of the binary indices of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A134959 Number of spanning hypertrees with n unlabeled vertices: analog of A035053 when edges of size 1 are allowed (with no two equal edges).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A299353 Number of labeled connected uniform hypergraphs spanning n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A305193 Number of connected factorizations of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A309314 BII-numbers of hyperforests.

Views

Author

Keywords

Comments

Examples

Crossrefs

A134956 Number of hyperforests with n labeled vertices: analog of A134954 when edges of size 1 are allowed (with no two equal edges).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A293607 Number of unlabeled clutters of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A120338 Number of disconnected antichain covers of a labeled n-set.