A196545 -id:A196545 - cp's OEIS frontend

A299201 Number of twice-partitions whose composite is the integer partition with Heinz number n.

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 5, 1, 2, 2, 5, 1, 4, 1, 4, 2, 2, 1, 8, 2, 2, 3, 4, 1, 6, 1, 7, 2, 2, 2, 11, 1, 2, 2, 8, 1, 5, 1, 4, 4, 2, 1, 16, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 13, 1, 2, 5, 11, 2, 5, 1, 4, 2, 6, 1, 19, 1, 2, 4, 4, 2, 5, 1, 13, 5, 2, 1, 13, 2

Offset: 1

Gus Wiseman, Feb 05 2018

nonn

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

			The a(36) = 11 twice-partitions:
  (2211),
  (22)(11), (211)(2), (221)(1), (21)(21),
  (2)(2)(11), (2)(11)(2), (11)(2)(2), (22)(1)(1), (21)(2)(1),
  (2)(2)(1)(1).

Robert Price, Table of n, a(n) for n = 1..200

Cf. A000041, A063834, A112798, A196545, A273873, A281145, A289501, A290261, A296150, A299200, A299202, A299203.

nn=100;
ptns=Table[If[n===1,{},Join@@Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]],{n,nn}];
tris=Join@@Map[Tuples[IntegerPartitions/@#]&,ptns];
Table[Length[Select[tris,Sort[Join@@#,Greater]===y&]],{y,ptns}]

A289078 Number of orderless same-trees of weight n.

Original entry on oeis.org

1, 2, 2, 5, 2, 9, 2, 22, 6, 11, 2, 94, 2, 13, 12, 334, 2, 205, 2, 210, 14, 17, 2, 7218, 8, 19, 68, 443, 2, 1687, 2, 69109, 18, 23, 16, 167873, 2, 25, 20, 89969, 2, 7041, 2, 1548, 644, 29, 2, 36094795, 10, 3078, 24, 2604, 2, 1484102, 20, 1287306, 26, 35, 2

Offset: 1

Gus Wiseman, Jun 23 2017

nonn

An orderless same-tree t is either: (case 1) a positive integer, or (case 2) a finite multiset of two or more orderless same-trees, all having the same weight. The weight of t in case 1 is the number itself, and in case 2 it is the sum of weights of the branches. For example {{{3,{1,1,1}},{2,{1,1},{1,1}}},{{{1,1,1},{1,1,1}},{{1,1},{1,1},{1,1}}}} is an orderless same-tree of weight 24 with 2 branches.

			The a(6)=9 orderless same-trees are: 6, (33), (3(111)), (222), (22(11)), (2(11)(11)), ((11)(11)(11)), ((111)(111)), (111111).

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

Cf. A196545, A273873, A275870, A281145, A281146, A289079.

with(numtheory):
a:= proc(n) option remember; 1 + add(
      binomial(a(n/d)+d-1, d), d=divisors(n) minus {1})
    end:
seq(a(n), n=1..60);  # Alois P. Heinz, Jul 05 2017

a[n_]:=If[n===1,1,1+Sum[Binomial[a[n/d]+d-1,d],{d,Rest[Divisors[n]]}]];
Array[a,100]

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + sumdiv(n, d, binomial(v[n/d]+d-1, d))); v} \\ Andrew Howroyd, Aug 20 2018

a(n) = 1 + Sum_{d|n, d>1} binomial(a(n/d)+d-1, d).

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

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

A289079 Number of orderless same-trees of weight n with all leaves equal to 1.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 5, 2, 3, 1, 13, 1, 3, 3, 22, 1, 16, 1, 15, 3, 3, 1, 151, 2, 3, 6, 17, 1, 41, 1, 334, 3, 3, 3, 637, 1, 3, 3, 275, 1, 56, 1, 21, 19, 3, 1, 15591, 2, 27, 3, 23, 1, 902, 3, 516, 3, 3, 1, 7858, 1, 3, 21, 69109, 3, 98, 1, 27, 3, 67, 1, 811756, 1

Offset: 1

Gus Wiseman, Jun 23 2017

nonn

a(n) is also the number of orderless same-trees of weight n with all leaves greater than 1.

			The a(12)=13 orderless same-trees with all leaves greater than 1 are: ((33)(33)), ((33)(222)), ((33)6), ((222)(222)), ((222)6), (66), ((22)(22)(22)), ((22)(22)4), ((22)44), (444), (3333), (222222), 12.

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

Cf. A196545, A273873, A275870, A281145, A281146, A289078.

with(numtheory):
a:= proc(n) option remember; `if`(n=1, 1, add(
      binomial(a(n/d)+d-1, d), d=divisors(n) minus {1}))
    end:
seq(a(n), n=1..80);  # Alois P. Heinz, Jul 05 2017

a[n_]:=If[n===1,1,Sum[Binomial[a[n/d]+d-1,d],{d,Rest[Divisors[n]]}]];
Array[a,100]

seq(n)={my(v=vector(n)); v[1]=1; for(n=2, n, v[n] = sumdiv(n, d, binomial(v[n/d]+d-1, d))); v} \\ Andrew Howroyd, Aug 20 2018

from sympy import divisors, binomial
l=[0, 1]
for n in range(2, 101): l+=[sum([binomial(l[n//d] + d - 1, d) for d in divisors(n)[1:]]), ]
l[1:] # Indranil Ghosh, Jul 06 2017

a(1) = 1, a(n>1) = Sum_{d|n, d>1} binomial(a(n/d)+d-1, d).

A050381 Number of series-reduced planted trees with n leaves of 2 colors.

Original entry on oeis.org

2, 3, 10, 40, 170, 785, 3770, 18805, 96180, 502381, 2667034, 14351775, 78096654, 429025553, 2376075922, 13252492311, 74372374366, 419651663108, 2379399524742, 13549601275893, 77460249369658, 444389519874841

Offset: 1

Christian G. Bower, Nov 15 1999

nonn

Consider the free algebraic system with two commutative associative operators (x+y) and (x*y) and two generators A,B. The number of elements with n occurrences of the generators is 2*a(n) if n>1, and the number of generators if n=1. - Michael Somos, Aug 07 2017
From Gus Wiseman, Feb 07 2020: (Start)
Also the number of semi-lone-child-avoiding rooted trees with n leaves. Semi-lone-child-avoiding means there are no vertices with exactly one child unless that child is an endpoint/leaf. For example, the a(1) = 2 through a(3) = 10 trees are:
  o    (oo)      (ooo)
  (o)  (o(o))    (o(oo))
       ((o)(o))  (oo(o))
                 ((o)(oo))
                 (o(o)(o))
                 (o(o(o)))
                 ((o)(o)(o))
                 ((o)(o(o)))
                 (o((o)(o)))
                 ((o)((o)(o)))
(End)

			For n=2, the 2*a(2) = 6 elements are: A+A, A+B, B+B, A*A, A*B, B*B. - _Michael Somos_, Aug 07 2017

Andrew Howroyd, Table of n, a(n) for n = 1..500
David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014).
F. Chapoton, F. Hivert, J.-C. Novelli, A set-operad of formal fractions and dendriform-like sub-operads, arXiv preprint arXiv:1307.0092 [math.CO], 2013.
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012. - From _N. J. A. Sloane_, Dec 22 2012
N. J. A. Sloane, Transforms
Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.
Index entries for sequences related to rooted trees

Column 2 of A319254.
Cf. A029856, A031148.
Lone-child-avoiding rooted trees with n leaves are A000669.
Lone-child-avoiding rooted trees with n vertices are A001678.
The locally disjoint case is A331874.
Semi-lone-child-avoiding rooted trees with n vertices are A331934.
Matula-Goebel numbers of these trees are A331935.
Cf. A000081, A005804, A141268, A196545, A291636, A316697, A330465, A331872, A331933, A331964.

terms = 22;
B[x_] = x O[x]^(terms+1);
A[x_] = 1/(1 - x + B[x])^2;
Do[A[x_] = A[x]/(1 - x^k + B[x])^Coefficient[A[x], x, k] + O[x]^(terms+1) // Normal, {k, 2, terms+1}];
Join[{2}, Drop[CoefficientList[A[x], x]/2, 2]] (* Jean-François Alcover, Aug 17 2018, after Michael Somos *)
slaurte[n_]:=If[n==1,{o,{o}},Join@@Table[Union[Sort/@Tuples[slaurte/@ptn]],{ptn,Rest[IntegerPartitions[n]]}]];
Table[Length[slaurte[n]],{n,10}] (* Gus Wiseman, Feb 07 2020 *)

{a(n) = my(A, B); if( n<2, 2*(n>0), B = x * O(x^n); A = 1 / (1 - x + B)^2; for(k=2, n, A /= (1 - x^k + B)^polcoeff(A, k)); polcoeff(A, n)/2)}; /* Michael Somos, Aug 07 2017 */

Doubles (index 2+) under EULER transform.
Product_{k>=1} (1-x^k)^-a(k) = 1 + a(1)*x + Sum_{k>=2} 2*a(k)*x^k. - Michael Somos, Aug 07 2017
a(n) ~ c * d^n / n^(3/2), where d = 6.158893517087396289837838459951206775682824030495453326610366016992093939... and c = 0.1914250508201011360729769525164141605187995730026600722369002... - Vaclav Kotesovec, Aug 17 2018

A299203 Number of enriched p-trees whose multiset of leaves is the integer partition with Heinz number n.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 4, 1, 1, 1, 5, 1, 3, 1, 3, 1, 1, 1, 11, 1, 1, 2, 3, 1, 5, 1, 12, 1, 1, 1, 15, 1, 1, 1, 11, 1, 4, 1, 3, 3, 1, 1, 38, 1, 3, 1, 3, 1, 9, 1, 9, 1, 1, 1, 21, 1, 1, 4, 34, 1, 4, 1, 3, 1, 5, 1, 54, 1, 1, 3, 3, 1, 4, 1, 33, 5, 1, 1, 23, 1, 1, 1, 9, 1, 20, 1, 3, 1, 1, 1, 117, 1, 3, 3, 12, 1, 4, 1, 9, 4, 1, 1, 57, 1, 4, 1, 34

Offset: 1

Gus Wiseman, Feb 05 2018

nonn

By convention, a(1) = 0.

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

			a(54) = 9: (((22)2)1), ((222)1), (((22)1)2), (((21)2)2), ((221)2), ((22)(21)), ((22)21), ((21)22), (2221).
a(40) = 11: ((31)(11)), (((31)1)1), ((3(11))1), ((311)1), (3((11)1)), (3(111)), (((11)1)3), ((111)3), ((31)11), (3(11)1), (3111).
a(36) = 15: ((22)(11)), ((2(11))2), (((11)2)2), (((21)1)2), ((211)2), (((22)1)1), (((21)2)1), ((221)1), ((21)(21)), (22(11)), (2(11)2), ((11)22), ((22)11), ((21)21), (2211).

Cf. A000041, A063834, A112798, A196545, A273873, A281145, A289501, A290261, A296150, A299200, A299201, A299202.

nn=120;
ptns=Table[If[n===1,{},Join@@Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]],{n,nn}];
tris=Join@@Map[Tuples[IntegerPartitions/@#]&,ptns];
qci[y_]:=qci[y]=If[Length[y]===1,1,Sum[Times@@qci/@t,{t,Select[tris,And[Length[#]>1,Sort[Join@@#,Greater]===y]&]}]];
qci/@ptns

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

cp's OEIS Frontend

A299201 Number of twice-partitions whose composite is the integer partition with Heinz number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A289078 Number of orderless same-trees of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

A289079 Number of orderless same-trees of weight n with all leaves equal to 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A050381 Number of series-reduced planted trees with n leaves of 2 colors.

Views

Author

Keywords

Comments

Examples