A304716 -id:A304716 - cp's OEIS frontend

A322390 Number of integer partitions of n with vertex-connectivity 1.

0, 1, 1, 2, 1, 3, 1, 4, 2, 5, 1, 8, 1, 7, 3, 11, 1, 14, 2, 18, 7, 21, 6, 35, 14, 43, 28, 65, 42, 96, 70, 141, 120, 205, 187, 315, 286, 445, 445, 657

Offset: 1

Gus Wiseman, Dec 05 2018

The vertex-connectivity of an integer partition is the minimum number of primes that must be divided out (and any parts then equal to 1 removed) so that the prime factorizations of the remaining parts form a disconnected (or empty) hypergraph.

			The a(14) = 7 integer partitions are (842), (8222), (77), (4442), (44222), (422222), (2222222).
The a(18) = 14 integer partitions:
  (9,9), (16,2),
  (8,8,2), (10,6,2),
  (8,4,4,2), (9,3,3,3),
  (4,4,4,4,2), (8,4,2,2,2),
  (3,3,3,3,3,3), (4,4,4,2,2,2), (8,2,2,2,2,2),
  (4,4,2,2,2,2,2),
  (4,2,2,2,2,2,2,2),
  (2,2,2,2,2,2,2,2,2).

Wikipedia, k-vertex-connected graph

Cf. A013922, A054921, A095983, A304714, A304716, A305078, A305079, A322335, A322338, A322387, A322389, A322391.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
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]]]]]]]]];
vertConn[y_]:=If[Length[csm[primeMS/@y]]!=1,0,Min@@Length/@Select[Subsets[Union@@primeMS/@y],Function[del,Length[csm[DeleteCases[DeleteCases[primeMS/@y,Alternatives@@del,{2}],{}]]]!=1]]];
Table[Length[Select[IntegerPartitions[n],vertConn[#]==1&]],{n,20}]

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

A325105 Number of binary carry-connected subsets of {1...n}.

Original entry on oeis.org

1, 2, 3, 7, 8, 20, 48, 112, 113, 325, 777, 1737, 3709, 7741, 15869, 32253, 32254, 96538, 225798, 485702, 1006338, 2049602, 4137346, 8315266, 16697102, 33465934, 67007886, 134100366, 268301518, 536720590, 1073575118, 2147316942, 2147316943, 6441886323

Offset: 0

Gus Wiseman, Mar 28 2019

nonn

A binary carry of two positive integers is an overlap of the positions of 1's in their reversed binary expansion. A subset is binary carry-connected if the graph whose vertices are the elements and whose edges are binary carries is connected.

			The a(0) = 1 through a(4) = 8 subsets:
  {}  {}   {}   {}       {}
      {1}  {1}  {1}      {1}
           {2}  {2}      {2}
                {3}      {3}
                {1,3}    {4}
                {2,3}    {1,3}
                {1,2,3}  {2,3}
                         {1,2,3}

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

Cf. A019565, A080572, A247935, A304714, A304716, A305078.
Cf. A325095, A325098, A325099, A325104, A325107, A325118, A325119.
Partial sums of A306299.

h:= proc(n, s) local i, m; m:= n;
      for i in s do m:= Bits[Or](m, i) od; {m}
    end:
g:= (n, s)-> (w-> `if`(w={}, s union {n}, s minus w union
              h(n, w)))(select(x-> Bits[And](n, x)>0, s)):
b:= proc(n, s) option remember; `if`(n=0,
      `if`(nops(s)>1, 0, 1), b(n-1, s)+b(n-1, g(n, s)))
    end:
a:= n-> b(n, {}):
seq(a(n), n=0..35);  # Alois P. Heinz, Mar 31 2019

binpos[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
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]]]]]]]]];
Table[Length[Select[Subsets[Range[n]],Length[csm[binpos/@#]]<=1&]],{n,0,10}]

a(n) = A306297(n,0) + A306297(n,1). - Alois P. Heinz, Mar 31 2019

a(16)-a(33) from Alois P. Heinz, Mar 31 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}]

A325119 Heinz numbers of binary carry-connected strict integer partitions.

Original entry on oeis.org

1, 2, 3, 5, 7, 10, 11, 13, 15, 17, 19, 22, 23, 29, 30, 31, 34, 37, 39, 41, 43, 46, 47, 51, 53, 55, 59, 61, 62, 65, 67, 71, 73, 77, 79, 82, 83, 85, 87, 89, 91, 93, 94, 97, 101, 102, 103, 107, 109, 110, 113, 115, 118, 119, 127, 129, 130, 131, 134, 137, 139, 141

Offset: 1

Gus Wiseman, Mar 28 2019

nonn

A binary carry of two positive integers is an overlap of the positions of 1's in their reversed binary expansion. An integer partition is binary carry-connected if the graph whose vertices are the parts and whose edges are binary carries is connected.

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1) * ... * prime(y_k), so these are squarefree numbers whose prime indices are binary carry-connected. 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.

			The sequence of terms together with their prime indices begins:
   1: {}
   2: {1}
   3: {2}
   5: {3}
   7: {4}
  10: {1,3}
  11: {5}
  13: {6}
  15: {2,3}
  17: {7}
  19: {8}
  22: {1,5}
  23: {9}
  29: {10}
  30: {1,2,3}
  31: {11}
  34: {1,7}
  37: {12}
  39: {2,6}
  41: {13}
  43: {14}

Cf. A019565, A048143, A056239, A112798, A304714, A304716, A305078.

Cf. A325098, A325099, A325100, A325105, A325110, A325118.

binpos[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
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[100],SquareFreeQ[#]&&Length[csm[binpos/@PrimePi/@First/@FactorInteger[#]]]<=1&]

A317077 Number of connected multiset partitions of normal multisets of size n.

Original entry on oeis.org

1, 1, 3, 8, 28, 110, 519, 2749, 16317, 106425, 755425, 5781956, 47384170, 413331955, 3818838624, 37213866876, 381108145231, 4088785729738, 45829237977692, 535340785268513, 6502943193997922, 81984445333355812, 1070848034863526547, 14467833457108560375, 201894571410270034773

Offset: 0

Gus Wiseman, Jul 20 2018

nonn

A multiset is normal if it spans an initial interval of positive integers.

			The a(3) = 8 connected multiset partitions are (111), (1)(11), (1)(1)(1), (122), (2)(12), (112), (1)(12), (123).

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

Cf. A007716, A007718, A048143, A293994, A303837, A303838, A304716, A305078.

Cf. A317073, A317075, A317078, A317079, A317080.

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]]]];
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]]]]]]]]];
allnorm[n_]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Length/@Table[Join@@Table[Select[mps[m],Length[csm[#]]==1&],{m,allnorm[n]}],{n,8}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
Connected(v)={my(u=vector(#v));for(n=1, #u, u[n]=v[n] - sum(k=1, n-1, binomial(n-1,k)*v[k]*u[n-k]));u}
seq(n)={my(u=vector(n, k, x*Ser(EulerT(vector(n,i,binomial(i+k-1,i)))))); Vec(1+vecsum(Connected(vector(n, k, sum(i=1, k, (-1)^(k-i)*binomial(k,i)*u[i])))))} \\ Andrew Howroyd, Jan 16 2023

Terms a(9) and beyond from Andrew Howroyd, Jan 16 2023

A322337 Number of strict 2-edge-connected integer partitions of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 1, 1, 2, 0, 4, 0, 4, 3, 5, 0, 9, 0, 10, 5, 11, 1, 18, 3, 17, 8, 22, 3, 35, 5, 32, 17, 39, 16, 59, 14, 58, 33, 75, 28, 103, 35, 106, 71, 125, 63, 174, 81, 192, 127, 220, 130, 294, 170, 325, 237, 378, 257, 504

Offset: 1

Gus Wiseman, Dec 04 2018

nonn

An integer partition is 2-edge-connected if the hypergraph of prime factorizations of its parts is connected and cannot be disconnected by removing any single part.

			The a(24) = 18 strict 2-edge-connected integer partitions of 24:
  (15,9)   (10,8,6)   (10,8,4,2)
  (16,8)   (12,8,4)   (12,6,4,2)
  (18,6)   (12,9,3)
  (20,4)   (14,6,4)
  (21,3)   (14,8,2)
  (22,2)   (15,6,3)
  (14,10)  (16,6,2)
           (18,4,2)
           (12,10,2)

Wikipedia, k-edge-connected graph

Cf. A007718, A013922, A054921, A095983, A218970, A275307, A286518, A304714, A304716, A305078, A305079, A322335, A322336.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
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]]]]]]]]];
twoedQ[sys_]:=And[Length[csm[sys]]==1,And@@Table[Length[csm[Delete[sys,i]]]==1,{i,Length[sys]}]];
Table[Length[Select[IntegerPartitions[n],And[UnsameQ@@#,twoedQ[primeMS/@#]]&]],{n,30}]

A317078 Number of connected multiset partitions of strongly normal multisets of size n.

Original entry on oeis.org

1, 1, 3, 6, 18, 46, 172, 563, 2347

Offset: 0

Gus Wiseman, Jul 20 2018

A multiset is strongly normal if it spans an initial interval of positive integers with weakly decreasing multiplicities.

			The a(3) = 6 connected multiset partitions are (111), (1)(11), (1)(1)(1), (112), (1)(12), (123).

Cf. A007716, A007718, A048143, A293994, A303837, A303838, A304716, A305078.

Cf. A317074, A317076, A317077, A317080.

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]]]];
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]]]]]]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
Length/@Table[Join@@Table[Select[mps[m],Length[csm[#]]==1&],{m,strnorm[n]}],{n,8}]

A326964 Number of connected set-systems covering a subset of {1..n}.

Original entry on oeis.org

1, 2, 7, 112, 32253, 2147316942, 9223372023968335715, 170141183460469231667123699322514272668, 5789604461865809771178549250434395393752402807429031284280914691514037561273

Offset: 0

Gus Wiseman, Aug 10 2019

nonn

A set-system is a finite set of finite nonempty sets.

			The a(0) = 1 through a(2) = 7 set-systems:
  {}    {}     {}
        {{1}}  {{1}}
               {{2}}
               {{1,2}}
               {{1},{1,2}}
               {{2},{1,2}}
               {{1},{2},{1,2}}

Covering sets of subsets are A000371.
Connected graphs are A001187.
The unlabeled version is A309667.
The BII-numbers of connected set-systems are A326749.
The covering case is A323818.
Cf. A007718, A048143, A058891, A092918, A300913, A304716, A326866, A326948.

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]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Length[csm[#]]<=1&]],{n,0,4}]

Binomial transform of A323818.

A329552 Smallest MM-number of a connected set of n sets.

Original entry on oeis.org

1, 2, 39, 195, 5655, 62205, 2674815

Offset: 0

Gus Wiseman, Nov 17 2019

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. The multiset of multisets with MM-number n is formed by taking the multiset of prime indices of each part of the multiset of prime indices of n. For example, the prime indices of 78 are {1,2,6}, so the multiset of multisets with MM-number 78 is {{},{1},{1,2}}.

			The sequence of terms together with their corresponding systems begins:
        1: {}
        2: {{}}
       39: {{1},{1,2}}
      195: {{1},{2},{1,2}}
     5655: {{1},{2},{1,2},{1,3}}
    62205: {{1},{2},{3},{1,2},{1,3}}
  2674815: {{1},{2},{3},{1,2},{1,3},{1,4}}

MM-numbers of connected set-systems are A328514.
The weight of the system with MM-number n is A302242(n).
Connected numbers are A305078.
Maximum connected divisor is A327076.
BII-numbers of connected sets of sets are A326749.
The smallest BII-number of a connected set of n sets is A329625(n).
Allowing edges to have repeated vertices gives A329553.
Requiring the edges to form an antichain gives A329555.
The smallest MM-number of a set of n nonempty sets is A329557(n).
Cf. A048143, A056239, A112798, A302494, A304714, A304716, A305079, A322389, A328513, A329554, A329556, A329558.
Classes of MM-numbers: A305078 (connected), A316476 (antichains), A318991 (chains), A320456 (covers), A329559 (clutters).

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
zsm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[Less@@#,GCD@@s[[#]]]>1&]},If[c=={},s,zsm[Sort[Append[Delete[s,List/@c[[1]]],LCM@@s[[c[[1]]]]]]]]];
da=Select[Range[10000],SquareFreeQ[#]&&And@@SquareFreeQ/@primeMS[#]&&Length[zsm[primeMS[#]]]<=1&];
Table[da[[Position[PrimeOmega/@da,n][[1,1]]]],{n,First[Split[Union[PrimeOmega/@da],#2==#1+1&]]}]

cp's OEIS Frontend

A322390 Number of integer partitions of n with vertex-connectivity 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A325105 Number of binary carry-connected subsets of {1...n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A325119 Heinz numbers of binary carry-connected strict integer partitions.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A317077 Number of connected multiset partitions of normal multisets of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A322337 Number of strict 2-edge-connected integer partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A317078 Number of connected multiset partitions of strongly normal multisets of size n.

Views

Author