A304867 -id:A304867 - cp's OEIS frontend

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

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

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

A321229 Number of non-isomorphic connected weight-n multiset partitions with multiset density -1.

Original entry on oeis.org

1, 1, 3, 6, 16, 37, 105, 279, 817, 2387, 7269

Offset: 0

Gus Wiseman, Oct 31 2018

The multiset density of a multiset partition is the sum of the numbers of distinct vertices in each part minus the number of parts minus the number of vertices.

The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(1) = 1 through a(5) = 37 multiset partitions:
  {{1}}  {{1,1}}    {{1,1,1}}      {{1,1,1,1}}        {{1,1,1,1,1}}
         {{1,2}}    {{1,2,2}}      {{1,1,2,2}}        {{1,1,2,2,2}}
         {{1},{1}}  {{1,2,3}}      {{1,2,2,2}}        {{1,2,2,2,2}}
                    {{1},{1,1}}    {{1,2,3,3}}        {{1,2,2,3,3}}
                    {{2},{1,2}}    {{1,2,3,4}}        {{1,2,3,3,3}}
                    {{1},{1},{1}}  {{1},{1,1,1}}      {{1,2,3,4,4}}
                                   {{1,1},{1,1}}      {{1,2,3,4,5}}
                                   {{1},{1,2,2}}      {{1},{1,1,1,1}}
                                   {{1,2},{2,2}}      {{1,1},{1,1,1}}
                                   {{1,3},{2,3}}      {{1,1},{1,2,2}}
                                   {{2},{1,2,2}}      {{1},{1,2,2,2}}
                                   {{3},{1,2,3}}      {{1,2},{2,2,2}}
                                   {{1},{1},{1,1}}    {{1,2},{2,3,3}}
                                   {{1},{2},{1,2}}    {{1,3},{2,3,3}}
                                   {{2},{2},{1,2}}    {{1,4},{2,3,4}}
                                   {{1},{1},{1},{1}}  {{2},{1,1,2,2}}
                                                      {{2},{1,2,2,2}}
                                                      {{2},{1,2,3,3}}
                                                      {{2,2},{1,2,2}}
                                                      {{3},{1,2,3,3}}
                                                      {{3,3},{1,2,3}}
                                                      {{4},{1,2,3,4}}
                                                      {{1},{1},{1,1,1}}
                                                      {{1},{1,1},{1,1}}
                                                      {{1},{1},{1,2,2}}
                                                      {{1},{1,2},{2,2}}
                                                      {{1},{2},{1,2,2}}
                                                      {{2},{1,2},{2,2}}
                                                      {{2},{1,3},{2,3}}
                                                      {{2},{2},{1,2,2}}
                                                      {{2},{3},{1,2,3}}
                                                      {{3},{1,3},{2,3}}
                                                      {{3},{3},{1,2,3}}
                                                      {{1},{1},{1},{1,1}}
                                                      {{1},{2},{2},{1,2}}
                                                      {{2},{2},{2},{1,2}}
                                                      {{1},{1},{1},{1},{1}}

Cf. A000272, A007716, A007718, A030019, A052888, A134954, A304867, A304887, A318697, A321155, A321227, A321228, A321231.

A306007 Number of non-isomorphic intersecting antichains of weight n.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 6, 6, 14, 22

Offset: 0

Gus Wiseman, Jun 16 2018

An intersecting antichain S is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection, and none of which is a subset of any other. The weight of S is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

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

Cf. A007411, A007716, A034691, A048143, A049311, A116540, A283877, A293606, A293607, A304867, A305999, A305854-A305857, A306005-A306008.

A304386 Number of unlabeled hypertrees (connected antichains with no cycles) spanning up to n vertices and allowing singleton edges.

Original entry on oeis.org

1, 2, 5, 15, 50, 200, 907, 4607, 25077, 144337, 863678, 5329994, 33697112, 217317986, 1424880997, 9474795661, 63769947778, 433751273356, 2977769238994, 20611559781972, 143720352656500, 1008765712435162, 7122806053951140, 50566532826530292, 360761703055959592

Offset: 0

Gus Wiseman, May 21 2018

nonn

			Non-isomorphic representatives of the a(3) = 15 hypertrees are the following:
  {}
  {{1}}
  {{1,2}}
  {{1,2,3}}
  {{2},{1,2}}
  {{1,3},{2,3}}
  {{3},{1,2,3}}
  {{1},{2},{1,2}}
  {{3},{1,2},{2,3}}
  {{3},{1,3},{2,3}}
  {{2},{3},{1,2,3}}
  {{1},{2},{3},{1,2,3}}
  {{2},{3},{1,2},{1,3}}
  {{2},{3},{1,3},{2,3}}
  {{1},{2},{3},{1,3},{2,3}}

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

Cf. A030019, A035053, A048143, A054921, A134954, A134955, A134957, A134959, A144959, A304386, A304717, A304867, A304911, A304912, A304968, A304970.

\\ 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))/(1-x))} \\ Andrew Howroyd, Aug 27 2018

Partial sums of b(1) = 1, b(n) = A134959(n) otherwise.

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

A320798 Number of non-isomorphic weight-n connected antichains of non-constant multisets with multiset density -1.

Original entry on oeis.org

0, 1, 2, 5, 9, 24, 51, 134, 328, 868

Offset: 1

Gus Wiseman, Nov 29 2018

The multiset density of a multiset partition is the sum of the numbers of distinct vertices in each part minus the number of parts minus the number of vertices.

The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(2) = 1 through a(6) = 24 multiset partitions:
  {{12}}  {{122}}  {{1122}}    {{11222}}    {{111222}}
          {{123}}  {{1222}}    {{12222}}    {{112222}}
                   {{1233}}    {{12233}}    {{112233}}
                   {{1234}}    {{12333}}    {{122222}}
                   {{13}{23}}  {{12344}}    {{122333}}
                               {{12345}}    {{123333}}
                               {{12}{233}}  {{123344}}
                               {{13}{233}}  {{123444}}
                               {{14}{234}}  {{123455}}
                                            {{123456}}
                                            {{112}{233}}
                                            {{122}{233}}
                                            {{12}{2333}}
                                            {{123}{344}}
                                            {{124}{344}}
                                            {{125}{345}}
                                            {{13}{2233}}
                                            {{13}{2333}}
                                            {{13}{2344}}
                                            {{133}{233}}
                                            {{14}{2344}}
                                            {{15}{2345}}
                                            {{13}{24}{34}}
                                            {{14}{24}{34}}

Cf. A007716, A007718, A286520, A304867, A319719, A319721, A321155, A321760, A322111, A322113.

A304918 Number of labeled antichain hyperforests spanning a subset of {1,...,n}.

Original entry on oeis.org

1, 2, 5, 18, 104, 943, 12133, 203038, 4177755, 101922814, 2874725600, 92009680557, 3294276613933, 130446181101044, 5660055256165565, 267044522107706072, 13611243187516647324, 745329728016955480687, 43636132793651444511809, 2719977663069107176768790

Offset: 0

Gus Wiseman, May 21 2018

nonn

			The a(3) = 18 hyperforests are the following:
{{1,2,3}}      {{2,3}}    {{1,3}}    {{1,2}}    {{3}}   {{2}}   {{1}}   {}
{{1,3},{2,3}}  {{2},{3}}  {{1},{3}}  {{1},{2}}
{{1,2},{2,3}}
{{1,2},{1,3}}
{{3},{1,2}}
{{2},{1,3}}
{{1},{2,3}}
{{1},{2},{3}}

Cf. A030019, A035053, A048143, A134954, A134955, A134957, A134956, A134957, A134959, A144959, A303838, A304716, A304717, A304867, A304911, A304912.

Binomial transform of A134954.

A306008 Number of non-isomorphic intersecting set-systems of weight n with no singletons.

Original entry on oeis.org

1, 0, 1, 1, 2, 3, 7, 10, 21, 39, 78

Offset: 0

Gus Wiseman, Jun 16 2018

An intersecting set-system is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection. The weight of a set-system is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

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

Cf. A007716, A034691, A048143, A049311, A116540, A283877, A293606, A293607, A304867, A305999, A305854-A305857, A306005-A306007.

A321228 Number of non-isomorphic hypertrees of weight n with singletons.

Original entry on oeis.org

1, 1, 1, 2, 4, 6, 13, 23, 49, 100, 220

Offset: 0

Gus Wiseman, Oct 31 2018

A hypertree with singletons is a connected set system (finite set of finite nonempty sets) with density -1, where the density of a set system is the sum of sizes of the parts (weight) minus the number of parts minus the number of vertices.

			Non-isomorphic representatives of the a(1) = 1 through a(7) = 23 hypertrees:
  {{1}}  {{1,2}}  {{1,2,3}}    {{1,2,3,4}}      {{1,2,3,4,5}}
                  {{2},{1,2}}  {{1,3},{2,3}}    {{1,4},{2,3,4}}
                               {{3},{1,2,3}}    {{4},{1,2,3,4}}
                               {{1},{2},{1,2}}  {{2},{1,3},{2,3}}
                                                {{2},{3},{1,2,3}}
                                                {{3},{1,3},{2,3}}
.
  {{1,2,3,4,5,6}}        {{1,2,3,4,5,6,7}}
  {{1,2,5},{3,4,5}}      {{1,2,6},{3,4,5,6}}
  {{1,5},{2,3,4,5}}      {{1,6},{2,3,4,5,6}}
  {{5},{1,2,3,4,5}}      {{6},{1,2,3,4,5,6}}
  {{1},{1,4},{2,3,4}}    {{1},{1,5},{2,3,4,5}}
  {{1,3},{2,4},{3,4}}    {{1,2},{2,5},{3,4,5}}
  {{1,4},{2,4},{3,4}}    {{1,4},{2,5},{3,4,5}}
  {{3},{1,4},{2,3,4}}    {{1,5},{2,5},{3,4,5}}
  {{3},{4},{1,2,3,4}}    {{4},{1,2,5},{3,4,5}}
  {{4},{1,4},{2,3,4}}    {{4},{1,5},{2,3,4,5}}
  {{1},{2},{1,3},{2,3}}  {{4},{5},{1,2,3,4,5}}
  {{1},{2},{3},{1,2,3}}  {{5},{1,2,5},{3,4,5}}
  {{2},{3},{1,3},{2,3}}  {{5},{1,5},{2,3,4,5}}
                         {{1},{3},{1,4},{2,3,4}}
                         {{1},{4},{1,4},{2,3,4}}
                         {{2},{1,3},{2,4},{3,4}}
                         {{2},{3},{1,4},{2,3,4}}
                         {{2},{3},{4},{1,2,3,4}}
                         {{3},{1,4},{2,4},{3,4}}
                         {{3},{4},{1,4},{2,3,4}}
                         {{4},{1,3},{2,4},{3,4}}
                         {{4},{1,4},{2,4},{3,4}}
                         {{1},{2},{3},{1,3},{2,3}}

Cf. A000272, A007716, A007718, A030019, A052888, A134954, A304867, A304887, A317672, A318697, A321155, A321227, A321229.

A321253 Number of non-isomorphic strict connected weight-n multiset partitions with multiset density -1.

Original entry on oeis.org

0, 1, 2, 5, 12, 28, 78, 202, 578, 1650, 4904

Offset: 0

Gus Wiseman, Nov 01 2018

The multiset density of a multiset partition is the sum of the numbers of distinct vertices in each part minus the number of parts minus the number of vertices.

The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(1) = 1 through a(5) = 28 multiset partitions:
  {{1}}  {{1,1}}  {{1,1,1}}    {{1,1,1,1}}      {{1,1,1,1,1}}
         {{1,2}}  {{1,2,2}}    {{1,1,2,2}}      {{1,1,2,2,2}}
                  {{1,2,3}}    {{1,2,2,2}}      {{1,2,2,2,2}}
                  {{1},{1,1}}  {{1,2,3,3}}      {{1,2,2,3,3}}
                  {{2},{1,2}}  {{1,2,3,4}}      {{1,2,3,3,3}}
                               {{1},{1,1,1}}    {{1,2,3,4,4}}
                               {{1},{1,2,2}}    {{1,2,3,4,5}}
                               {{1,2},{2,2}}    {{1},{1,1,1,1}}
                               {{1,3},{2,3}}    {{1,1},{1,1,1}}
                               {{2},{1,2,2}}    {{1,1},{1,2,2}}
                               {{3},{1,2,3}}    {{1},{1,2,2,2}}
                               {{1},{2},{1,2}}  {{1,2},{2,2,2}}
                                                {{1,2},{2,3,3}}
                                                {{1,3},{2,3,3}}
                                                {{1,4},{2,3,4}}
                                                {{2},{1,1,2,2}}
                                                {{2},{1,2,2,2}}
                                                {{2},{1,2,3,3}}
                                                {{2,2},{1,2,2}}
                                                {{3},{1,2,3,3}}
                                                {{3,3},{1,2,3}}
                                                {{4},{1,2,3,4}}
                                                {{1},{1,2},{2,2}}
                                                {{1},{2},{1,2,2}}
                                                {{2},{1,2},{2,2}}
                                                {{2},{1,3},{2,3}}
                                                {{2},{3},{1,2,3}}
                                                {{3},{1,3},{2,3}}

Cf. A000272, A007716, A007718, A030019, A052888, A134954, A304867, A304887, A318697, A321155, A321194, A321228, A321229, A321254.

cp's OEIS Frontend

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

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

A321229 Number of non-isomorphic connected weight-n multiset partitions with multiset density -1.

Views

Author

Keywords

Comments

Examples

Crossrefs

A306007 Number of non-isomorphic intersecting antichains of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A304386 Number of unlabeled hypertrees (connected antichains with no cycles) spanning up to n vertices and allowing singleton edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A320798 Number of non-isomorphic weight-n connected antichains of non-constant multisets with multiset density -1.

Views

Author

Keywords

Comments

Examples

Crossrefs

A304918 Number of labeled antichain hyperforests spanning a subset of {1,...,n}.

Views

Author

Keywords

Examples

Crossrefs

Formula

A306008 Number of non-isomorphic intersecting set-systems of weight n with no singletons.

Views

Author

Keywords

Comments

Examples

Crossrefs

A321228 Number of non-isomorphic hypertrees of weight n with singletons.

Views

Author

Keywords

Comments

Examples

Crossrefs

A321253 Number of non-isomorphic strict connected weight-n multiset partitions with multiset density -1.

Views