A001190 -id:A001190 - cp's OEIS frontend

A317718 Number of uniform relatively prime rooted trees with n nodes.

1, 1, 2, 4, 7, 13, 27, 55, 125, 278, 650, 1510, 3624, 8655, 21017, 51212, 125857, 310581, 770767, 1920226

Offset: 1

Gus Wiseman, Aug 05 2018

An unlabeled rooted tree is uniform and relatively prime iff either it is a single node or a single node with a single uniform relatively prime branch, or the branches of the root have empty intersection (relatively prime) and equal multiplicities (uniform) and are themselves uniform relatively prime trees.

			The a(6) = 13 uniform relatively prime rooted trees:
  (((((o)))))
  ((((oo))))
  (((o(o))))
  (((ooo)))
  ((o((o))))
  ((o(oo)))
  ((oooo))
  (o(((o))))
  (o((oo)))
  (o(o(o)))
  (o(ooo))
  ((o)((o)))
  (ooooo)

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

Cf. A000081, A001190, A004111, A072774, A301700, A317588.

Cf. A317705, A317707, A317708, A317709, A317710, A317711, A317712, A317717.

purt[n_]:=purt[n]=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[purt/@ptn]],Or[Length[#]==1,And[SameQ@@Length/@Split[#],Intersection@@#=={}]]&],{ptn,IntegerPartitions[n-1]}]];
Table[Length[purt[n]],{n,20}]

A319541 Triangle read by rows: T(n,k) is the number of binary rooted trees with n leaves of exactly k colors and all non-leaf nodes having out-degree 2.

Original entry on oeis.org

1, 1, 1, 1, 4, 3, 2, 14, 27, 15, 3, 48, 180, 240, 105, 6, 171, 1089, 2604, 2625, 945, 11, 614, 6333, 24180, 42075, 34020, 10395, 23, 2270, 36309, 207732, 554820, 755370, 509355, 135135, 46, 8518, 207255, 1710108, 6578550, 13408740, 14963130, 8648640, 2027025

Offset: 1

Andrew Howroyd, Sep 22 2018

See table 2.2 in the Johnson reference.

			Triangle begins:
   1;
   1,    1;
   1,    4,     3;
   2,   14,    27,     15;
   3,   48,   180,    240,    105;
   6,  171,  1089,   2604,   2625,    945;
  11,  614,  6333,  24180,  42075,  34020,  10395;
  23, 2270, 36309, 207732, 554820, 755370, 509355, 135135;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Virginia Perkins Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. South Carolina, 2012.

Columns 1..5 are A001190, A220819, A220820, A220821, A220822.
Main diagonal is A001147.
Row sums give A319590.
Cf. A241555, A319376, A319539.

A:= proc(n, k) option remember; `if`(n<2, k*n, `if`(n::odd, 0,
      (t-> t*(1-t)/2)(A(n/2, k)))+add(A(i, k)*A(n-i, k), i=1..n/2))
    end:
T:= (n, k)-> add((-1)^i*binomial(k, i)*A(n, k-i), i=0..k):
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Sep 23 2018

A[n_, k_] := A[n, k] = If[n<2, k n, If[OddQ[n], 0, (#(1-#)/2)&[A[n/2, k]]] + Sum[A[i, k] A[n - i, k], {i, 1, n/2}]];
T[n_, k_] := Sum[(-1)^i Binomial[k, i] A[n, k - i], {i, 0, k}];
Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 02 2019, after Alois P. Heinz *)

\\ here R(n,k) is k-th column of A319539 as a vector.
R(n,k)={my(v=vector(n)); v[1]=k; for(n=2, n, v[n]=sum(j=1, (n-1)\2, v[j]*v[n-j]) + if(n%2, 0, binomial(v[n/2]+1, 2))); v}
M(n)={my(v=vector(n, k, R(n,k)~)); Mat(vector(n, k, sum(i=1, k, (-1)^(k-i)*binomial(k,i)*v[i])))}
{my(T=M(10)); for(n=1, #T~, print(T[n, ][1..n]))}

T(n,k) = Sum_{i=1..k} (-1)^(k-i)*binomial(k,i)*A319539(n,i).

A000672 Number of 3-valent trees (= boron trees or binary trees) with n nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 6, 11, 18, 37, 66, 135, 265, 552, 1132, 2410, 5098, 11020, 23846, 52233, 114796, 254371, 565734, 1265579, 2841632, 6408674, 14502229, 32935002, 75021750, 171404424, 392658842, 901842517, 2076217086, 4790669518, 11077270335

Offset: 0

N. J. A. Sloane

This can be described in 2 ways: (a) Trees with n nodes of valency <= 3, for n = 0,1,2,3,... (b) Trees with t = 2n+2 nodes of valency either 1 or 3 (implying that there are n nodes of valency 3 - the boron atoms - and n+2 nodes of valency 1 - the hydrogen atoms), for t = 2,4,6,8,...

Essentially the same sequences arises from studying the number of unrooted, unlabeled binary tree topologies with n leaves (see A129860). - Steven Kelk, Jul 22 2016

			The 4 trees with 6 nodes are:
._._._._._. . ._._._._. . ._._._._. . ._._._.
. . . . . . . . | . . . . . . | . . . . | |
G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 + 4*x^6 + 6*x^7 + 11*x^8 + ...

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 307.
P. J. Cameron, Oligomorphic Permutation Groups, Cambridge; see Fig. 2 p. 35.
A. Cayley, On the analytical forms called trees, with application to the theory of chemical combinations, Reports British Assoc. Advance. Sci. 45 (1875), 257-305 = Math. Papers, Vol. 9, 427-460 (see p. 451).
Joseph Felsenstein, Inferring Phylogenies. Sinauer Associates, Inc., 2004, page 33. Note that at least the first two editions give an incorrect version of this sequence.
R. C. Read, personal communication.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. J. Mathar, Table of n, a(n) for n = 0..191 [b-file corrected by _N. J. A. Sloane_, Oct 04 2010]
Dominik Bendle, Janko Boehm, Yue Ren, and Benjamin Schröter, Parallel Computation of tropical varieties, their positive part, and tropical Grassmannians, arXiv:2003.13752 [math.AG], 2020.
Nicolas Broutin and Philippe Flajolet, The distribution of height and diameter in random non-plane binary trees, Random Struct. Algorithms 41, No. 2, 215-252 (2012).
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183.
M. Chan, Tropical hyperelliptic curves, arXiv preprint arXiv:1110.0273 [math.CO], 2011.
Sergio Consoli, Jan Korst, Gijs Geleijnse, and Steffen Pauws, On the minimum quartet tree cost problem, arXiv:1807.00566 [cs.DM], 2018.
S. J. Cyvin, J. Brunvoll, and B. N. Cyvin, Enumeration of constitutional isomers of polyenes, J. Molec. Struct. (Theochem) 357, no. 3 (1995) 255-261.
V. Fack, S. Lievens, and J. Van der Jeugt, On the diameter of the rotation graph of binary coupling trees, Discrete Math. 245 (2002), no. 1-3, 1--18. MR1887046 (2003i:05047).
Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, Six-Point Conformal Blocks in the Snowflake Channel, arXiv:2004.02824 [hep-th], 2020.
Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, Seven-Point Conformal Blocks in the Extended Snowflake Channel and Beyond, arXiv:2006.13964 [hep-th], 2020.
Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, All Global One- and Two-Dimensional Higher-Point Conformal Blocks, arXiv:2009.07674 [hep-th], 2020.
M. D. Hendy, C. H. C. Little, David Penny, Comparing trees with pendant vertices labelled, SIAM J. Appl. Math. 44 (5) (1984) Table 1
Virginia Perkins Johnson, Enumeration Results on Leaf Labeled Trees, PhD Dissertation, University of South Carolina, 2012. - From _N. J. A. Sloane_, Dec 22 2012
R. Otter, The number of trees, Ann. of Math. (2) 49 (1948), 583-599 discusses asymptotics.
E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees), J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976
Eric Weisstein's World of Mathematics, Trivalent Tree
Index entries for sequences related to trees

Column k = 3 of A144528.
A000672 = A000675 + A000673.
Cf. A001190(n+1) (rooted trees).
Cf. A052120, A000022, A000200, A000602, A129860.

(* c = A001190 *) c[n_?OddQ] := c[n] = Sum[c[k]*c[n-k], {k, 1, (n-1)/2}]; c[n_?EvenQ] := c[n] = (1/2)*c[n/2]*(c[n/2] + 1) + Sum[c[k]*c[n-k], {k, 1, n/2-1}]; c[0] = 0; c[1] = 1; b[x_] := If[IntegerQ[x], c[x+1], 0]; a[0] = a[1] = a[2] = 1; a[n_] := b[n/2] - (1/3)*(b[(n-1)/3]-1)*b[(n-1)/3]*(b[(n-1)/3] + 1) + 2*b[n] - b[n+1] - Sum[(1/2)*(b[i]-1)*b[i]*b[-2*i + n - 1], {i, 1, (n-2)/2}] + Sum[b[i]*Sum[b[j]*b[n-i-j-1], {j, i, (1/2)*(n-i-1)}], {i, 1, (n-1)/3}]; Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jan 19 2015 *)
n = 50; (* algorithm from Rains and Sloane *)
S2[f_,h_,x_] := f[h,x]^2/2 + f[h,x^2]/2;
S3[f_,h_,x_] := f[h,x]^3/6 + f[h,x] f[h,x^2]/2 + f[h,x^3]/3;
T[-1,z_] := 1;  T[h_,z_] := T[h,z] = Table[z^k, {k,0,n}].Take[CoefficientList[z^(n+1) + 1 + S2[T,h-1,z]z, z], n+1];
Sum[Take[CoefficientList[z^(n+1) + S3[T,h-1,z]z - S3[T,h-2,z]z - (T[h-1,z] - T[h-2,z]) (T[h-1,z]-1),z], n+1], {h,1,n/2}] + PadRight[{1,1}, n+1] + Sum[Take[CoefficientList[z^(n+1) + (T[h,z] - T[h-1,z])^2/2 + (T[h,z^2] - T[h-1,z^2])/2, z],n+1], {h,0,n/2}] (* Robert A. Russell, Sep 15 2018 *)
n = 60; c[n_?OddQ] := c[n] = Sum[c[k]*c[n-k], {k,1,(n-1)/2}];
c[n_?EvenQ] := c[n] = (1/2)*c[n/2]*(c[n/2] + 1) + Sum[c[k]*c[n-k],
  {k,1,n/2-1}]; c[0] = 0; c[1] = 1; (* as in program 1 above *)
gf[x_] := Sum[c[i+1] x^i, {i,0,n}]; (* g.f. for A001190(n+1) *)
ci[x_] := SymmetricGroupIndex[3, x] /. x[i_] -> gf[x^i];
CoefficientList[Normal[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 +
x ci[x], {x,0,n}]], x] (* Robert A. Russell, Jan 17 2023 *)

Rains and Sloane give a g.f.
a(0)=a(1)=a(2)=1, a(n) = 2*b(n+1) - b(n+2) + b((n+1)/2) - 2*C(1+b(n/3), 3) - Sum_{i=1..[(n-1)/2]} C(b(i), 2)*b(n-2*i) + Sum_{i=1..[n/3]} b(i) Sum_{j=i..[(n-i)/2]} b(j)*b(n-i-j), where b(x) = A001190(x+1) if x is an integer, otherwise 0 (Cyvin et al.) [Index of A001190 shifted by R. J. Mathar, Mar 08 2010]
a(n) = A000673(n) + A000675(n).
a(n) ~ c * d^n / n^(5/2), where d = A086317 = 2.4832535361726368585622885181... and c = 1.2551088797592580080398489829149157375... . - Vaclav Kotesovec, Apr 19 2016
G.f.: B(x) - cycle_index(S2,-B(x)) + x * cycle_index(S3,B(x)) = B(x) - (B(x)^2 - B(x^2)) / 2 + x * (B(x)^3 + 3*B(x) B(x^2) + 2*B(x^3)) / 6, where B(x) = 1 + x * cycle_index(S2,B(x)) = 1 + x * (B(x)^2 + B(x^2)) / 2 is the generating function for A001190(n+1). - Robert A. Russell, Jan 17 2023

A086317 Decimal expansion of asymptotic constant xi for counts of weakly binary trees.

Original entry on oeis.org

2, 4, 8, 3, 2, 5, 3, 5, 3, 6, 1, 7, 2, 6, 3, 6, 8, 5, 8, 5, 6, 2, 2, 8, 8, 5, 1, 8, 1, 7, 8, 2, 2, 1, 2, 8, 9, 1, 8, 8, 6, 9, 7, 3, 4, 0, 8, 1, 4, 3, 6, 4, 5, 8, 5, 9, 2, 0, 2, 5, 9, 6, 9, 7, 3, 0, 6, 7, 4, 2, 5, 4, 0, 8, 8, 5, 8, 0, 9, 8, 3, 9, 0, 6, 4, 7, 6, 4, 0, 1, 6, 9, 1, 6, 7, 2, 1, 8, 2, 7, 4, 7

Offset: 1

Eric W. Weisstein, Jul 15 2003

			2.48325353617263685856228851817822128918869734...

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Lyuben Lichev, Dieter Mitsche, On the modularity of 3-regular random graphs and random graphs with given degree sequences, arXiv:2007.15574 [math.PR], 2020.
Eric Weisstein's World of Mathematics, Weakly binary tree

Cf. A001190, A086318, A240943.

Cf. A000672, A003214.

digits = 102; c[0] = 2; c[n_] := c[n] = c[n - 1]^2 + 2; xi[n_Integer] := xi[n] = c[n]^(2^-n); xi[5]; xi[n = 10]; While[RealDigits[xi[n], 10, digits] != RealDigits[xi[n - 5], 10, digits], n = n + 5]; RealDigits[xi[n], 10, digits] // First (* Jean-François Alcover, May 27 2014 *)

Equals 1/A240943.

Equals lim_{n->infinity} A001190(n)^(1/n). - Vaclav Kotesovec, Jul 28 2014

Typos corrected by Jean-François Alcover, May 27 2014

A295461 Number of unlabeled rooted trees with 2n + 1 nodes in which all outdegrees are even.

Original entry on oeis.org

1, 1, 2, 5, 12, 33, 91, 264, 780, 2365, 7274, 22727, 71784, 229094, 737215, 2390072, 7798020, 25587218, 84377881, 279499063, 929556155, 3102767833, 10390936382, 34903331506, 117564309276, 396994228503, 1343716120550, 4557952756658, 15491856887741

Offset: 0

Gus Wiseman, Jan 13 2018

nonn

			The a(3) = 5 trees: (o(o(oo))), (o(oooo)), ((oo)(oo)), (ooo(oo)), (oooooo).

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

Cf. A000081, A000598, A001190, A003238, A004111, A027193, A027187, A032305, A067659, A290689, A291443, A297791, A298118, A298120, A298126.

erut[n_]:=erut[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[erut/@c]]]/@Select[IntegerPartitions[n-1],EvenQ[Length[#]]&]];
Table[Length[erut[n]],{n,1,30,2}]

A300442 Number of binary strict trees of weight n.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 10, 23, 46, 108, 231, 561, 1285, 3139, 7348, 18265, 43907, 109887, 267582, 675866, 1669909, 4238462, 10555192, 26955062, 67706032, 173591181, 438555624, 1129088048, 2869732770, 7410059898, 18911818801, 48986728672, 125562853003, 326011708368

Offset: 0

Gus Wiseman, Mar 05 2018

nonn

A binary strict tree of weight n > 0 is either a single node of weight n, or an ordered pair of binary strict trees with strictly decreasing weights summing to n.

			The a(5) = 6 binary strict trees: 5, (41), (32), ((31)1), ((21)2), (((21)1)1).
The a(6) = 10 binary strict trees:
  6,
  (51), (42),
  ((41)1), ((32)1), ((31)2),
  (((31)1)1), (((21)2)1), (((21)1)2),
  ((((21)1)1)1).

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

Cf. A000992, A001190, A063834, A196545, A273873, A289501, A292432, A293511, A300352, A300440, A300443.

a:= proc(n) option remember;
      1+add(a(j)*a(n-j), j=1..(n-1)/2)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Mar 06 2018

k[n_]:=k[n]=1+Sum[Times@@k/@y,{y,Select[IntegerPartitions[n],Length[#]===2&&UnsameQ@@#&]}];
Array[k,40]
(* Second program: *)
a[n_] := a[n] = 1 + Sum[a[j]*a[n - j], {j, 1, (n - 1)/2}];
a /@ Range[0, 40] (* Jean-François Alcover, May 13 2021, after Alois P. Heinz *)

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + sum(k=1, (n-1)\2, v[k]*v[n-k])); concat([1], v)} \\ Andrew Howroyd, Aug 25 2018

a(n) = 1 + Sum_{x + y = n, 0 < x < y < n} a(x) * a(y).

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

A036770 Number of labeled rooted trees with a degree constraint: (2n)!/(2^n) C(2*n+1, n).

Original entry on oeis.org

1, 3, 60, 3150, 317520, 52390800, 12843230400, 4382752374000, 1986847742880000, 1155153277710432000, 838011196011749760000, 742058914068404412480000, 787724078011075453248000000, 987468397792455300321600000000, 1443283810213452666950050560000000

Offset: 0

N. J. A. Sloane

nonn

a(n) is the number of rooted labeled strictly binary trees (each vertex has exactly two children or none) on 2*n + 1 vertices. - Geoffrey Critzer, Nov 13 2011

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 46.
Lajos Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10; see Eqs. (12) and (13) on p. 4.
Eric Weisstein's World of Mathematics, Strongly Binary Tree.
Index entries for sequences related to rooted trees

Cf. A001190, A036771, A036772, A036773, A052510.

[Factorial(2*n)/(2^n) * Binomial(2*n+1, n): n in [0..15]]; // Vincenzo Librandi, Jan 29 2020

spec := [S,{S=Union(Z,Prod(Z,Set(S,card=2)))},labeled]: seq(combstruct[count](spec,size=n)

Range[0, 19]! CoefficientList[Series[(1 - (1 - 2 x^2)^(1/2))/x, {x, 0, 20}], x] (* Geoffrey Critzer, Nov 13 2011 *)

Recurrence (with interpolated zeros): Define (b(n): n >= 0) by b(2*m+1) = a(m) and b(2*m) = 0 for m >= 0. Then the sequence (b(n): n >= 0) satisfies the recurrence (-2*n^3 - 6*n^2 - 4*n)*b(n) + (n + 3)*b(n+2) = 0 for n >= 0 with b(0) = 0 and b(1) = 1. [Corrected by Petros Hadjicostas, Jun 07 2019]
E.g.f. with interpolated zeros: G(x) = Sum_{n >= 0} b(n)*x^n/n! = Sum_{m >= 0} a(m)*x^(2*m + 1)/(2*m + 1)! = 1/x * (1 - (1 - 2*x^2)^(1/2)) for 0 < |x| < 1/sqrt(2). [Edited by Petros Hadjicostas, Jun 07 2019]
E.g.f. with interpolated zeros satisfies G(x)= x*(1 + G(x)^2/2). - Geoffrey Critzer, Nov 13 2011
D-finite with recurrence (with no interpolated zeros): -2*a(n)*(n + 1)*(2*n + 1)*(2*n + 3) + (n + 2)*a(n+1) = 0 with a(0) = 1. - Petros Hadjicostas, Jun 08 2019
G.f.: 4F1(1,1,1/2,3/2;2;8*x). - R. J. Mathar, Jan 28 2020

A300866 Signed recurrence over binary strict trees: a(n) = 1 - Sum_{x + y = n, 0 < x < y < n} a(x) * a(y).

Original entry on oeis.org

1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, -1, 1, 1, -2, 3, -1, -3, 8, -8, 1, 14, -26, 22, 10, -59, 90, -52, -74, 238, -291, 80, 417, -930, 915, 124, -1991, 3483, -2533, -2148, 9011, -12596, 5754, 14350, -37975, 42735, -4046, -77924, 154374, -133903, -56529, 376844, -591197, 355941, 522978, -1706239

Offset: 0

Gus Wiseman, Mar 13 2018

sign

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

Cf. A000992, A001190, A007317, A063834, A099323, A196545, A220418, A273866, A273873, A289501, A290261, A300442, A300443, A300862, A300863, A300864, A300865.

a[n_]:=a[n]=1-Sum[a[k]*a[n-k],{k,1,(n-1)/2}];
Array[a,40]

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 - sum(k=1, (n-1)\2, v[k]*v[n-k])); concat([1], v)} \\ Andrew Howroyd, Aug 27 2018

A301344 Regular triangle where T(n,k) is the number of semi-binary rooted trees with n nodes and k leaves.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 4, 1, 0, 0, 1, 6, 4, 0, 0, 0, 1, 9, 11, 2, 0, 0, 0, 1, 12, 24, 9, 0, 0, 0, 0, 1, 16, 46, 32, 3, 0, 0, 0, 0, 1, 20, 80, 86, 20, 0, 0, 0, 0, 0, 1, 25, 130, 203, 86, 6, 0, 0, 0, 0, 0, 1, 30, 200, 423, 283, 46, 0, 0, 0, 0, 0, 0, 1, 36, 295, 816, 786, 234, 11, 0, 0, 0, 0

Offset: 1

Gus Wiseman, Mar 19 2018

A rooted tree is semi-binary if all outdegrees are <= 2. The number of semi-binary trees with n nodes is equal to the number of binary trees with n+1 leaves; see A001190.

			Triangle begins:
1
1   0
1   1   0
1   2   0   0
1   4   1   0   0
1   6   4   0   0   0
1   9  11   2   0   0   0
1  12  24   9   0   0   0   0
1  16  46  32   3   0   0   0   0
1  20  80  86  20   0   0   0   0   0
1  25 130 203  86   6   0   0   0   0   0
The T(6,3) = 4 semi-binary rooted trees: ((o(oo))), (o((oo))), (o(o(o))), ((o)(oo)).

Cf. A000081, A000598, A001190, A001678, A003238, A004111, A055277, A111299, A273873, A290689, A291636, A292050, A298118, A298204, A298422, A298426, A301342, A301343, A301345.

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

cp's OEIS Frontend

A317718 Number of uniform relatively prime rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A319541 Triangle read by rows: T(n,k) is the number of binary rooted trees with n leaves of exactly k colors and all non-leaf nodes having out-degree 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A000672 Number of 3-valent trees (= boron trees or binary trees) with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A086317 Decimal expansion of asymptotic constant xi for counts of weakly binary trees.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A295461 Number of unlabeled rooted trees with 2n + 1 nodes in which all outdegrees are even.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A300442 Number of binary strict trees of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

A036770 Number of labeled rooted trees with a degree constraint: (2n)!/(2^n) C(2*n+1, n).