A301467 -id:A301467 - cp's OEIS frontend

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.

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

Alois P. Heinz, Jun 18 2018

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

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

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

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.

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

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

A301462 Number of enriched r-trees of size n.

Original entry on oeis.org

1, 2, 3, 8, 23, 77, 254, 921, 3249, 12133, 44937, 172329, 654895, 2565963, 9956885, 39536964, 156047622, 626262315, 2499486155, 10129445626, 40810378668, 166475139700, 676304156461, 2775117950448, 11342074888693, 46785595997544, 192244951610575, 796245213910406

Offset: 0

Gus Wiseman, Mar 21 2018

nonn

An enriched r-tree of size n > 0 is either a single node of size n, or a finite sequence of enriched r-trees with weakly decreasing sizes summing to n - 1.

These are different from the R-trees of data science and the enriched R-trees of Bousquet-Mélou and Courtiel.

			The a(3) = 8 enriched r-trees: 3, (2), ((1)), ((())), (11), (1()), (()1), (()()).

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

Cf. A000081, A003238, A004111, A032305, A055277, A093637, A127524, A196545, A289501, A290689, A300443, A301342-A301345, A301364-A301368, A301422, A301467, A301469, A301470.

ert[n_]:=ert[n]=1+Sum[Times@@ert/@y,{y,IntegerPartitions[n-1]}];
Array[ert,30]

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + polcoef(1/prod(k=1, n-1, 1 - v[k]*x^k + O(x^n)), n-1)); concat([1], v)} \\ Andrew Howroyd, Aug 26 2018

O.g.f.: 1/(1 - x) + x Product_{i > 0} 1/(1 - a(i) x^i).

A301480 Number of rooted twice-partitions of n.

Original entry on oeis.org

1, 1, 2, 4, 8, 15, 30, 54, 103, 186, 345, 606, 1115, 1936, 3466, 6046, 10630, 18257, 31927, 54393, 93894, 159631, 272155, 458891, 779375, 1305801, 2196009, 3667242, 6130066, 10170745, 16923127, 27942148, 46211977, 76039205, 125094369, 204952168, 335924597

Offset: 1

Gus Wiseman, Mar 22 2018

nonn

A rooted partition of n is an integer partition of n - 1. A rooted twice-partition of n is a choice of a rooted partition of each part in a rooted partition of n.

			The a(5) = 8 rooted twice-partitions: ((3)), ((21)), ((111)), ((2)()), ((11)()), ((1)(1)), ((1)()()), (()()()()).
The a(6) = 15 rooted twice-partitions:
(4), (31), (22), (211), (1111),
(3)(), (21)(), (111)(), (2)(1), (11)(1),
(2)()(), (11)()(), (1)(1)(),
(1)()()(),
()()()()().

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

Cf. A001383, A002865, A032305, A063834, A093637, A127524, A196545, A220418, A281113, A289501, A301422, A301462, A301467.

nn=30;
ser=x*Product[1/(1-PartitionsP[n-1]x^n),{n,nn}];
Table[SeriesCoefficient[ser,{x,0,n}],{n,nn}]

seq(n)={Vec(1/prod(k=1, n-1, 1 - numbpart(k-1)*x^k + O(x^n)))} \\ Andrew Howroyd, Aug 29 2018

O.g.f.: x * Product_{n > 0} 1/(1 - P(n-1) x^n) where P = A000041.

A300486 Number of relatively prime or monic partitions of n.

Original entry on oeis.org

1, 2, 3, 4, 7, 8, 15, 18, 28, 35, 56, 64, 101, 120, 168, 210, 297, 348, 490, 583, 776, 946, 1255, 1482, 1952, 2335, 2981, 3581, 4565, 5387, 6842, 8119, 10086, 12013, 14863, 17527, 21637, 25525, 31083, 36695, 44583, 52256, 63261, 74171, 88932, 104303, 124754

Offset: 1

Gus Wiseman, Apr 15 2018

nonn

A relatively prime or monic partition of n is an integer partition of n that is either of length 1 (monic) or whose parts have no common divisor other than 1 (relatively prime).

			The a(6) = 8 relatively prime or monic partitions are (6), (51), (411), (321), (3111), (2211), (21111), (111111). Missing from this list are (42), (33), (222).

Andrew Howroyd, Table of n, a(n) for n = 1..1000
A. David Christopher and M. Davamani Christober, Relatively Prime Uniform Partitions, Gen. Math. Notes, Vol. 13, No. 2, December, 2012, pp. 1-12.

Cf. A000837, A001383, A063834, A093637, A196545, A281113, A289501, A300383, A301462, A301467, A301480, A302094, A302698, A302915, A302916, A302917.

Table[Length[Select[IntegerPartitions[n],Or[Length[#]===1,GCD@@#===1]&]],{n,20}]

a(n)={(n > 1) + sumdiv(n, d, moebius(d)*numbpart(n/d))} \\ Andrew Howroyd, Aug 29 2018

a(n > 1) = 1 + A000837(n) = 1 + Sum_{d|n} mu(d) * A000041(n/d).

A301706 Number of rooted thrice-partitions of n.

Original entry on oeis.org

1, 1, 2, 4, 9, 19, 43, 91, 201, 422, 918, 1896, 4089, 8376, 17793, 36445, 76446, 155209, 324481, 655426, 1355220, 2741092, 5617505, 11291037, 23086423, 46227338, 93753196, 187754647, 378675055, 754695631, 1518414812, 3016719277, 6037006608, 11984729983

Offset: 1

Gus Wiseman, Mar 25 2018

nonn

A rooted partition of n is an integer partition of n - 1. A rooted twice-partition of n is a choice of a rooted partition of each part in a rooted partition of n. A rooted thrice-partition of n is a choice of a rooted twice-partition of each part in a rooted partition of n.

			The a(5) = 9 rooted thrice-partitions:
((2)), ((11)), ((1)()), (()()()),
((1))(), (()())(), (())(()),
(())()(),
()()()().
The a(6) = 19 rooted thrice-partitions:
((3)), ((21)), ((111)), ((2)()), ((11)()), ((1)(1)), ((1)()()), (()()()()),
((2))(), ((11))(), ((1)())(), (()()())(), ((1))(()), (()())(()),
((1))()(), (()())()(), (())(())(),
(())()()(),
()()()()().

Cf. A000041, A001383, A002865, A063834, A093637, A119442, A196545, A281113, A289501, A300383, A301422, A301462, A301467, A301480, A301595, A301598.

twire[n_]:=twire[n]=Sum[Times@@PartitionsP/@(ptn-1),{ptn,IntegerPartitions[n-1]}];
thrire[n_]:=Sum[Times@@twire/@ptn,{ptn,IntegerPartitions[n-1]}];
Array[thrire,30]

A301470 Signed recurrence over enriched r-trees: a(n) = (-1)^n + Sum_y Product_{i in y} a(y) where the sum is over all integer partitions of n - 1.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 2, 3, 5, 9, 15, 27, 47, 87, 155, 288, 524, 983, 1813, 3434, 6396, 12174, 22891, 43810, 82925, 159432, 303559, 585966, 1121446, 2171341, 4172932, 8106485, 15635332, 30445899, 58925280, 115014681, 223210718, 436603718, 849480835, 1664740873

Offset: 0

Gus Wiseman, Mar 21 2018

nonn

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

Cf. A032305, A055277, A093637, A127524, A196545, A220418, A273866, A273873, A289501, A290261, A290971, A301342-A301345, A301364-A301368, A301422, A301462, A301467, A301469.

b:= proc(n, i) option remember; `if`(n=0, 1,
     `if`(i<1, 0, b(n, i-1)+a(i)*b(n-i, min(n-i, i))))
    end:
a:= n-> `if`(n<2, 1-n, b(n-2$2)+b(n-1, n-2)):
seq(a(n), n=0..45);  # Alois P. Heinz, Jun 23 2018

a[n_]:=a[n]=(-1)^n+Sum[Times@@a/@y,{y,IntegerPartitions[n-1]}];
Array[a,30]
(* Second program: *)
b[n_, i_] := b[n, i] = If[n == 0, 1,
     If[i < 1, 0, b[n, i - 1] + a[i] b[n - i, Min[n - i, i]]]];
a[n_] := If[n < 2, 1 - n, b[n - 2, n - 2] + b[n - 1, n - 2]];
a /@ Range[0, 45] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)

O.g.f.: 1/(1 + x) + x Product_{i > 0} 1/(1 - a(i) x^i).

a(n) = Sum_t (-1)^w(t) where the sum is over all enriched r-trees of size n and w(t) is the sum of leaves of t.

A301764 Number of ways to choose a constant rooted partition of each part in a constant rooted partition of n such that the flattened sequence is also constant.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Mar 26 2018

nonn

A rooted partition of n is an integer partition of n - 1.

			The a(11) = 8 rooted twice-partitions: (9), (333), (111111111), (4)(4), (22)(22), (1111)(1111), (1)(1)(1)(1)(1), ()()()()()()()()()().

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

Cf. A002865, A007425, A063834, A093637, A127524, A295931, A300383, A301422, A301462, A301467, A301480, A301706.

Table[If[n===1,1,DivisorSum[n-1,If[#===1,1,DivisorSigma[0,#-1]]&]],{n,100}]

a(n)=if(n==1, 1, sumdiv(n-1, d, if(d==1, 1, numdiv(d-1)))) \\ Andrew Howroyd, Aug 26 2018

A302094 Number of relatively prime or monic twice-partitions of n.

Original entry on oeis.org

1, 3, 6, 10, 27, 35, 113, 170, 396, 641, 1649, 2318, 5905, 9112, 18678, 32529, 69094, 106210, 227480, 363433, 705210, 1196190, 2325023, 3724233, 7192245, 11915884, 21857887, 36597843, 67406158, 109594872, 201747847, 333400746, 591125465, 987069077, 1743223350

Offset: 1

Gus Wiseman, Apr 15 2018

nonn

A relatively prime or monic partition of n is an integer partition of n that is either of length 1 (monic) or whose parts have no common divisor other than 1 (relatively prime). Then a relatively prime or monic twice-partition of n is a choice of a relatively prime or monic partition of each part in a relatively prime or monic partition of n.

			The a(4) = 10 relatively prime or monic twice-partitions:
(4), (31), (211), (1111),
(3)(1), (21)(1), (111)(1),
(2)(1)(1), (11)(1)(1),
(1)(1)(1)(1).

A. David Christopher and M. Davamani Christober, Relatively Prime Uniform Partitions, Gen. Math. Notes, Vol. 13, No. 2, December, 2012, pp. 1-12.

Cf. A000837, A001383, A063834, A093637, A196545, A281113, A289501, A300383, A300486, A301462, A301467, A301480, A302915, A302916, A302917.

ip[n_]:=ip[n]=Select[IntegerPartitions[n],Or[Length[#]===1,GCD@@#===1]&];
Table[Sum[Times@@Length/@ip/@ptn,{ptn,ip[n]}],{n,10}]

A302915 Number of relatively prime enriched p-trees of weight n.

Original entry on oeis.org

1, 2, 4, 8, 28, 56, 256, 656, 2480, 6688, 30736, 73984, 366560, 1006720, 3966976, 12738560, 58427648, 148069632, 764473600, 2133585664, 8939502080, 28705390592, 136987259648, 356634376704, 1780025034240, 5455065263104, 23215437079552, 73123382895616

Offset: 1

Gus Wiseman, Apr 15 2018

nonn

A relatively prime enriched p-tree of weight n is either a single node of weight n, or a finite sequence of two or more relatively prime enriched p-trees whose weights are weakly decreasing, relatively prime, and sum to n.

			The a(4) = 8 relatively prime enriched p-trees are 4, (31), ((21)1), (((11)1)1), ((111)1), (211), ((11)11), (1111). Missing from this list are the enriched p-trees ((11)(11)), ((11)2), (2(11)), (22).

Cf. A000081, A000837, A003238, A004111, A055277, A093637, A196545, A289501, A290689, A300486, A301462, A301467, A302094, A302916, A302917.

a[n_]:=a[n]=1+Sum[Times@@a/@y,{y,Rest[Select[IntegerPartitions[n],Or[Length[#]===1,GCD@@#===1]&]]}];
Array[a,20]

A302916 Number of relatively prime p-trees of weight n.

Original entry on oeis.org

1, 1, 2, 4, 11, 22, 74, 174, 530, 1302, 4713, 10639, 40877, 101795, 325609, 925733, 3432819, 8078511, 32542036, 82226383, 279096823, 795532677, 3066505569, 7374764180, 28946183035, 79313174765, 275507514909, 772692247626, 3049937788372, 7071057261148

Offset: 1

Gus Wiseman, Apr 15 2018

nonn

A relatively prime p-tree of weight n is either a single node, or a finite sequence of two or more relatively prime p-trees whose weights are weakly decreasing, relatively prime, and sum to n.

			The a(4) = 4 relatively prime p-trees are (((oo)o)o), ((ooo)o), ((oo)oo), (oooo). Missing from this list is the p-tree ((oo)(oo)).

Cf. A000081, A000837, A003238, A004111, A055277, A093637, A196545, A289501, A290689, A300486, A301462, A301467, A302094, A302915, A302917.

a[n_]:=a[n]=If[n===1,1,Sum[Times@@a/@y,{y,Rest[Select[IntegerPartitions[n],Or[Length[#]===1,GCD@@#===1]&]]}]];
Array[a,20]

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A301462 Number of enriched r-trees of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A301480 Number of rooted twice-partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A300486 Number of relatively prime or monic partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A301706 Number of rooted thrice-partitions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A301470 Signed recurrence over enriched r-trees: a(n) = (-1)^n + Sum_y Product_{i in y} a(y) where the sum is over all integer partitions of n - 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A301764 Number of ways to choose a constant rooted partition of each part in a constant rooted partition of n such that the flattened sequence is also constant.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A302094 Number of relatively prime or monic twice-partitions of n.