A000992 -id:A000992 - cp's OEIS frontend

A300797 Number of strict trees of weight 2n + 1 in which all outdegrees and all leaves are odd.

1, 1, 1, 1, 2, 2, 4, 6, 11, 17, 34, 59, 118, 213, 424, 799, 1606, 3072, 6216, 12172, 24650, 48710, 99333, 198237, 405526, 815267, 1673127, 3387165, 6974702, 14179418, 29285048, 59841630, 123848399, 253927322, 526936694, 1084022437, 2253778793, 4649778115

Offset: 0

Gus Wiseman, Mar 13 2018

nonn

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

			The a(7) = 6 strict trees: 15, (11 3 1), (9 5 1), (7 5 3), ((7 3 1) 3 1), ((5 3 1) 5 1).

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

Cf. A000009, A000992, A032305, A063834, A078408, A089259, A196545, A273873, A279785, A289501, A298118, A300301, A300352, A300353, A300436, A300439, A300440, A300652.

a[n_]:=a[n]=If[OddQ[n],1,0]+Sum[Times@@a/@ptn,{ptn,Select[IntegerPartitions[n],Length[#]>1&&OddQ[Length[#]]&&UnsameQ@@#&]}];
Table[a[n],{n,1,60,2}]

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

a(30)-a(37) from Alois P. Heinz, Mar 13 2018

A374244 A Catalan-like sequence formed from the row sums of a Catalan-like triangle where row n is truncated to have ceiling((n+4)*log(3)/log(2)) - (n + 6) terms.

Original entry on oeis.org

1, 2, 5, 9, 23, 43, 113, 331, 698, 1966, 4072, 11433, 23701, 66734, 205712, 459632, 1348864, 2927822, 8499580, 26809375, 61495590, 183946295, 408179706, 1204202538, 2643267587, 7756962475, 24708004563, 57390010121, 173405214133, 389606249120, 1160606285961, 3738436950162

Offset: 1

Rob Bunce, Jul 01 2024

			Standard Catalan:
 n   Sum   Triangle terms
 1     1 = 1;
 2     2 = 1, 1;
 3     5 = 1, 2,  2;
 4    14 = 1, 3,  5; /5
 5    42 = 1, 4,  9, 14; /14
 6   132 = 1, 5, 14, 28; /42;  14
 7   429 = 1, 6, 20, 48, 90; /132; 132
...
When n=4, number of terms is restricted to 3 dropping 1 term; ceiling((4+4)*log(3)/log(2)) - (4 + 6) = 3.
When n=6, number of terms is restricted to 4 dropping 2 terms; ceiling((6+4)*log(3)/log(2)) - (6 + 6) = 4.
etc.
Truncating at the point indicated by / and summing the remaining triangle terms in the normal way results in:
n    Sum  Truncated Triangle terms
 1     1 = 1;
 2     2 = 1, 1;
 3     5 = 1, 2, 2;
 4     9 = 1, 3, 5;
 5    23 = 1, 4, 9, 9;
 6    43 = 1, 5, 14, 23;
 7   113 = 1, 6, 20, 43, 43;
 8   331 = 1, 7, 27, 70, 113, 113;
 9   698 = 1, 8, 35, 105, 218, 331;
10  1966 = 1, 9, 44, 149, 367, 698, 698;
11  4072 = 1, 10, 54, 203, 570, 1268, 1966;
12 11433 = 1, 11, 65, 268, 838, 2106, 4072, 4072;
13 23701 = 1, 12, 77, 345, 1183, 3289, 7361, 11433;
...

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

Cf. A009766, A000108, Half Catalan A000992.

Cf. A100982 (row sums of A368514).

lista(N) = {
  my(T=vector(N, n, vector(logint(3^(n+4), 2)-n-5)));
  for(n=1, #T
  , for(k=1, #T[n]
    , T[n][k]= if(1==k, 1, k<=#T[n-1], T[n][k-1]+T[n-1][k], T[n][k-1])
    );
  );
  vector(#T, n, vecsum(T[n]));
}

Same as for a normal Catalan triangle T(n,k), read by rows, each term is the sum of the entries above and to the left, i.e., T(n,k) = Sum_{j=0..k} T(n-1,j) where j is limited to the truncated length.

a(26) onwards from Andrew Howroyd, Oct 25 2024

A248748 Number of rooted binary trees with n leaves and each internal vertex colored in one of two colors.

Original entry on oeis.org

1, 2, 4, 16, 48, 192, 704, 3072, 12032, 52736, 219136, 985088, 4218880, 19144704, 84066304, 387088384, 1725497344, 7989886976, 36128948224, 168658206720, 770103574528, 3611291549696, 16636941697024, 78453223194624, 363787840389120, 1721209150504960

Offset: 1

Stanislav Sykora, Oct 13 2014

nonn

For n>1, a(n) is the number of bipolar networks one can build from n identical impedances by combining smaller networks either in series or in parallel.

Also for n>1, given two symmetric binary operations f(x,y) and g(x,y), such as two different means of x and y, one can use them (and just them) to form up to a(n) distinct expressions with n arguments x1,x2,...,x5.

			a(5)=48 because there are three binary trees with 5 leaves, namely, (1,((1,1),(1,1))); (1,(1,(1,(1,1)))); ((1,1),(1,(1,1))); and each of their four (5-1) internal vertices can be colored in 2 ways, giving rise to 3*2^4 = 48 possibilities. The "coloring" can be indicated by means of two different kinds of parentheses, for example (1,[(1,1),[1,1]]).
It also implies that 5 identical impedances can be wired together in 48 ways, iterating only simple series/parallel bondings.
Also, given two different means f(x,y) and g(x,y) of two numbers (e.g., an arithmetic and a geometric one), these can be combined to form 48 distinct means of 5 arguments x1,x2,x3,x4,x5. One such mean, for example, is f(x1,g(f(x2,x3),g(x4,x5))), corresponding to (1,[(1,1),[1,1]]).

Stanislav Sykora, Table of n, a(n) for n = 1..1000

Cf. A000992.

v=vector(1000); v[1]=1; \\ Use any desired size
for(n=2,#v, v[n]=sum(k=1,n\2,v[k]*v[n-k])); \\ v = A000992
for(n=1,#v, v[n]*=2^(n-1)); v \\ Final multiplication and result display

a(n) = A000992(n)*2^(n-1).

A335833 Triangle read by rows. T(n,k) is the number of full binary trees with n leaves and with k internal nodes whose left and right children have the same number of leaf descendants, where n > 0 and 0 <= k < n.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 2, 2, 1, 0, 0, 1, 4, 3, 3, 0, 0, 0, 1, 6, 7, 6, 3, 0, 1, 0, 1, 9, 14, 13, 8, 1, 1, 0, 0, 1, 12, 27, 28, 23, 8, 3, 1, 0, 0, 1, 16, 49, 58, 54, 25, 8, 3, 0, 0, 0, 1, 20, 82, 119, 125, 82, 34, 15, 2, 1, 0

Offset: 1

Laura Monroe, Jun 25 2020

Consider a full binary tree with n unlabeled leaves, such that for every internal node, the number of leaf descendants of the left child is greater than or equal to the number of leaf descendants of the right child. Two such trees are considered isomorphic if one may be obtained from the other by some series of transpositions of left and right children. Label an internal nodes S if its two children have the same number of leaf descendants, and D if its two children have a different number of leaf descendants, and call this an SD-tree. T(n,k) is then the number of distinct trees having n > 0 leaves and 0 <= k < n S-nodes, read by rows (Monroe et al., proposition 38).
Binary operations that are commutative and non-associative map to this type of tree. One example of this kind of operation is floating-point summation on n summands on a machine adhering to IEEE 754 arithmetic standards. Another example is a single-elimination tournament on n teams (A096351), which always has A268289(n-1) S-nodes.
Column 1 gives A000012 (Monroe et al., proposition 11 and remark 42).
Column 2 gives A002620 (Monroe et al., proposition 18).
Row sums give A000992 (Monroe et al., proposition 36 and remark 42).
T(n,n-1) is 1 if n = 2^k and is 0 otherwise. This is true because there are exactly n-1 internal nodes on a binary tree with n leaves, and the only way for all of these to be S-nodes is if the tree is the unique perfect tree with 2^k leaves.
T(n,1) is the first non-0 entry in row n, when n>1. T(n,A011371(n)) is the last non-0 entry in row n. (Monroe et al., propositions 27 and 34)
The number of unique leaf-labeled full binary trees of isomorphic parenthetic form with exactly k >= 1 S-nodes is n!/(2^k) (Monroe et al., corollary 4). There are then T(n,k)*n!/(2^k) not necessarily isomorphic unique leaf-labeled full binary trees having exactly k nodes. For example, serial summation, where the parenthesization is in summand order, as in (...(((a+b)+c)+d)+...), always has exactly 1 S-node, so there are n!/2 possible serial summations (Monroe et al., lemmas 8 and 9, corollary 10, and proposition 11).
The comments above that suggest that this sequence enumerates binary trees up to transpositions of left and right children appear to be incorrect. This sequence rather enumerates those trees as specified in the opening paragraph: for every internal node, the number of leaf descendants of the left child is greater than or equal to the number of leaf descendants of the right child. This is the difference between A000992 which is the row sums of this sequence and A001190. The two diverge for n >= 8. The remark that commutative binary operations map to this type of tree is, therefore, also incorrect. - Andrew Howroyd, Mar 25 2023

			The table for T(n,k) begins:
  n\k 0   1   2   3    4    5    6    7    8   9  10  11  12  13  14  15
   1  1
   2  0   1
   3  0   1   0
   4  0   1   0   1
   5  0   1   1   1    0
   6  0   1   2   2    1    0
   7  0   1   4   3    3    0    0
   8  0   1   6   7    6    3    0    1
   9  0   1   9  14   13    8    1    1    0
  10  0   1  12  27   28   23    8    3    1   0
  11  0   1  16  49   58   54   25    8    3   0   0
  12  0   1  20  82  119  125   82   34   15   2   1   0
  13  0   1  25 132  237  270  213   99   42   8   3   0   0
  14  0   1  30 199  449  578  542  322  151  51  11   3   0   0
  15  0   1  36 294  821 1190 1255  867  440 173  39  15   0   0   0
  16  0   1  42 414 1419 2394 2841 2338 1388 656 215  79  18   7   0   1
  ...
The complete set of non-isomorphic 4-leaf SD-trees is:
        D            S
       / \          / \
      D   *        S   S
     / \          /|   |\
    S   *        * *   * *
   / \
  *   *
T(6,2) = 2 gives the first example of a set of parameters n and k that has more than one non-isomorphic SD-tree. The complete set of non-isomorphic 6-leaf 2-S-node SD-trees is:
          D                 D
         / \               / \
        D   S             D   *
       / \  |\           / \
      D   * * *         D   S
     / \               / \  |\
    S   *             S   * * *
   / \               / \
  *   *             *   *
From _Andrew Howroyd_, Apr 12 2023: (Start)
When n = 8 there are two trees, illustrated below, which are isomorphic (up to exchange of left and right children), but are counted separately by this sequence:
             S                     S
           /   \                 /   \
          D     S              S      D
        / |     | \          / |      | \
       D  *     S  S        S  S      D  *
     /  \      /|  |\      /|  |\     | \
    S    *    * *  * *    * *  * *    S  *
   / \                               / \
  *   *                             *   *
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows).
Laura Monroe, A Class of Trees Having Near-Best Balance, arXiv:2108.11496 [cs.DM], 2021.
Laura Monroe and Vanessa Job, Computationally Inequivalent Summations and Their Parenthetic Forms, arXiv:2005.05387 [cs.DM], 2020.

Cf. A000012, A000992, A002620, A011371, A096351, A268289.

using Memoize
@memoize function T(n, k)
    k > n-1 && return 0
    (n==1) && (k==0) && return 1
    t, h = 0, n>>1
    for j in 1:h-1, i in 0:k
            t += T(j, i)*T(n-j, k-i)
    end
    if n&1 > 0
        for i in 0:k
            t += T(h, i)*T(h+1, k-i)
        end
    else
        for i in 0:k
            t += T(h, i)*T(h, k-i-1)
        end
    end
    t
end
for n in 1:16
    [T(n,k) for k in 0:n-1] |> println
end # Peter Luschny, Jun 26 2020

T(n)={my(v=vector(n)); v[1] = 1; for(n=2, n, v[n] = (polcoef(Ser(v[1..n])^2, n-2) + if(n%2==0, (2*y-1)*v[n/2]^2))/2); vector(#v, n, Vecrev(v[n], n))}
{ my(A=T(12)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Mar 25 2023

T(n,k) = 0, if k >= n. T(n,k) = 1, if n = 1 and k = 0.
T(n,k) = Sum_{j=1..floor((n-1)/2)} Sum_{i=0..k} T(j,i)*T(n-j,k-i), if n is odd and > 1.
T(n,k) = Sum_{j=1..floor((n-1)/2)} Sum_{i=0..k} T(j,i)*T(n-j,k-i) + Sum_{i=0..k-1} T(n/2,i)*T(n/2,k-1-i), if n is even.

A030033 a(n+1) = Sum_{k = 0..floor(2n/3)} a(k)a(n-k) for n >= 0 with a(0) = 1.

Original entry on oeis.org

1, 1, 1, 2, 4, 7, 15, 34, 72, 165, 387, 861, 2039, 4894, 11256, 27085, 66021, 156347, 381720, 940211, 2261208, 5578659, 13846756, 33654950, 83539418, 208608556, 512069441, 1278522424, 3207377196, 7925966000

Offset: 0

N. J. A. Sloane

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A000992, A030032, A030037.

a := proc(n) local k; option remember;
     if n = 0 then 1;
     else add(a(k)*a(n - 1 - k), k = 0 .. floor(2/3*n - 2/3));
     end if;
end proc;
seq(a(n), n = 0..30); # Petros Hadjicostas, Nov 07 2019

Name edited by Petros Hadjicostas, Nov 07 2019

A030035 a(n+1) = Sum_{k=0..floor(3n/4)} a(k) a(n-k).

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 17, 38, 89, 213, 480, 1151, 2810, 6978, 16497, 40731, 101680, 256491, 623916, 1568966, 3972773, 10130647, 25044032, 63573638, 162478685, 417322917, 1049096179, 2687278965, 6917001254, 17882746627, 45391766669, 116995255065, 302689722551

Offset: 0

N. J. A. Sloane

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A000992, A030034, A030038.

lista(nn) = {my(v=vector(nn+2, i, 1)); for(n=1, nn, v[n+2]=sum(k=1, 1+(3*n)\4, v[k]*v[n+2-k])); v; } \\ Jinyuan Wang, Mar 18 2020

More terms from Jinyuan Wang, Mar 18 2020

A348530 a(1) = 1; a(n) = Sum_{k=1..ceiling(n/2)} a(k) * a(n-k).

Original entry on oeis.org

1, 1, 2, 3, 7, 14, 33, 70, 173, 400, 1008, 2391, 6132, 15019, 38799, 96520, 252022, 638788, 1679091, 4297452, 11373921, 29426350, 78204705, 203658812, 543828898, 1426912159, 3822817135, 10078227662, 27092960887, 71803114869, 193496832857, 514684042158

Offset: 1

Ilya Gutkovskiy, Oct 21 2021

nonn

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

Cf. A000108, A000992.

a:= proc(n) option remember; `if`(n=1, 1,
      add(a(k)*a(n-k), k=1..ceil(n/2)))
    end:
seq(a(n), n=1..32);  # Alois P. Heinz, Oct 21 2021

a[1] = 1; a[n_] := a[n] = Sum[a[k] a[n - k], {k, 1, Ceiling[n/2]}]; Table[a[n], {n, 1, 32}]

A030040 a(n+1) = Sum_{k=0..floor(n/tau)} a(k) * a(n-k), where tau = (1+sqrt(5))/2.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 13, 26, 57, 117, 262, 602, 1329, 3079, 7245, 16503, 38869, 89113, 210974, 504309, 1179630, 2824021, 6635307, 15941802, 38557737, 91823353, 222366338, 541354461, 1299734664, 3164349333, 7610216362, 18557153445, 45434487823, 110039888736

Offset: 0

N. J. A. Sloane

nonn

Cf. A000992, A001622.

lista(nn) = {my(v=vector(nn+2, i, 1)); for(n=1, nn, v[n+2]=sum(k=1, 1+n\((1+sqrt(5))/2), v[k]*v[n+2-k])); v; } \\ Jinyuan Wang, Mar 18 2020

More terms from Jinyuan Wang, Mar 18 2020

A030041 a(n+1) = Sum_{k=0..sqrt(n)} a(k) * a(n-k).

Original entry on oeis.org

1, 1, 2, 3, 5, 12, 23, 45, 92, 183, 434, 936, 2012, 4365, 9551, 20748, 45065, 108070, 245109, 553308, 1253492, 2846553, 6482338, 14721344, 33423804, 75916943, 187505118, 441004027, 1032009219, 2419549459, 5676752449, 13331861333, 31398821908, 73794930935

Offset: 0

N. J. A. Sloane

nonn

Cf. A000992.

lista(nn) = {my(v=vector(nn+2, i, 1)); for(n=0, nn, v[n+2]=sum(k=1, 1+sqrt(n), v[k]*v[n+2-k])); v; } \\ Jinyuan Wang, Mar 18 2020

More terms from Jinyuan Wang, Mar 18 2020

A335562 Number of unlabelled unary-binary trees with n nodes such that every node with two children has children of different subtree sizes.

Original entry on oeis.org

1, 1, 1, 3, 5, 13, 29, 71, 165, 421, 1029, 2647, 6593, 17241, 43801, 115555, 297513, 791337, 2062737, 5516755, 14497373, 38994597, 103269053, 278921927, 742950845, 2014648253, 5396210357, 14677306503, 39477832745, 107701409665, 290871580345, 795431700707, 2155140605137

Offset: 1

Marcel K. Goh, Jun 14 2020

nonn

Cf. A000992.

lista(nn) = {my(va = vector(nn)); va[1] = 1; for (n=2, nn, va[n] = va[n-1] + sum(k=1, n-2, if (k != n-k-1, va[k]*va[n-k-1]));); va;} \\ Michel Marcus, Jun 14 2020

a(1) = 1, a(n) = a(n-1) + Sum_{k=1..n-2} (a(k)*a(n-k-1)*[k != n-k-1]).

cp's OEIS Frontend

A300797 Number of strict trees of weight 2n + 1 in which all outdegrees and all leaves are odd.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A374244 A Catalan-like sequence formed from the row sums of a Catalan-like triangle where row n is truncated to have ceiling((n+4)*log(3)/log(2)) - (n + 6) terms.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A248748 Number of rooted binary trees with n leaves and each internal vertex colored in one of two colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A335833 Triangle read by rows. T(n,k) is the number of full binary trees with n leaves and with k internal nodes whose left and right children have the same number of leaf descendants, where n > 0 and 0 <= k < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Julia

PARI

Formula

A030033 a(n+1) = Sum_{k = 0..floor(2*n/3)} a(k)*a(n-k) for n >= 0 with a(0) = 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Extensions

A030035 a(n+1) = Sum_{k=0..floor(3*n/4)} a(k) * a(n-k).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A348530 a(1) = 1; a(n) = Sum_{k=1..ceiling(n/2)} a(k) * a(n-k).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A030040 a(n+1) = Sum_{k=0..floor(n/tau)} a(k) * a(n-k), where tau = (1+sqrt(5))/2.

Views

Author

Keywords

Crossrefs

Programs

A030033 a(n+1) = Sum_{k = 0..floor(2n/3)} a(k)a(n-k) for n >= 0 with a(0) = 1.

A030035 a(n+1) = Sum_{k=0..floor(3n/4)} a(k) a(n-k).