A322110 Number of non-isomorphic connected multiset partitions of weight n that cannot be capped by a tree.

1, 1, 3, 6, 15, 32, 86, 216, 628, 1836, 5822

Offset: 0

Author

Gus Wiseman, Nov 26 2018

Keywords

• nonn
• more

Comments

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

The density of a multiset partition is defined to be the sum of numbers of distinct elements in each part, minus the number of parts, minus the total number of distinct elements in the whole partition. A multiset partition is a tree if it has more than one part, is connected, and has density -1. A cap is a certain kind of non-transitive coarsening of a multiset partition. For example, the four caps of {{1,1},{1,2},{2,2}} are {{1,1},{1,2},{2,2}}, {{1,1},{1,2,2}}, {{1,1,2},{2,2}}, {{1,1,2,2}}. - Gus Wiseman, Feb 05 2021

Examples

			The multiset partition C = {{1,1},{1,2,3},{2,3,3}} is not a tree but has the cap {{1,1},{1,2,3,3}} which is a tree, so C is not counted under a(8).
Non-isomorphic representatives of the a(1) = 1 through a(5) = 32 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},{1,2}}      {{1,1},{1,1,1}}
                                   {{2},{1,2,2}}      {{1},{1,2,2,2}}
                                   {{3},{1,2,3}}      {{1,2},{1,2,2}}
                                   {{1},{1},{1,1}}    {{2},{1,1,2,2}}
                                   {{1},{2},{1,2}}    {{2},{1,2,2,2}}
                                   {{2},{2},{1,2}}    {{2},{1,2,3,3}}
                                   {{1},{1},{1},{1}}  {{2,2},{1,2,2}}
                                                      {{2,3},{1,2,3}}
                                                      {{3},{1,2,3,3}}
                                                      {{4},{1,2,3,4}}
                                                      {{1},{1},{1,1,1}}
                                                      {{1},{1,1},{1,1}}
                                                      {{1},{1},{1,2,2}}
                                                      {{1},{2},{1,2,2}}
                                                      {{2},{1,2},{1,2}}
                                                      {{2},{1,2},{2,2}}
                                                      {{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}}
		

Links

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

Crossrefs

Non-isomorphic tree multiset partitions are counted by A321229.

The weak-antichain case is counted by A322117.

The case without singletons is counted by A322118.

Cf. A002218, A007718, A013922, A030019, A056156, A275307, A304118, A304382, A304887, A305052, A305079, A321194.

Extensions

Corrected by Gus Wiseman, Jan 27 2021