A301364 -id:A301364 - 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

A301368 Regular triangle where T(n,k) is the number of binary enriched p-trees of weight n with k leaves.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 3, 2, 1, 2, 4, 5, 3, 1, 3, 7, 12, 12, 6, 1, 3, 9, 19, 28, 25, 11, 1, 4, 14, 36, 65, 81, 63, 24, 1, 4, 16, 48, 107, 172, 193, 136, 47, 1, 5, 22, 75, 192, 369, 522, 522, 331, 103, 1, 5, 25, 96, 284, 643, 1108, 1420, 1292, 750, 214, 1, 6

Offset: 1

Gus Wiseman, Mar 19 2018

A binary enriched p-tree of weight n is either a single node of weight n, or an ordered pair of binary enriched p-trees with weakly decreasing weights summing to n.

			Triangle begins:
  1
  1   1
  1   1   1
  1   2   3   2
  1   2   4   5   3
  1   3   7  12  12   6
  1   3   9  19  28  25  11
  1   4  14  36  65  81  63  24
  1   4  16  48 107 172 193 136  47
  1   5  22  75 192 369 522 522 331 103
  ...
The T(6,3) = 7 binary enriched p-trees: ((41)1), ((32)1), (4(11)), ((31)2), ((22)2), (3(21)), ((21)3).

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

Last entries of each row give A000992. Row sums are A300443.

Cf. A001190, A008284, A055277, A063834, A196545, A273873, A289501, A292050, A298422, A298426, A300354, A300439, A300442, A301344, A301364-A301367.

bintrees[n_]:=Prepend[Join@@Table[Tuples[bintrees/@ptn],{ptn,Select[IntegerPartitions[n],Length[#]===2&]}],n];
Table[Length[Select[bintrees[n],Count[#,_Integer,{-1}]===k&]],{n,13},{k,n}]

A(n)={my(v=vector(n)); for(n=1, n, v[n] = y + sum(k=1, n\2, v[k]*v[n-k])); apply(p->Vecrev(p/y), v)}
{ my(T=A(10)); for(n=1, #T, print(T[n])) } \\ Andrew Howroyd, Aug 26 2018

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.

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.

A301365 Regular triangle where T(n,k) is the number of strict trees of weight n with k leaves.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 4, 4, 1, 0, 1, 3, 7, 9, 7, 1, 0, 1, 3, 10, 19, 20, 11, 1, 0, 1, 4, 15, 35, 51, 43, 16, 1, 0, 1, 4, 18, 55, 104, 123, 84, 22, 1, 0, 1, 5, 25, 84, 196, 298, 284, 153, 29, 1, 0, 1, 5, 30, 120, 331, 624, 783, 614, 260, 37

Offset: 1

Gus Wiseman, Mar 19 2018

A strict tree of weight n > 0 is either a single node of weight n, or a finite sequence of two or more strict trees with strictly decreasing weights summing to n.

			Triangle begins:
  1
  1   0
  1   1   0
  1   1   1   0
  1   2   2   1   0
  1   2   4   4   1   0
  1   3   7   9   7   1   0
  1   3  10  19  20  11   1   0
  1   4  15  35  51  43  16   1   0
The T(7,3) = 7 strict trees: ((51)1), ((42)1), ((41)2), ((32)2), (4(21)), ((31)3), (421).

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

Row sums are A273873.

Cf. A004111, A008284, A032305, A055277, A063834, A281145, A289501, A294018, A294079, A300352, A300442, A300443, A301342, A301364-A301368.

strtrees[n_]:=Prepend[Join@@Table[Tuples[strtrees/@ptn],{ptn,Select[IntegerPartitions[n],Length[#]>1&&UnsameQ@@#&]}],n];
Table[Length[Select[strtrees[n],Count[#,_Integer,{-1}]===k&]],{n,12},{k,n}]

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

A301367 Regular triangle where T(n,k) is the number of orderless same-trees of weight n with k leaves.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 1, 2, 1, 0, 0, 0, 1, 1, 1, 1, 2, 1, 3, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 4, 4, 3, 5, 1, 0, 1, 0, 1, 0, 1, 0, 2, 1, 1, 0, 0, 1, 2, 1, 1, 1, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 4, 5, 10, 11, 14, 12, 14, 7, 13, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1

Offset: 1

Gus Wiseman, Mar 19 2018

An orderless same-tree of weight n > 0 is either a single node of weight n, or a finite multiset of two or more orderless same-trees whose weights are all the same and sum to n.

			Triangle begins:
1
1   1
1   0   1
1   1   1   2
1   0   0   0   1
1   1   1   2   1   3
1   0   0   0   0   0   1
1   1   1   3   4   4   3   5
1   0   1   0   1   0   1   0   2
1   1   0   0   1   2   1   1   1   3
1   0   0   0   0   0   0   0   0   0   1
1   1   2   4   5  10  11  14  12  14   7  13
1   0   0   0   0   0   0   0   0   0   0   0   1
1   1   0   0   0   0   1   2   1   1   1   1   1   3
The T(8,5) = 4 orderless same-trees: (4((11)(11))), (4(1111)), ((22)(2(11))), (222(11)).

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

Last entries of each row give A289079. Row sums are A289078.

Cf. A003238, A006241, A008284, A055277, A063834, A273873, A281145, A289501, A294080, A298422, A298426, A299201, A299203, A301343, A301364-A301368.

olstrees[n_]:=Prepend[Join@@Table[Select[Tuples[olstrees/@ptn],OrderedQ],{ptn,Select[IntegerPartitions[n],Length[#]>1&&SameQ@@#&]}],n];
Table[Length[Select[olstrees[n],Count[#,_Integer,{-1}]===k&]],{n,14},{k,n}]

S(g, k)={polcoef(exp(sum(i=1, k, x^i*subst(g, y, y^i)/i) + O(x*x^k)), k)}
A(n)={my(v=vector(n)); for(n=1, n, v[n] = y + sumdiv(n, d, S(v[n/d], d))); apply(p -> Vecrev(p/y), v)}
{ my(v=A(16)); for(n=1, #v, print(v[n])) } \\ Andrew Howroyd, Aug 20 2018

A301366 Regular triangle where T(n,k) is the number of same-trees of weight n with k leaves.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 2, 2, 1, 0, 0, 0, 1, 1, 1, 1, 5, 3, 3, 1, 0, 0, 0, 0, 0, 1, 1, 1, 2, 6, 12, 14, 12, 6, 1, 0, 1, 0, 3, 0, 3, 0, 2, 1, 1, 0, 0, 1, 7, 10, 10, 5, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 3, 7, 21, 41, 58, 100, 100, 94, 48, 20

Offset: 1

Gus Wiseman, Mar 19 2018

A same-tree of weight n > 0 is either a single node of weight n, or a finite sequence of two or more same-trees whose weights are all the same and sum to n.

			Triangle begins:
1
1   1
1   0   1
1   1   2   2
1   0   0   0   1
1   1   1   5   3   3
1   0   0   0   0   0   1
1   1   2   6  12  14  12   6
1   0   1   0   3   0   3   0   2
1   1   0   0   1   7  10  10   5   3
1   0   0   0   0   0   0   0   0   0   1
1   1   3   7  21  41  58 100 100  94  48  20
The T(8,4) = 6 same-trees: (4(2(11))), (4((11)2)), ((22)(22)), ((2(11))4), (((11)2)4), (2222).

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

Last entries of each row give A006241. Row sums are A281145.

Cf. A003238, A008284, A055277, A063834, A273873, A289501, A294080, A298422, A298426, A299201, A299203, A300442, A300443, A301343, A301364-A301368.

sametrees[n_]:=Prepend[Join@@Table[Tuples[sametrees/@ptn],{ptn,Select[IntegerPartitions[n],Length[#]>1&&SameQ@@#&]}],n];
Table[Length[Select[sametrees[n],Count[#,_Integer,{-1}]===k&]],{n,12},{k,n}]

A(n)={my(v=vector(n)); for(n=1, n, v[n] = x + sumdiv(n, d, v[n/d]^d)); apply(p -> Vecrev(p/x), v)}
{my(v=A(16)); for(n=1, #v, print(v[n]))} \\ Andrew Howroyd, Aug 20 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

A301368 Regular triangle where T(n,k) is the number of binary enriched p-trees of weight n with k leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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

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.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A301365 Regular triangle where T(n,k) is the number of strict trees of weight n with k leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A301367 Regular triangle where T(n,k) is the number of orderless same-trees of weight n with k leaves.

Views

Author