A290689 -id:A290689 - cp's OEIS frontend

A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 6, 8, 4, 1, 0, 1, 9, 18, 14, 5, 1, 0, 1, 12, 35, 39, 21, 6, 1, 0, 1, 16, 62, 97, 72, 30, 7, 1, 0, 1, 20, 103, 212, 214, 120, 40, 8, 1, 0, 1, 25, 161, 429, 563, 416, 185, 52, 9, 1, 0, 1, 30, 241, 804, 1344, 1268, 732, 270, 65, 10, 1, 0

Offset: 1

Christian G. Bower, May 09 2000

Harary denotes the g.f. as P(x, y) on page 33 "... , and let P(x,y) = Sum Sum P_{nm} x^ny^m where P_{nm} is the number of planted trees with n points and m endpoints, in which again the plant has not been counted either as a point or as an endpoint." - Michael Somos, Nov 02 2014

			From _Joerg Arndt_, Aug 18 2014: (Start)
Triangle starts:
01: 1
02: 1    0
03: 1    1    0
04: 1    2    1    0
05: 1    4    3    1    0
06: 1    6    8    4    1    0
07: 1    9   18   14    5    1    0
08: 1   12   35   39   21    6    1    0
09: 1   16   62   97   72   30    7    1    0
10: 1   20  103  212  214  120   40    8    1    0
11: 1   25  161  429  563  416  185   52    9    1    0
12: 1   30  241  804 1344 1268  732  270   65   10    1    0
13: 1   36  348 1427 2958 3499 2544 1203  378   80   11    1    0
...
The trees with n=5 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:
:
:     1:  [ 0 1 2 3 4 ]   1
:  O--o--o--o--o
:
:     2:  [ 0 1 2 3 3 ]   2
:  O--o--o--o
:        .--o
:
:     3:  [ 0 1 2 3 2 ]   2
:  O--o--o--o
:     .--o
:
:     4:  [ 0 1 2 3 1 ]   2
:  O--o--o--o
:  .--o
:
:     5:  [ 0 1 2 2 2 ]   3
:  O--o--o
:     .--o
:     .--o
:
:     6:  [ 0 1 2 2 1 ]   3
:  O--o--o
:     .--o
:  .--o
:
:     7:  [ 0 1 2 1 2 ]   2
:  O--o--o
:  .--o--o
:
:     8:  [ 0 1 2 1 1 ]   3
:  O--o--o
:  .--o
:  .--o
:
:     9:  [ 0 1 1 1 1 ]   4
:  O--o
:  .--o
:  .--o
:  .--o
:
This gives [1, 4, 3, 1, 0], row n=5 of the triangle.
(End)
G.f. = x*(y + x*y + x^2*(y + y^2) + x^3*(y + 2*y^2 + y^3) + x^4*(y + 4*y^2 + 3*x^3 + y^4) + ...).

F. Harary, Recent results on graphical enumeration, pp. 29-36 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
N. J. A. Sloane, Transforms
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Index entries for sequences related to rooted trees

Row sums give A000081.
Columns 2 through 12: A002620(n-1), A055278-A055287.
Cf. A055288, A055289, A055290.
Cf. A001190, A003238, A004111, A055327, A214575, A290689, A298422, A298426, A301342, A301343, A301344, A301345.

rut[n_]:=rut[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[rut/@c]]]/@IntegerPartitions[n-1]];
Table[Length[Select[rut[n],Count[#,{},{-2}]===k&]],{n,13},{k,n}] (* Gus Wiseman, Mar 19 2018 *)

{T(n, k) = my(A = O(x)); if(k<1 || k>n, 0, for(j=1, n, A = x*(y - 1  + exp( sum(i=1, j, 1/i * subst( subst( A + x * O(x^(j\i)), x, x^i), y, y^i) ) ))); polcoeff( polcoeff(A, n), k))}; /* Michael Somos, Aug 24 2015 */

G.f. satisfies A(x, y) = x*y + x*EULER(A(x, y)) - x. Shifts up under EULER transform.
G.f. satisfies A(x, y) = x*y - x + x * exp(Sum_{i>0} A(x^i, y^i) / i). [Harary, p. 34, equation (10)]. - Michael Somos, Nov 02 2014
Sum_k T(n, k) = A000081(n). - Michael Somos, Aug 24 2015

A290822 Transitive numbers: Matula-Goebel numbers of transitive rooted trees.

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 14, 16, 18, 24, 28, 30, 32, 36, 38, 42, 48, 54, 56, 60, 64, 72, 76, 78, 84, 90, 96, 98, 106, 108, 112, 114, 120, 126, 128, 138, 144, 150, 152, 156, 162, 168, 180, 192, 196, 210, 212, 216, 222, 224, 228, 234, 238, 240, 252, 256, 262, 266, 270

Offset: 1

Gus Wiseman, Oct 19 2017

nonn

A number x is transitive if whenever prime(y) divides x and prime(z) divides y, we have prime(z) divides x.

			The sequence of transitive rooted trees begins:
1  o
2  (o)
4  (oo)
6  (o(o))
8  (ooo)
12 (oo(o))
14 (o(oo))
16 (oooo)
18 (o(o)(o))
24 (ooo(o))
28 (oo(oo))
30 (o(o)((o)))
32 (ooooo)
36 (oo(o)(o))
38 (o(ooo))
42 (o(o)(oo))
48 (oooo(o))
54 (o(o)(o)(o))
56 (ooo(oo))
60 (oo(o)((o)))
64 (oooooo)
72 (ooo(o)(o))
76 (oo(ooo))
78 (o(o)(o(o)))
84 (oo(o)(oo))
90 (o(o)(o)((o)))
96 (ooooo(o))
98 (o(oo)(oo))

Robert P. P. McKone, Table of n, a(n) for n = 1..9999

Cf. A007097, A276625, A279861, A290689, A290760.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
subprimes[n_]:=If[n===1,{},Union@@Cases[FactorInteger[n],{p_,_}:>FactorInteger[PrimePi[p]][[All,1]]]];
Select[Range[270],Divisible[#,Times@@subprimes[#]]&]

A032305 Number of rooted trees where any 2 subtrees extending from the same node have a different number of nodes.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 12, 25, 51, 111, 240, 533, 1181, 2671, 6014, 13795, 31480, 72905, 168361, 393077, 914784, 2150810, 5040953, 11914240, 28089793, 66702160, 158013093, 376777192, 896262811, 2144279852, 5120176632, 12286984432, 29428496034, 70815501209

Offset: 1

Christian G. Bower

nonn

			The a(6) = 6 fully unbalanced trees: (((((o))))), (((o(o)))), ((o((o)))), (o(((o)))), (o(o(o))), ((o)((o))). - _Gus Wiseman_, Jan 10 2018

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Gus Wiseman, Illustration of the first 8 terms of A032305.
Index entries for sequences related to rooted trees

Cf. A000081, A001678, A003238, A004111, A213920, A273873, A290689, A291443, A297571.

Column k=1 of A318753.

A:= proc(n) if n<=1 then x else convert(series(x* (product(1+ coeff(A(n-1), x,i)*x^i, i=1..n-1)), x=0, n+1), polynom) fi end: a:= n-> coeff(A(n), x,n): seq(a(n), n=1..31);  # Alois P. Heinz, Aug 22 2008
# second Maple program:
g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(`if`(j=0, 1, g((i-1)$2))*g(n-i*j, i-1), j=0..min(1, n/i))))
    end:
a:= n-> g((n-1)$2):
seq(a(n), n=1..35);  # Alois P. Heinz, Mar 04 2013

nn=30;f[x_]:=Sum[a[n]x^n,{n,0,nn}];sol=SolveAlways[0 == Series[f[x]-x Product[1+a[i]x^i,{i,1,nn}],{x,0,nn}],x];Table[a[n],{n,1,nn}]/.sol  (* Geoffrey Critzer, Nov 17 2012 *)
allnim[n_]:=If[n===1,{{}},Join@@Function[c,Select[Union[Sort/@Tuples[allnim/@c]],UnsameQ@@(Count[#,_List,{0,Infinity}]&/@#)&]]/@IntegerPartitions[n-1]];
Table[Length[allnim[n]],{n,15}] (* Gus Wiseman, Jan 10 2018 *)
g[n_, i_] := g[n, i] = If[n == 0, 1, If[i < 1, 0,
     Sum[If[j == 0, 1, g[i-1, i-1]]*g[n-i*j, i-1], {j, 0, Min[1, n/i]}]]];
a[n_] := g[n-1, n-1];
Array[a, 35] (* Jean-François Alcover, May 21 2021, after Alois P. Heinz *)

a(n)=polcoeff(x*prod(i=1,n-1,1+a(i)*x^i)+x*O(x^n),n)

Shifts left under "EFK" (unordered, size, unlabeled) transform.
G.f.: A(x) = x*Product_{n>=1} (1+a(n)*x^n) = Sum_{n>=1} a(n)*x^n. - Paul D. Hanna, Apr 07 2004
Lim_{n->infinity} a(n)^(1/n) = 2.5119824... - Vaclav Kotesovec, Nov 20 2019
G.f.: x * exp(Sum_{n>=1} Sum_{k>=1} (-1)^(k+1) * a(n)^k * x^(n*k) / k). - Ilya Gutkovskiy, Jun 30 2021

A306844 Number of anti-transitive rooted trees with n nodes.

Original entry on oeis.org

1, 1, 2, 3, 7, 14, 36, 83, 212, 532, 1379, 3577, 9444, 25019, 66943, 179994, 487031, 1323706, 3614622, 9907911

Offset: 1

Gus Wiseman, Mar 13 2019

A rooted tree is anti-transitive if the subbranches are disjoint from the branches, i.e., no branch of a branch is a branch.

			The a(1) = 1 through a(6) = 14 anti-transitive rooted trees:
  o  (o)  (oo)   (ooo)    (oooo)     (ooooo)
          ((o))  ((oo))   ((ooo))    ((oooo))
                 (((o)))  (((oo)))   (((ooo)))
                          ((o)(o))   ((o)(oo))
                          ((o(o)))   ((o(oo)))
                          (o((o)))   ((oo(o)))
                          ((((o))))  (o((oo)))
                                     (oo((o)))
                                     ((((oo))))
                                     (((o)(o)))
                                     (((o(o))))
                                     ((o((o))))
                                     (o(((o))))
                                     (((((o)))))

Gus Wiseman, The a(7) = 36 anti-transitive rooted trees.
Gus Wiseman, The a(10) = 532 anti-transitive rooted trees.

Cf. A276625, A279861, A279861, A290689, A290760, A304360.

Cf. A324694, A324695, A324738, A324741, A324743, A324751, A324754, A324756, A324758, A324759, A324764.

rtall[n_]:=Union[Sort/@Join@@(Tuples[rtall/@#]&/@IntegerPartitions[n-1])];
Table[Length[Select[rtall[n],Intersection[Union@@#,#]=={}&]],{n,10}]

a(16)-a(20) from Jinyuan Wang, Jun 20 2020

A301700 Number of aperiodic rooted trees with n nodes.

Original entry on oeis.org

1, 1, 1, 2, 4, 10, 21, 52, 120, 290, 697, 1713, 4200, 10446, 26053, 65473, 165257, 419357, 1068239, 2732509, 7013242, 18059960, 46641983, 120790324, 313593621, 816046050, 2128101601, 5560829666, 14557746453, 38177226541, 100281484375, 263815322761, 695027102020

Offset: 1

Gus Wiseman, Apr 23 2018

nonn

An unlabeled rooted tree is aperiodic if the multiset of branches of the root is an aperiodic multiset, meaning it has relatively prime multiplicities, and each branch is also aperiodic.

			The a(6) = 10 aperiodic trees are (((((o))))), (((o(o)))), ((o((o)))), ((oo(o))), (o(((o)))), (o(o(o))), ((o)((o))), (oo((o))), (o(o)(o)), (ooo(o)).

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

Cf. A000081, A000740, A000837, A001678, A003238, A004111, A007716, A007916, A100953, A276625, A284639, A290689, A298422, A303386, A303431.

arut[n_]:=arut[n]=If[n===1,{{}},Join@@Function[c,Select[Union[Sort/@Tuples[arut/@c]],GCD@@Length/@Split[#]===1&]]/@IntegerPartitions[n-1]];
Table[Length[arut[n]],{n,20}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
MoebiusT(v)={vector(#v, n, sumdiv(n,d,moebius(n/d)*v[d]))}
seq(n)={my(v=[1]); for(n=2, n, v=concat([1], MoebiusT(EulerT(v)))); v} \\ Andrew Howroyd, Sep 01 2018

Terms a(21) and beyond from Andrew Howroyd, Sep 01 2018

A325755 Numbers n divisible by their prime shadow A181819(n).

Original entry on oeis.org

1, 2, 9, 12, 18, 36, 40, 60, 84, 112, 120, 125, 132, 156, 180, 204, 225, 228, 250, 252, 276, 280, 336, 348, 352, 360, 372, 396, 440, 441, 444, 450, 468, 492, 516, 520, 540, 560, 564, 600, 612, 636, 675, 680, 684, 708, 732, 760, 804, 828, 832, 840, 852, 876

Offset: 1

Gus Wiseman, May 19 2019

nonn

We define the prime shadow A181819(n) to be the product of primes indexed by the exponents in the prime factorization of n. For example, 90 = prime(1)*prime(2)^2*prime(3) has prime shadow prime(1)*prime(2)*prime(1) = 12.

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), so these are Heinz numbers of integer partitions containing their multiset of multiplicities as a submultiset (counted by A325702).

			The sequence of terms together with their prime indices begins:
     1: {}
     2: {1}
     9: {2,2}
    12: {1,1,2}
    18: {1,2,2}
    36: {1,1,2,2}
    40: {1,1,1,3}
    60: {1,1,2,3}
    84: {1,1,2,4}
   112: {1,1,1,1,4}
   120: {1,1,1,2,3}
   125: {3,3,3}
   132: {1,1,2,5}
   156: {1,1,2,6}
   180: {1,1,2,2,3}
   204: {1,1,2,7}
   225: {2,2,3,3}
   228: {1,1,2,8}
   250: {1,3,3,3}
   252: {1,1,2,2,4}

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A181819, A182857, A290689, A290822, A323014, A324843, A325702, A325706, A325708, A325756.

red[n_]:=If[n==1,1,Times@@Prime/@Last/@FactorInteger[n]];
Select[Range[100],Divisible[#,red[#]]&]

A298118 Number of unlabeled rooted trees with n nodes in which all positive outdegrees are odd.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 11, 21, 40, 80, 159, 322, 657, 1356, 2816, 5896, 12407, 26267, 55861, 119331, 255878, 550665, 1188786, 2574006, 5588177, 12162141, 26529873, 57993624, 127020653, 278716336, 612617523, 1348680531, 2973564157, 6565313455, 14514675376

Offset: 1

Gus Wiseman, Jan 12 2018

nonn

			The a(6) = 6 trees: (((((o))))), (((ooo))), ((oo(o))), (oo((o))), (o(o)(o)), (ooooo).

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

Cf. A000081, A000598, A003238, A004111, A027193, A032305, A067659, A290689, A291443, A297791, A298120.

orut[n_]:=orut[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[orut/@c]]]/@Select[IntegerPartitions[n-1],OddQ[Length[#]]&]];
Table[Length[orut[n]],{n,15}]

a(n) ~ c * d^n / n^(3/2), where d = 2.30984417428419893876754252289588812511559... and c = 0.5598122522173731208680575003383895445787... - Vaclav Kotesovec, Jun 04 2019

a(24)-a(35) from Alois P. Heinz, Jan 12 2018

A290760 Matula-Goebel numbers of transitive rooted identity trees (or transitive finitary sets).

Original entry on oeis.org

1, 2, 6, 30, 78, 330, 390, 870, 1410, 3198, 3390, 4290, 7878, 9570, 10230, 11310, 13026, 15510, 15990, 18330, 26070, 30966, 37290, 39390, 40890, 44070, 45210, 65130, 84810, 94830, 98310, 104610, 122070, 124410, 132990, 154830, 159330, 175890, 198330, 201630

Offset: 1

Gus Wiseman, Oct 19 2017

nonn

A rooted tree is transitive if every terminal subtree is a branch of the root. A finitary set is transitive if every element is also a subset.

			Let o = {}. The sequence of transitive finitary sets begins:
1     o
2     {o}
6     {o,{o}}
30    {o,{o},{{o}}}
78    {o,{o},{o,{o}}}
330   {o,{o},{{o}},{{{o}}}}
390   {o,{o},{{o}},{o,{o}}}
870   {o,{o},{{o}},{o,{{o}}}}
1410  {o,{o},{{o}},{{o},{{o}}}}
3198  {o,{o},{o,{o}},{{o,{o}}}}
3390  {o,{o},{{o}},{o,{o},{{o}}}}
4290  {o,{o},{{o}},{{{o}}},{o,{o}}}
7878  {o,{o},{o,{o}},{o,{o,{o}}}}
9570  {o,{o},{{o}},{{{o}}},{o,{{o}}}}
10230 {o,{o},{{o}},{{{o}}},{{{{o}}}}}
11310 {o,{o},{{o}},{o,{o}},{o,{{o}}}}
13026 {o,{o},{o,{o}},{{o},{o,{o}}}}
15510 {o,{o},{{o}},{{{o}}},{{o},{{o}}}}
15990 {o,{o},{{o}},{o,{o}},{{o,{o}}}}
18330 {o,{o},{{o}},{o,{o}},{{o},{{o}}}}

Cf. A000081, A001192, A004111, A007097, A076146, A276625, A279861, A290689, A290822.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
finitaryQ[n_]:=finitaryQ[n]=Or[n===1,With[{m=primeMS[n]},{UnsameQ@@m,finitaryQ/@m}]/.List->And];
subprimes[n_]:=If[n===1,{},Union@@Cases[FactorInteger[n],{p_,_}:>FactorInteger[PrimePi[p]][[All,1]]]];
transitaryQ[n_]:=Divisible[n,Times@@subprimes[n]];
nn=100000;Fold[Select,Range[nn],{finitaryQ,transitaryQ}]

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

A325702 Number of integer partitions of n containing their multiset of multiplicities (as a submultiset).

Original entry on oeis.org

1, 1, 0, 0, 2, 1, 2, 1, 3, 3, 8, 7, 10, 13, 17, 19, 28, 35, 38, 51, 67, 81, 100, 128, 157, 195, 233, 285, 348, 427, 506, 613, 733, 873, 1063, 1263, 1503, 1802, 2131, 2537, 3005, 3565, 4171, 4922, 5820, 6775, 8001, 9333, 10860, 12739, 14840, 17206, 20029, 23248

Offset: 0

Gus Wiseman, May 18 2019

nonn

The Heinz numbers of these partitions are given by A325755.

			The partition x = (4,3,1,1,1) has multiplicities (3,1,1), which are a submultiset of x, so x is counted under a(10).
The a(1) = 1 through a(11) = 7 partitions:
  (1)  (22)   (221)  (2211)  (3211)  (4211)   (333)    (3322)    (7211)
       (211)         (3111)          (32111)  (5211)   (3331)    (33221)
                                     (41111)  (32211)  (6211)    (52211)
                                                       (42211)   (53111)
                                                       (43111)   (322211)
                                                       (322111)  (332111)
                                                       (421111)  (431111)
                                                       (511111)

Cf. A000041, A181819, A225486, A290689, A290822, A304360, A323014, A324736, A324748, A324753, A324843, A325254, A325755.

submultQ[cap_,fat_]:=And@@Function[i,Count[fat,i]>=Count[cap,i]]/@Union[List@@cap]
Table[Length[Select[IntegerPartitions[n],submultQ[Sort[Length/@Split[#]],#]&]],{n,0,30}]

cp's OEIS Frontend

A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A290822 Transitive numbers: Matula-Goebel numbers of transitive rooted trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A032305 Number of rooted trees where any 2 subtrees extending from the same node have a different number of nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A306844 Number of anti-transitive rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A301700 Number of aperiodic rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A325755 Numbers n divisible by their prime shadow A181819(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A298118 Number of unlabeled rooted trees with n nodes in which all positive outdegrees are odd.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions