A300660
Number of unlabeled rooted phylogenetic trees with n (leaf-) nodes such that for each inner node all children are either leaves or roots of distinct subtrees.
Original entry on oeis.org
0, 1, 1, 2, 3, 6, 13, 30, 72, 182, 467, 1222, 3245, 8722, 23663, 64758, 178459, 494922, 1380105, 3867414, 10884821, 30756410, 87215419, 248117618, 707952902, 2025479210, 5809424605, 16700811214, 48113496645, 138884979562, 401645917999, 1163530868090
Offset: 0
: a(3) = 2: : a(4) = 3: :
: o o : o o o :
: / \ /|\ : / \ / \ /( )\ :
: o N N N N : o N o N N N N N :
: ( ) : / \ /|\ :
: N N : o N N N N :
: : ( ) :
: : N N :
From _Gus Wiseman_, Feb 06 2020: (Start)
The a(2) = 1 through a(6) = 13 unlabeled rooted phylogenetic semi-identity trees:
(oo) (ooo) (oooo) (ooooo) (oooooo)
((o)(oo)) ((o)(ooo)) ((o)(oooo)) ((o)(ooooo))
((o)((o)(oo))) ((oo)(ooo)) ((oo)(oooo))
((o)((o)(ooo))) ((o)(oo)(ooo))
((oo)((o)(oo))) (((o)(oo))(ooo))
((o)((o)((o)(oo)))) ((o)((o)(oooo)))
((o)((oo)(ooo)))
((oo)((o)(ooo)))
((o)(oo)((o)(oo)))
((o)((o)((o)(ooo))))
((o)((oo)((o)(oo))))
((oo)((o)((o)(oo))))
((o)((o)((o)((o)(oo)))))
(End)
The locally disjoint case is
A316694.
-
b:= proc(n,i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(b(n-i*j, i-1)*binomial(a(i), j), j=0..n/i)))
end:
a:= n-> `if`(n=0, 0, 1+b(n, n-1)):
seq(a(n), n=0..30);
-
b[0, ] = 1; b[, _?NonPositive] = 0;
b[n_, i_] := b[n, i] = Sum[b[n-i*j, i-1]*Binomial[a[i], j], {j, 0, n/i}];
a[0] = 0; a[n_] := a[n] = 1 + b[n, n-1];
Table[a[n], {n, 0, 31}] (* Jean-François Alcover, May 03 2019, from Maple *)
ursit[n_]:=Prepend[Join@@Table[Select[Union[Sort/@Tuples[ursit/@ptn]],UnsameQ@@#&],{ptn,Select[IntegerPartitions[n],Length[#]>1&]}],n];
Table[Length[ursit[n]],{n,10}] (* Gus Wiseman, Feb 06 2020 *)
A319312
Number of series-reduced rooted trees whose leaves are integer partitions whose multiset union is an integer partition of n.
Original entry on oeis.org
1, 3, 7, 22, 67, 242, 885, 3456, 13761, 56342, 234269, 989335, 4225341, 18231145, 79321931, 347676128, 1533613723, 6803017863, 30328303589, 135808891308, 610582497919, 2755053631909, 12472134557093, 56630659451541, 257841726747551, 1176927093597201
Offset: 1
The a(3) = 7 trees:
(3) (21) (111)
((1)(2)) ((1)(11))
((1)(1)(1))
((1)((1)(1)))
Cf.
A000081,
A000311,
A000669,
A001678,
A005804,
A141268,
A292504,
A300660,
A316653,
A316654,
A316656.
-
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
phyfacs[n_]:=Prepend[Join@@Table[Union[Sort/@Tuples[phyfacs/@f]],{f,Select[facs[n],Length[#]>1&]}],n];
Table[Sum[Length[phyfacs[Times@@Prime/@m]],{m,IntegerPartitions[n]}],{n,6}]
-
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
seq(n)={my(v=[]); for(n=1, n, v=concat(v, numbpart(n) + EulerT(concat(v,[0]))[n])); v} \\ Andrew Howroyd, Sep 18 2018
A316651
Number of series-reduced rooted trees with n leaves spanning an initial interval of positive integers.
Original entry on oeis.org
1, 2, 12, 112, 1444, 24086, 492284, 11910790, 332827136, 10546558146, 373661603588, 14636326974270, 628032444609396, 29296137817622902, 1476092246351259964, 79889766016415899270, 4622371378514020301740, 284719443038735430679268, 18601385258191195218790756
Offset: 1
The a(3) = 12 trees:
(1(11)), (111),
(1(12)), (2(11)), (112),
(1(22)), (2(12)), (122),
(1(23)), (2(13)), (3(12)), (123).
-
b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(binomial(A(i, k)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
end:
A:= (n, k)-> `if`(n<2, n*k, b(n, n-1, k)):
a:= n-> add(add(A(n, k-j)*(-1)^j*binomial(k, j), j=0..k-1), k=1..n):
seq(a(n), n=1..20); # Alois P. Heinz, Sep 18 2018
-
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]]]];
gro[m_]:=If[Length[m]==1,m,Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])]];
allnorm[n_Integer]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Sum[Length[gro[m]],{m,allnorm[n]}],{n,5}]
(* Second program: *)
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0,
Sum[Binomial[A[i, k] + j - 1, j] b[n - i*j, i - 1, k], {j, 0, n/i}]]];
A[n_, k_] := If[n < 2, n*k, b[n, n - 1, k]];
a[n_] := Sum[Sum[A[n, k-j]*(-1)^j*Binomial[k, j], {j, 0, k-1}], {k, 1, n}];
Array[a, 20] (* Jean-François Alcover, May 09 2021, after Alois P. Heinz *)
-
\\ here R(n,k) is A000669, A050381, A220823, ...
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n,k)={my(v=[k]); for(n=2, n, v=concat(v, EulerT(concat(v,[0]))[n])); v}
seq(n)={sum(k=1, n, R(n,k)*sum(r=k, n, binomial(r,k)*(-1)^(r-k)) )} \\ Andrew Howroyd, Sep 14 2018
A316652
Number of series-reduced rooted trees whose leaves span an initial interval of positive integers with multiplicities an integer partition of n.
Original entry on oeis.org
1, 2, 9, 69, 623, 7793, 110430, 1906317, 36833614, 816101825, 19925210834, 541363267613, 15997458049946, 515769374925576, 17905023985615254, 669030297769291562, 26689471638523499483, 1134895275721374771655, 51161002326406795249910, 2440166138715867838359915
Offset: 1
The a(3) = 9 trees:
(1(11)), (111),
(1(12)), (2(11)), (112),
(1(23)), (2(13)), (3(12)), (123).
-
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]]]];
gro[m_]:=If[Length[m]==1,m,Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])]];
Table[Sum[Length[gro[m]],{m,Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n]}],{n,4}]
-
\\ See A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n)); v[1]=sv(1); for(n=2, #v, v[n] = polcoef( sExp(x*Ser(v[1..n])), n )); x*Ser(v)}
StronglyNormalLabelingsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Jan 04 2021
A316655
Number of series-reduced rooted trees whose leaves span an initial interval of positive integers with multiplicities the integer partition with Heinz number n.
Original entry on oeis.org
0, 1, 1, 1, 2, 3, 5, 4, 12, 9, 12, 17, 33, 29, 44, 26, 90, 90, 261, 68, 168, 93, 766, 144, 197, 307, 575, 269, 2312, 428, 7068, 236, 625, 1017, 863, 954, 21965, 3409, 2342, 712
Offset: 1
Sequence of sets of trees begins:
1:
2: 1
3: (11)
4: (12)
5: (1(11)), (111)
6: (1(12)), (2(11)), (112)
7: (1(1(11))), (1(111)), ((11)(11)), (11(11)), (1111)
8: (1(23)), (2(13)), (3(12)), (123)
9: (1(1(22))), (1(2(12))), (1(122)), (2(1(12))), (2(2(11))), (2(112)), ((11)(22)), ((12)(12)), (11(22)), (12(12)), (22(11)), (1122)
Cf.
A000081,
A000311,
A000669,
A001678,
A005804,
A056239,
A141268,
A181821,
A292504,
A296150,
A300660,
A304660.
-
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]]]];
gro[m_]:=If[Length[m]==1,m,Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])]];
Table[Length[gro[Flatten[MapIndexed[Table[#2,{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]]]]],{n,20}]
A316694
Number of lone-child-avoiding locally disjoint rooted identity trees whose leaves form an integer partition of n.
Original entry on oeis.org
1, 1, 2, 3, 6, 13, 28, 62, 143, 338, 804, 1948, 4789, 11886, 29796, 75316, 191702, 491040, 1264926, 3274594, 8514784, 22229481, 58243870
Offset: 1
The a(7) = 28 rooted trees:
7,
(16),
(25),
(1(15)),
(34),
(1(24)), (2(14)), (4(12)), (124),
(1(1(14))),
(3(13)),
(2(23)),
(1(1(23))), (1(2(13))), (1(3(12))), (1(123)), (2(1(13))), (3(1(12))), (12(13)), (13(12)),
(1(1(1(13)))),
(2(2(12))),
(1(1(2(12)))), (1(2(1(12)))), (1(12(12))), (2(1(1(12)))), (12(1(12))),
(1(1(1(1(12))))).
Missing from this list but counted by A300660 are ((12)(13)) and ((12)(1(12))).
The semi-identity tree version is
A212804.
Not requiring local disjointness gives
A300660.
The non-identity tree version is
A316696.
This is the case of
A331686 where all leaves are singletons.
Locally disjoint rooted identity trees are
A316471.
Lone-child-avoiding locally disjoint rooted trees are
A331680.
Locally disjoint enriched identity p-trees are
A331684.
-
disjointQ[u_]:=Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];
nms[n_]:=nms[n]=Prepend[Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],And[UnsameQ@@#,disjointQ[#]]&],{ptn,Rest[IntegerPartitions[n]]}],{n}];
Table[Length[nms[n]],{n,10}]
Updated with corrected terminology by
Gus Wiseman, Feb 06 2020
A316656
Number of series-reduced rooted identity trees whose leaves span an initial interval of positive integers with multiplicities the integer partition with Heinz number n.
Original entry on oeis.org
0, 1, 0, 1, 0, 1, 0, 4, 3, 1, 0, 9, 0, 1, 6, 26, 0, 36, 0, 16, 10, 1, 0, 92, 21, 1, 197, 25, 0, 100, 0, 236, 15, 1, 53, 474
Offset: 1
Sequence of sets of trees begins:
1:
2: 1
3:
4: (12)
5:
6: (1(12))
7:
8: (1(23)), (2(13)), (3(12)), (123)
9: (1(2(12))), (2(1(12))), (12(12))
10: (1(1(12)))
11:
12: (1(1(23))), (1(2(13))), (1(3(12))), (1(123)), (2(1(13))), (3(1(12))), ((12)(13)), (12(13)), (13(12))
Cf.
A000081,
A000311,
A000669,
A001678,
A004111,
A005804,
A056239,
A141268,
A181821,
A292504,
A296150,
A300660,
A304660.
-
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]]]];
gro[m_]:=If[Length[m]==1,m,Select[Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])],UnsameQ@@#&]];
Table[Length[gro[Flatten[MapIndexed[Table[#2,{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]]]]],{n,30}]
A316654
Number of series-reduced rooted identity trees whose leaves span an initial interval of positive integers with multiplicities an integer partition of n.
Original entry on oeis.org
1, 1, 5, 39, 387, 4960, 74088, 1312716, 26239484, 595023510, 14908285892, 412903136867, 12448252189622, 407804188400373, 14380454869464352, 544428684832123828, 21991444994187529639, 945234507638271696504, 43042162953650721470752, 2071216980365429970912347
Offset: 1
The a(3) = 5 trees are (1(12)), (1(23)), (2(13)), (3(12)), (123).
Cf.
A000081,
A000311,
A000669,
A001678,
A004111,
A005804,
A141268,
A181821,
A292504,
A300660,
A304660.
-
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]]]];
gro[m_]:=If[Length[m]==1,m,Select[Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])],UnsameQ@@#&]];
Table[Sum[Length[gro[m]],{m,Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n]}],{n,5}]
-
\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n)); v[1]=sv(1); for(n=2, #v, v[n]=polcoef(sWeighT(x*Ser(v[1..n])), n)); x*Ser(v)}
StronglyNormalLabelingsSeq(cycleIndexSeries(12)) \\ Andrew Howroyd, Jan 22 2021
A316766
Number of series-reduced locally stable rooted identity trees whose leaves form an integer partition of n.
Original entry on oeis.org
1, 1, 2, 3, 6, 13, 30, 72, 180, 458, 1194, 3160, 8459, 22881, 62417, 171526, 474405, 1319395, 3687711, 10352696, 29178988
Offset: 1
The a(6) = 13 trees:
6,
(15),
(1(14)),
(1(1(13))),
(1(1(1(12)))),
(1(23)), (2(13)), (3(12)), (123),
(1(2(12))), (2(1(12))), (12(12)),
(24).
Example of non-stable trees are ((12)(123)) and ((12)(12(12))).
Cf.
A000081,
A000669,
A001678,
A004111,
A141268,
A292504,
A300660,
A316467,
A316474,
A316653,
A316654,
A316656.
-
submultisetQ[M_,N_]:=Or[Length[M]==0,MatchQ[{Sort[List@@M],Sort[List@@N]},{{x_,Z___},{_,x_,W___}}/;submultisetQ[{Z},{W}]]];
stableQ[u_]:=Apply[And,Outer[#1==#2||!submultisetQ[#1,#2]&&!submultisetQ[#2,#1]&,u,u,1],{0,1}];
nms[n_]:=nms[n]=Prepend[Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],And[UnsameQ@@#,stableQ[#]]&],{ptn,Rest[IntegerPartitions[n]]}],{n}];
Table[Length[nms[n]],{n,10}]
Showing 1-9 of 9 results.
Comments