A316654 -id:A316654

Search: a316654 -id:a316654

Displaying 1-9 of 9 results found.

page 1

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.

+10
37

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

From Gus Wiseman, Jul 31 2018 and Feb 06 2020: (Start)

a(n) is the number of lone-child-avoiding rooted identity trees whose leaves form an integer partition of n. For example, the following are the a(6) = 13 lone-child-avoiding rooted identity trees whose leaves form an integer partition of 6.

(15),

(24),

(123), (1(23)), (2(13)), (3(12)),

(1(14)),

(1(1(13))),

(12(12)), (1(2(12))), (2(1(12))),

(1(1(1(12)))).

(End)

LINKS

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

Wikipedia, Phylogenetic tree

Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

FORMULA

a(n) ~ c * d^n / n^(3/2), where d = 3.045141208159736483720243229947630323380565686... and c = 0.2004129296838557718008171812000512670126... - Vaclav Kotesovec, Aug 27 2018

EXAMPLE

: 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)

MAPLE

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);

MATHEMATICA

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 *)

CROSSREFS

Cf. A000081, A004111, A141268, A289501, A301467.

Cf. A000669, A001678, A005804, A292504, A300660, A316653, A316654, A316656.

The locally disjoint case is A316694.

Cf. A276625, A306200, A319312, A331679, A331686, A331875.

KEYWORD

nonn,eigen

AUTHOR

Alois P. Heinz, Jun 18 2018

STATUS

approved

A319312

Number of series-reduced rooted trees whose leaves are integer partitions whose multiset union is an integer partition of n.

+10
37

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Also the number of orderless tree-factorizations of Heinz numbers of integer partitions of n.

Also the number of phylogenetic trees on a multiset of labels summing to n.

LINKS

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

EXAMPLE

The a(3) = 7 trees:

(3) (21) (111)

((1)(2)) ((1)(11))

((1)(1)(1))

((1)((1)(1)))

MATHEMATICA

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}]

PROG

(PARI) 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

CROSSREFS

Cf. A000081, A000311, A000669, A001678, A005804, A141268, A292504, A300660, A316653, A316654, A316656.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Sep 17 2018

EXTENSIONS

Terms a(14) and beyond from Andrew Howroyd, Sep 18 2018

STATUS

approved

A316651

Number of series-reduced rooted trees with n leaves spanning an initial interval of positive integers.

+10
30

1, 2, 12, 112, 1444, 24086, 492284, 11910790, 332827136, 10546558146, 373661603588, 14636326974270, 628032444609396, 29296137817622902, 1476092246351259964, 79889766016415899270, 4622371378514020301740, 284719443038735430679268, 18601385258191195218790756

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

A rooted tree is series-reduced if every non-leaf node has at least two branches.

LINKS

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

FORMULA

From Vaclav Kotesovec, Sep 18 2019: (Start)

a(n) ~ c * d^n * n^(n-1), where d = 1.37392076830840090205551979... and c = 0.41435722857311602982846...

a(n) ~ 2*log(2)*A326396(n)/n. (End)

EXAMPLE

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).

MAPLE

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

MATHEMATICA

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 *)

PROG

(PARI) \\ 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

CROSSREFS

Cf. A000081, A000311, A000669, A001678, A005804, A034691, A141268, A292504.

Cf. A316652, A316653, A316654, A316655, A316656, A319369.

Row sums of A319376.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Jul 09 2018

EXTENSIONS

Terms a(9) and beyond from Andrew Howroyd, Sep 14 2018

STATUS

approved

A316652

Number of series-reduced rooted trees whose leaves span an initial interval of positive integers with multiplicities an integer partition of n.

+10
25

1, 2, 9, 69, 623, 7793, 110430, 1906317, 36833614, 816101825, 19925210834, 541363267613, 15997458049946, 515769374925576, 17905023985615254, 669030297769291562, 26689471638523499483, 1134895275721374771655, 51161002326406795249910, 2440166138715867838359915

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

A rooted tree is series-reduced if every non-leaf node has at least two branches.

LINKS

Table of n, a(n) for n=1..20.

EXAMPLE

The a(3) = 9 trees:

(1(11)), (111),

(1(12)), (2(11)), (112),

(1(23)), (2(13)), (3(12)), (123).

MATHEMATICA

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}]

PROG

(PARI) \\ 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

CROSSREFS

Cf. A000081, A000311, A000669, A001678, A005804, A141268, A181821, A292504, A304660.

Cf. A316651, A316653, A316654, A316655, A316656.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Jul 09 2018

EXTENSIONS

Terms a(10) and beyond from Andrew Howroyd, Jan 04 2021

STATUS

approved

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.

+10
16

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,5

COMMENTS

A rooted tree is series-reduced if every non-leaf node has at least two branches.

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

LINKS

Table of n, a(n) for n=1..40.

FORMULA

a(prime(n)) = A000669(n).

a(2^n) = A000311(n).

EXAMPLE

Sequence of sets of trees begins:

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)

MATHEMATICA

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}]

CROSSREFS

Cf. A000081, A000311, A000669, A001678, A005804, A056239, A141268, A181821, A292504, A296150, A300660, A304660.

Cf. A316651, A316652, A316653, A316654, A316656.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jul 09 2018

EXTENSIONS

a(37)-a(40) from Robert Price, Sep 13 2018

STATUS

approved

A316694

Number of lone-child-avoiding locally disjoint rooted identity trees whose leaves form an integer partition of n.

+10
16

1, 1, 2, 3, 6, 13, 28, 62, 143, 338, 804, 1948, 4789, 11886, 29796, 75316, 191702, 491040, 1264926, 3274594, 8514784, 22229481, 58243870

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

A rooted tree is lone-child-avoiding if every non-leaf node has at least two branches. It is locally disjoint if no branch overlaps any other (unequal) branch of the same root. It is an identity tree if no branch appears multiple times under the same root.

LINKS

Table of n, a(n) for n=1..23.

Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

EXAMPLE

The a(7) = 28 rooted trees:

(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))).

MATHEMATICA

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}]

CROSSREFS

Cf. A000081, A000669, A001678, A141268, A292504, A316653, A316654, A316656.

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.

Rooted identity trees are A004111.

Locally disjoint rooted identity trees are A316471.

Lone-child-avoiding locally disjoint rooted trees are A331680.

Locally disjoint enriched identity p-trees are A331684.

Cf. A306200, A316697, A331678, A331679, A331681, A331683, A331783, A331874.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jul 10 2018

EXTENSIONS

a(21)-a(23) from Robert Price, Sep 16 2018

Updated with corrected terminology by Gus Wiseman, Feb 06 2020

STATUS

approved

A316653

Number of series-reduced rooted identity trees with n leaves spanning an initial interval of positive integers.

+10
10

1, 1, 6, 58, 774, 13171, 272700, 6655962, 187172762, 5959665653, 211947272186, 8327259067439, 358211528524432, 16744766791743136, 845195057333580332, 45814333121920927067, 2654330505021077873594, 163687811930206581162063, 10705203621191765328300832

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

A rooted tree is series-reduced if every non-leaf node has at least two branches. It is an identity tree if no branch appears multiple times under the same root.

LINKS

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

EXAMPLE

The a(3) = 6 trees are (1(12)), (2(12)), (1(23)), (2(13)), (3(12)), (123).

MATHEMATICA

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@@#&]];

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}]

PROG

(PARI) \\ here R(n, 2) is A031148.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}

R(n, k)={my(v=[k]); for(n=2, n, v=concat(v, WeighT(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

CROSSREFS

Cf. A000081, A000311, A000669, A001678, A004111, A005804, A034691, A141268, A292504, A300660.

Cf. A316651, A316652, A316654, A316655, A316656.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Jul 09 2018

EXTENSIONS

Terms a(9) and beyond from Andrew Howroyd, Sep 14 2018

STATUS

approved

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.

+10
10

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,8

COMMENTS

A rooted tree is series-reduced if every non-leaf node has at least two branches. It is an identity tree if no branch appears multiple times under the same root.

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

LINKS

Table of n, a(n) for n=1..36.

FORMULA

a(prime(n>1)) = 0.

a(2^n) = A000311(n).

EXAMPLE

Sequence of sets of trees begins:

2: 1

4: (12)

6: (1(12))

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))

MATHEMATICA

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}]

CROSSREFS

Cf. A000081, A000311, A000669, A001678, A004111, A005804, A056239, A141268, A181821, A292504, A296150, A300660, A304660.

Cf. A316651, A316652, A316653. A316654, A316655.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jul 09 2018

STATUS

approved

A316766

Number of series-reduced locally stable rooted identity trees whose leaves form an integer partition of n.

+10
0

1, 1, 2, 3, 6, 13, 30, 72, 180, 458, 1194, 3160, 8459, 22881, 62417, 171526, 474405, 1319395, 3687711, 10352696, 29178988

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

A rooted tree is series-reduced if every non-leaf node has at least two branches. It is locally stable if no branch is a submultiset of any other branch of the same root. It is an identity tree if no branch appears multiple times under the same root.

LINKS

Table of n, a(n) for n=1..21.

EXAMPLE

The a(6) = 13 trees:

(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))).

MATHEMATICA

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}]

CROSSREFS

Cf. A000081, A000669, A001678, A004111, A141268, A292504, A300660, A316467, A316474, A316653, A316654, A316656.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jul 12 2018

EXTENSIONS

a(18)-a(21) from Robert Price, Sep 14 2018

STATUS

approved

page 1

Search completed in 0.010 seconds