A127524 -id:A127524 - cp's OEIS frontend

A301462 Number of enriched r-trees of size n.

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

A301467 Number of enriched r-trees of size n with no empty subtrees.

Original entry on oeis.org

1, 2, 4, 8, 20, 48, 136, 360, 1040, 2944, 8704, 25280, 76320, 226720, 692992, 2096640, 6470016, 19799936, 61713152, 190683520, 598033152, 1863995392, 5879859200, 18438913536, 58464724992, 184356152832, 586898946048, 1859875518464, 5941384080384, 18901502482432

Offset: 1

Gus Wiseman, Mar 21 2018

nonn

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

			The a(4) = 8 enriched r-trees with no empty subtrees: 4, (3), (21), ((2)), (111), ((11)), ((1)1), (((1))).
The a(5) = 20 enriched r-trees with no empty subtrees:
  5,
  (4), ((3)), ((21)), (((2))), ((111)), (((11))), (((1)1)), ((((1)))),
  (31), (22), (2(1)), ((2)1), ((1)2), ((11)1), ((1)(1)), (((1))1),
  (211), ((1)11),
  (1111).

Alois P. Heinz, Table of n, a(n) for n = 1..1910

Cf. A000081, A004111, A032305, A055277, A093637, A127524, A196545, A289501, A300660, A301342-A301345, A301364-A301368, A301422, A301462, A301469, A301470.

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(b(n-i*j, i-1)* a(i)^j, j=0..n/i)))
    end:
a:= n-> `if`(n<2, n, 1+b(n-1$2)):
seq(a(n), n=1..30);  # Alois P. Heinz, Jun 21 2018

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

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

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

A301422 Regular triangle where T(n,k) is the number of r-trees of size n with k leaves.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 6, 8, 4, 1, 0, 1, 9, 19, 14, 5, 1, 0, 1, 12, 36, 40, 21, 6, 1, 0, 1, 16, 65, 102, 75, 30, 7, 1, 0, 1, 20, 106, 223, 224, 123, 40, 8, 1, 0, 1, 25, 168, 457, 604, 439, 191, 52, 9, 1, 0, 1, 30, 248, 847, 1433, 1346, 764, 276

Offset: 1

Gus Wiseman, Mar 20 2018

An r-tree (A093637) of size n > 0 is a finite sequence of r-trees with weakly decreasing sizes summing to n - 1. This is a similar construction to p-trees (A196545) except that r-trees are not required to be series-reduced and are weighted by all nodes (including the root) rather than just the leaves.

			Triangle begins:
  1
  1   0
  1   1   0
  1   2   1   0
  1   4   3   1   0
  1   6   8   4   1   0
  1   9  19  14   5   1   0
  1  12  36  40  21   6   1   0
  1  16  65 102  75  30   7   1   0
  1  20 106 223 224 123  40   8   1   0
  1  25 168 457 604 439 191  52   9   1   0
  ...
The T(6,3) = 8 r-trees: (((ooo))), (((oo)o)), (((o)oo)), (((oo))o), (((o)o)o), ((oo)(o)), (((o))oo), ((o)(o)o).

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

Cf. A000081, A003238, A004111, A032305, A055277, A093637, A127524, A196545, A289501, A290689, A291443, A297791, A300443, A301342-A301345, A301364.

rtrees[n_]:=Join@@Table[Tuples[rtrees/@y],{y,IntegerPartitions[n-1]}];
Table[Length[Select[rtrees[n],Count[#,{},{-2}]===k&]],{n,8},{k,n}]

A(n)={my(v=vector(n)); v[1]=y; for(n=2, n, v[n] = polcoef(1/prod(k=1, n-1, 1 - v[k]*x^k + O(x^n)), n-1)); vector(n, k, Vecrev(v[k]/y,k))}
{ my(T=A(10)); for(n=1, #T, print(T[n])) } \\ Andrew Howroyd, Aug 26 2018

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.

A127525 Number of ordered rooted trees where each subtree from given node has the same number of nodes.

Original entry on oeis.org

1, 1, 2, 3, 5, 6, 12, 13, 24, 33, 60, 61, 142, 143, 289, 447, 699, 700, 1558, 1559, 3518, 5375, 8977, 8978, 17179, 20305, 40471, 54808, 98182, 98183, 242068, 242069, 477002, 695051, 1183654, 1510612, 2629806, 2629807, 5057173, 7928654, 12366025, 12366026

Offset: 1

Franklin T. Adams-Watters, Jan 17 2007

nonn

			The tree shown below left counts, because the left subtree has 3 nodes and so does the right subtree and a similar condition holds for the subtrees. The tree shown on the right is not counted, because the left subtree has 3 nodes, while the right subtree has 4.
O..........O...O...O
|..........|....\./.
O...O...O..O.....O..
.\...\./....\....|..
.O...O......O...O..
..\./........\./...
...O..........O....

Alois P. Heinz, Table of n, a(n) for n = 1..5590

Cf. A000108, A127524, A007059.

a:= proc(n) option remember; `if`(n<2, n, add(
      a((n-1)/d)^d, d=numtheory[divisors](n-1)))
    end:
seq(a(n), n=1..45);  # Alois P. Heinz, Sep 08 2018

a[1] = 1;
a[n_] := a[n] = Sum[a[(n-1)/d]^d, {d, Divisors[n-1]}];
Array[a, 45] (* Jean-François Alcover, Oct 28 2020 *)

a(1) = 1; a(n+1) = Sum_{d|n} a(n/d)^d.

L.g.f.: -log(Product_{n>=1} (1 - a(n)*x^n)^(1/n)) = Sum_{n>=1} a(n+1)*x^n/n. - Ilya Gutkovskiy, Apr 29 2019

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

A301469 Signed recurrence over enriched r-trees: a(n) = 2 * (-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

2, -1, 1, 0, 0, 1, 0, 1, 1, 1, 2, 3, 3, 6, 7, 11, 17, 23, 35, 53, 75, 119, 173, 264, 398, 603, 911, 1411, 2114, 3279, 4977, 7696, 11760, 18253, 27909, 43451, 66675, 103945, 160096, 249904, 385876, 603107, 933474, 1461967, 2266384, 3553167, 5521053, 8664117, 13485744

Offset: 0

Gus Wiseman, Mar 21 2018

sign

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

a[n_]:=a[n]=2(-1)^n+Sum[Times@@a/@y,{y,IntegerPartitions[n-1]}];
Array[a,30]

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

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

A301750 Number of rooted twice-partitions of n where the composite rooted partition is strict.

Original entry on oeis.org

1, 1, 2, 3, 5, 8, 12, 18, 29, 42, 61, 86, 127, 181, 257, 352, 489, 668, 935, 1270, 1730, 2312, 3101, 4112, 5533, 7345, 9742, 12785, 16793, 21821, 28452, 36908, 48108, 62198, 80337, 103081, 132372, 168805, 215247, 273678

Offset: 1

Gus Wiseman, Mar 26 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(8) = 18 rooted twice-partitions where the composite rooted partition is strict:
(6), (51), (42), (321),
(5)(), (41)(), (32)(), (4)(1), (3)(2),
(4)()(), (31)()(), (3)(1)(),
(3)()()(), (21)()()(), (2)(1)()(),
(2)()()()(),
(1)()()()()(),
()()()()()()().

Cf. A002865, A063834, A093637, A127524, A279790, A294788, A301422, A301462, A301467, A301480, A301706.

twirtns[n_]:=Join@@Table[Tuples[IntegerPartitions[#-1]&/@ptn],{ptn,IntegerPartitions[n-1]}];
Table[Select[twirtns[n],UnsameQ@@Join@@#&]//Length,{n,30}]

A301763 Number of ways to choose a constant rooted partition of each part in a constant rooted partition of n.

Original entry on oeis.org

1, 1, 2, 3, 4, 4, 8, 5, 8, 13, 14, 5, 32, 7, 20, 64, 26, 6, 92, 7, 126, 199, 22, 5, 352, 252, 41, 581, 394, 7, 1832, 9, 292, 2119, 31, 3216, 4946, 10, 40, 8413, 7708, 9, 20656, 9, 2324, 53546, 24, 5, 70040, 16395, 59361, 131204, 9503, 7, 266780, 178180, 82086

Offset: 1

Gus Wiseman, Mar 26 2018

nonn

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

			The a(7) = 8 rooted twice-partitions: (5), (11111), (2)(2), (2)(11), (11)(2), (11)(11), (1)(1)(1), ()()()()()().
The a(15) = 20 rooted twice-partitions:
()()()()()()()()()()()()()(),
(1)(1)(1)(1)(1)(1)(1), (111111)(111111), (1111111111111),
(111111)(222), (222)(111111), (222)(222),
(111111)(33), (222)(33), (33)(111111), (33)(222), (33)(33),
(111111)(6), (222)(6), (33)(6), (6)(111111), (6)(222), (6)(33), (6)(6),
(13).

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

Cf. A000005, A002865, A047968, A063834, A093637, A127524, A295924, A300383, A301422, A301462, A301467, A301480, A301706.

Table[If[n===1,1,Sum[If[d===n-1,1,DivisorSigma[0,(n-1)/d-1]]^d,{d,Divisors[n-1]}]],{n,50}]

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

cp's OEIS Frontend

A301462 Number of enriched r-trees of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A301467 Number of enriched r-trees of size n with no empty subtrees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A301422 Regular triangle where T(n,k) is the number of r-trees of size n with k leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A301480 Number of rooted twice-partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A127525 Number of ordered rooted trees where each subtree from given node has the same number of nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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