A304867 -id:A304867 - cp's OEIS frontend

A321227 Number of connected multiset partitions with multiset density -1 of strongly normal multisets of size n.

0, 1, 3, 6, 17, 43, 147, 458, 1729, 6445, 27011

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.

A multiset is normal if it spans an initial interval of positive integers, and strongly normal if in addition its multiplicities are weakly decreasing.

			The a(1) = 1 through a(4) = 17 multiset partitions:
  {{1}}  {{1,1}}    {{1,1,1}}      {{1,1,1,1}}
         {{1,2}}    {{1,1,2}}      {{1,1,1,2}}
         {{1},{1}}  {{1,2,3}}      {{1,1,2,2}}
                    {{1},{1,1}}    {{1,1,2,3}}
                    {{1},{1,2}}    {{1,2,3,4}}
                    {{1},{1},{1}}  {{1},{1,1,1}}
                                   {{1,1},{1,1}}
                                   {{1},{1,1,2}}
                                   {{1,1},{1,2}}
                                   {{1},{1,2,2}}
                                   {{1},{1,2,3}}
                                   {{1,2},{1,3}}
                                   {{2},{1,1,2}}
                                   {{1},{1},{1,1}}
                                   {{1},{1},{1,2}}
                                   {{1},{2},{1,2}}
                                   {{1},{1},{1},{1}}

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

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]]],Union@@s[[c[[1]]]]]]]]];
mensity[c_]:=Total[(Length[Union[#]]-1&)/@c]-Length[Union@@c];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
Table[Sum[Length[Select[mps[m],And[mensity[#]==-1,Length[csm[#]]==1]&]],{m,strnorm[n]}],{n,0,8}]

A333348 Matching number of the tree of n vertices with the largest number of maximum matchings.

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 16, 16, 16, 16, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 24, 24, 24

Offset: 0

Kevin Ryde, Mar 15 2020

nonn

Heuberger and Wagner consider how many different maximum matchings a tree of n vertices may have. They determine the unique tree (free tree) of n vertices with the largest number of maximum matchings, or at n=6 and n=34 the two trees with equal largest number. a(n) is the matching number of the unique tree, and of both n=34 trees since they have the same matching number. For n=6, a(6)=1 is the star-6 which is their T_{6,1}. The other n=6 is their T_{6,2} and its matching number would be a(6)=2 instead.

The trees n!=2 have all pairs of leaves an even distance apart (the type of free tree counted by A304867). Vertices an even distance to a leaf are Heuberger and Wagner's type A, and vertices an odd distance to a leaf are type B. Per their definitions (and for any "even distance leaves" tree in fact), all type B vertices must be matched in a maximum matching and consequently the matching number is the number of type B vertices. 2n/7 appears in the formula below since each "C" part contains 7 vertices of which 2 are type B; then there are certain fixed additional B vertices according to n mod 7.

Paolo Xausa, Table of n, a(n) for n = 0..10000
Clemens Heuberger and Stephan Wagner, The Number of Maximum Matchings in a Tree, Discrete Mathematics, volume 311, issue 21, November 2011, pages 2512-2542; arXiv preprint, arXiv:1011.6554 [math.CO], 2010.
Clemens Heuberger and Stephan Wagner, Number of Maximum Matchings In a Tree - Sage Worksheet, constructing the trees.
Kevin Ryde, vpar examples/most-maximum-matchings.gp creating, counting, and recurrences, in PARI/GP.
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,1,-1).

Cf. A333347 (number of maximum matchings).

A333348[n_] := Switch[n, 2, 1, 6, 1, 13, 3, 20, 5, _, Floor[(2*n + 2)/7]];
Array[A333348, 100, 0] (* Paolo Xausa, Jun 18 2024 *)

a(2)=a(6)=1, a(13)=3, a(20)=5, and otherwise a(n) = floor((2n+2)/7).

A337089 Number of rooted trees of n vertices in which all leaves are at even depths (distances down from the root).

Original entry on oeis.org

0, 1, 0, 1, 1, 3, 4, 10, 17, 38, 73, 158, 324, 700, 1483, 3224, 6979, 15300, 33571, 74219, 164476, 366302, 817999, 1833280, 4119266, 9281867, 20962757, 47453359, 107637494, 244630449, 556964670, 1270218355, 2901393727, 6637071449, 15203568955, 34872363374

Offset: 0

Kevin Ryde, Aug 15 2020

nonn

For n=0, there are no rooted trees at all, per A000081.
For n>=1, by omitting the root vertex, a(n) is the number of rooted forests of n-1 vertices in which all leaves are at odd depths down from the forest roots.  This includes the empty forest (no vertices at all).
For n>=1, a(n) is the number of rooted hypertrees of weight n-1.  Each vertex (leaf or not) at an even depth is a hypervertex.  The root is the hypertree root.  Each hyperedge is the set of vertices surrounding an odd depth vertex, so that the weight (total hyperedge cardinalities) is the number of edges in the tree (n-1).
A337090 counts trees with all leaves at odd depths.  The forests interpretation here is those odd trees assembled to make odd forests so that this sequence is shift-up of the Euler transform of A337090.  In turn A337090 is shift-up of the Euler transform of the present sequence (except for treatment of the empty forest) so that it's convenient to calculate them together term by term.

			For n=5 vertices there are a(5) = 3 rooted trees in which all leaves are at even depths.
    *        *       *      depth=0, root
    |       / \      |
    *      *   *     *
   /|\     |   |     |
  * * *    *   *     *      depth=2, even
                     |
                     *
                     |
                     *      depth=4, even

Kevin Ryde, Table of n, a(n) for n = 0..600

Cf. A337090, A304867.

\\ Return a vector of vec[n]=a(n) for n=1..len inclusive (so a(0)=0 omitted).
a_vector(len) = {
  my(evens=vector(len), ec=vector(len)); evens[1]=1;
  my(odds=vector(len),  oc=vector(len));
  for(n=1,len-1,
    ec[n] = sumdiv(n,d, d*evens[d]);
    oc[n] = sumdiv(n,d, d*odds[d]);
    evens[n+1] =          sum(k=1,n,   oc[k]*evens[n+1-k])  /n;
    odds[n+1]  = (ec[n] + sum(k=1,n-1, ec[k]* odds[n+1-k])) /n);
  evens; }  \\ or instead "odds" is A337090

a(n) = (Sum_{k=1..n-1} a(k) * Sum_{d divides n-k} d*A337090(d)) / (n-1), for n>=2.
G.f.: x * Product_{k>=1} 1/(1-x^k)^A337090(k).
G.f.: x * exp(Sum_{k>=1} A337090(x^k)/k).

A304977 Number of unlabeled hyperforests spanning n vertices with singleton edges allowed.

Original entry on oeis.org

1, 1, 4, 14, 55, 235, 1112, 5672, 30783, 175733, 1042812, 6385278, 40093375, 257031667, 1676581863, 11098295287, 74401300872, 504290610004, 3451219615401, 23821766422463, 165684694539918, 1160267446543182, 8175446407807625, 57928670942338011, 412561582740147643

Offset: 0

Gus Wiseman, May 22 2018

nonn

			Non-isomorphic representatives of the a(3) = 14 hyperforests are the following:
  {{1,2,3}}
  {{3},{1,2}}
  {{3},{1,2,3}}
  {{1,3},{2,3}}
  {{1},{2},{3}}
  {{2},{3},{1,3}}
  {{2},{3},{1,2,3}}
  {{3},{1,2},{2,3}}
  {{3},{1,3},{2,3}}
  {{1},{2},{3},{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, A134954, A134955, A134956, A134957, A134958, A134959, A144959, A304867, A304911, A304912, A304918.

\\ 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)); concat([1], EulerT(Vec(Ser(EulerT(u))*(1-x*Ser(u))-1)))} \\ Andrew Howroyd, Aug 27 2018

Euler transform of b(1) = 1, b(n > 1) = A134959(n).

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

A322112 Number of non-isomorphic self-dual connected multiset partitions of weight n with no singletons and multiset density -1.

Original entry on oeis.org

1, 0, 1, 1, 1, 2, 2, 4, 4, 9, 9

Offset: 0

Gus Wiseman, Nov 26 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 dual of a multiset partition has, for each vertex, one part consisting of the indices (or positions) of the parts containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,2}} is {{1},{1,2,2}}. A multiset partition is self-dual if it is isomorphic to its dual. For example, {{1,1},{1,2,2},{2,3,3}} is self-dual, as it is isomorphic to its dual {{1,1,2},{2,2,3},{3,3}}.
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(10) = 9 multiset partitions:
  {{11}}  {{111}}  {{1111}}  {{11111}}    {{111111}}    {{1111111}}
                             {{11}{122}}  {{22}{1122}}  {{111}{1222}}
                                                        {{22}{11222}}
                                                        {{11}{12}{233}}
.
  {{11111111}}      {{111111111}}        {{1111111111}}
  {{111}{11222}}    {{1111}{12222}}      {{1111}{112222}}
  {{22}{112222}}    {{22}{1122222}}      {{22}{11222222}}
  {{11}{122}{233}}  {{222}{111222}}      {{222}{1112222}}
                    {{11}{11}{12233}}    {{111}{122}{2333}}
                    {{11}{113}{2233}}    {{22}{113}{23333}}
                    {{12}{111}{2333}}    {{22}{1133}{2233}}
                    {{22}{113}{2333}}    {{33}{33}{112233}}
                    {{12}{13}{22}{344}}  {{11}{14}{223}{344}}

Cf. A000272, A007716, A007718, A030019, A052888, A134954, A304867, A304887, A316983, A321155, A321255, A322111.

A304919 Number of labeled hyperforests spanning {1,...,n} and allowing singleton edges.

Original entry on oeis.org

1, 1, 5, 45, 665, 14153, 399421, 14137301, 603647601, 30231588689, 1738713049013, 112976375651901, 8186616300733321, 654642360222892057, 57267075701210437229, 5440407421313402397541, 557802495215406348358113, 61393838258161429159571873, 7220049654850517272144419941, 903546142463635579042416518989

Offset: 0

Gus Wiseman, May 21 2018

nonn

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

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

Inverse binomial transform of A134956.

cp's OEIS Frontend

A321227 Number of connected multiset partitions with multiset density -1 of strongly normal multisets of size n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A333348 Matching number of the tree of n vertices with the largest number of maximum matchings.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A337089 Number of rooted trees of n vertices in which all leaves are at even depths (distances down from the root).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A304977 Number of unlabeled hyperforests spanning n vertices with singleton edges allowed.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A322112 Number of non-isomorphic self-dual connected multiset partitions of weight n with no singletons and multiset density -1.

Views

Author

Keywords

Comments

Examples

Crossrefs

A304919 Number of labeled hyperforests spanning {1,...,n} and allowing singleton edges.

Views

Author

Keywords

Examples

Crossrefs

Formula