A007562 -id:A007562 - cp's OEIS frontend

A007439 Number of planted trees: all sub-rooted trees from any node are identical; non-root, non-leaf nodes an even distance from the root are of degree 2.

1, 1, 1, 2, 2, 4, 3, 7, 4, 11, 6, 15, 7, 24, 8, 29, 12, 40, 13, 51, 14, 68, 19, 76, 20, 107, 23, 116, 29, 147, 30, 175, 31, 215, 39, 229, 45, 297, 46, 312, 55, 387, 56, 435, 57, 513, 73, 534, 74, 670, 78, 705, 92, 823, 93, 897, 102, 1051, 117, 1082

Offset: 1

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..1000
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A003238, A007562.

Cf. A027750.

a007439 n = a007439_list !! (n-1)
a007439_list = 1 : 1 : f 2 where
   f x = (sum $ map a007439 $ a027750_row (x - 1)) : f (x + 1)
-- Reinhard Zumkeller, Dec 20 2014

a[n_] := a[n] = Sum[a[k], {k, Divisors[n-2]}]; a[1] = a[2] = 1; Table[a[n], {n, 1, 60}] (* Jean-François Alcover, May 15 2013 *)

a(n+2) = Sum a(k), k|n. Shifts left two places under inverse Moebius transformation.

G.f. A(x) satisfies: A(x) = x + x^2 * (1 + A(x) + A(x^2) + A(x^3) + ...). - Ilya Gutkovskiy, May 09 2019

New description from Christian G. Bower, Oct 15 1998

A007560 Number of planted identity trees where non-root, non-leaf nodes an even distance from root are of degree 2.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 6, 10, 17, 29, 51, 89, 159, 284, 512, 930, 1692, 3101, 5698, 10515, 19464, 36143, 67296, 125622, 235050, 440756, 828142, 1558955, 2939761, 5552744, 10504222, 19899760, 37750091, 71704061, 136361602, 259618770, 494821629, 944074665

Offset: 1

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..1000
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version]
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

Cf. A007562.

Column k=2 of A316074.

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(a(i), j)*b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> `if`(n<2, n, b(n-2, n-2)):
seq(a(n), n=1..50);  # Alois P. Heinz, May 19 2013

b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[a[i], j]*b[n-i*j, i-1], {j, 0, n/i}]]]; a[n_] := If[n<2, n, b[n-2, n-2]]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Jan 27 2014, after Alois P. Heinz *)

Shifts 2 places left under weigh transform.
a(n) ~ c * d^n / n^(3/2), d = 1.983229991815043367273184141..., c = 0.5857451140002020594085469... . - Vaclav Kotesovec, Aug 25 2014
G.f.: x + x^2 * Product_{n>=1} (1 + x^n)^a(n). - Ilya Gutkovskiy, May 09 2019

Better description from Christian G. Bower, May 15 1998

A144018 Triangle T(n,k), n >= 1, 1 <= k <= n, read by rows, where sequence a_k of column k has a_k(0)=0, followed by (k+1)-fold 1 and a_k(n) shifts k places left under Euler transform.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 9, 3, 2, 1, 1, 20, 6, 3, 2, 1, 1, 48, 10, 5, 3, 2, 1, 1, 115, 20, 8, 5, 3, 2, 1, 1, 286, 36, 14, 7, 5, 3, 2, 1, 1, 719, 72, 23, 12, 7, 5, 3, 2, 1, 1, 1842, 137, 40, 18, 11, 7, 5, 3, 2, 1, 1, 4766, 275, 69, 30, 16, 11, 7, 5, 3, 2, 1, 1, 12486, 541, 121, 47, 25, 15, 11, 7, 5, 3, 2, 1, 1

Offset: 1

Alois P. Heinz, Sep 07 2008

			T(5,1) = ([1,2,4]*[1,1,4] + [1]*[1]*4 + [1,2]*[1,1]*2 + [1,3]*[1,2]*1)/4 = 36/4 = 9.
Triangle begins:
    1;
    1,  1;
    2,  1,  1;
    4,  2,  1,  1;
    9,  3,  2,  1, 1;
   20,  6,  3,  2, 1, 1;
   48, 10,  5,  3, 2, 1, 1;
  115, 20,  8,  5, 3, 2, 1, 1;
  286, 36, 14,  7, 5, 3, 2, 1, 1;
  719, 72, 23, 12, 7, 5, 3, 2, 1, 1;

Alois P. Heinz, Rows n = 1..141, flattened
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version]
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
N. J. A. Sloane, Transforms

Columns k=1..10 give A000081, A007562, A218020, A218021, A218022, A218023, A218024, A218025, A218026, A218027.
T(2n,n) gives A000041(n).
Cf. A316074.

etrk:= proc(p) proc(n, k) option remember; `if`(n=0, 1,
         add(add(d*p(d, k), d=numtheory[divisors](j))*
         procname(n-j, k), j=1..n)/n)
       end end:
B:= etrk(T):
T:= (n, k)-> `if`(n<=k, `if`(n=0, 0, 1), B(n-k, k)):
seq(seq(T(n, k), k=1..n), n=1..14);

etrk[p_] := Module[{f}, f[n_, k_] := f[n, k] = If[n == 0, 1, (Sum[Sum[d*p[d, k], {d, Divisors[j]}]*f[n-j, k], {j, 1, n-1}] + Sum[d*p[d, k], {d, Divisors[n]}])/n]; f]; b = etrk[t]; t[n_, k_] := If[n <= k, If[n == 0, 0, 1], b[n-k, k]]; Table[t[n, k], {n, 1, 13}, {k, 1, n}] // Flatten (* Jean-François Alcover, Aug 01 2013, after Alois P. Heinz *)

A320767 Inverse Euler transform applied once to {1,-1,0,0,0,...}, twice to {1,0,0,0,0,...}, or three times to {1,1,1,1,1,...}.

Original entry on oeis.org

1, 1, -2, 1, -1, 2, -3, 4, -5, 8, -13, 18, -25, 40, -62, 90, -135, 210, -324, 492, -750, 1164, -1809, 2786, -4305, 6710, -10460, 16264, -25350, 39650, -62057, 97108, -152145, 238818, -375165, 589520, -927200, 1459960, -2300346, 3626200, -5720274, 9030450

Offset: 0

Gus Wiseman, Oct 20 2018

sign

The Euler transform of a sequence q is the sequence of coefficients of x^n, n > 0, in the expansion of Product_{n > 0} 1/(1 - x^n)^q(n). The constant term 1 is sometimes taken to be the zeroth part of the Euler transform.

Cf. A000081, A001970, A007562, A007294, A034691, A059966, A061255, A061256, A061257, A065490, A073576, A117209.

EulerInvTransform[{}]={};EulerInvTransform[seq_]:=Module[{final={}},For[i=1,i<=Length[seq],i++,AppendTo[final,i*seq[[i]]-Sum[final[[d]]*seq[[i-d]],{d,i-1}]]];
Table[Sum[MoebiusMu[i/d]*final[[d]],{d,Divisors[i]}]/i,{i,Length[seq]}]];
Nest[EulerInvTransform,Array[DiscreteDelta,50,0],2]

A143363 Number of ordered trees with n edges and having no protected vertices. A protected vertex in an ordered tree is a vertex at least 2 edges away from its leaf descendants.

Original entry on oeis.org

1, 1, 1, 3, 6, 17, 43, 123, 343, 1004, 2938, 8791, 26456, 80597, 247091, 763507, 2372334, 7413119, 23271657, 73376140, 232238350, 737638868, 2350318688, 7510620143, 24064672921, 77294975952, 248832007318, 802737926643

Offset: 0

Emeric Deutsch, Aug 20 2008

nonn

The "no protected vertices" condition can be rephrased as "every non-leaf vertex has at least one leaf child". But a(n) is also the number of ordered trees with n edges in which every non-leaf vertex has at most one leaf child. - David Callan, Aug 22 2014
Also the number of locally non-intersecting ordered rooted trees with n edges, meaning every non-leaf subtree has empty intersection. The unordered version is A007562. - Gus Wiseman, Nov 19 2022
a(n) is the number of parking functions of size n-1 avoiding the patterns 123, 132, and 213 . - Lara Pudwell, Apr 10 2023
For n>0, a(n) is the number of ways to place non-intersecting diagonals in convex n+3-gon so as to create no triangles such that none of the dividing diagonals passes through a chosen vertex. (empirical observation) - Muhammed Sefa Saydam, Feb 14 2025 and Aug 05 2025

			From _Gus Wiseman_, Nov 19 2022: (Start)
The a(0) = 1 through a(4) = 6 trees with at least one leaf directly under any non-leaf node:
  o  (o)  (oo)  (ooo)   (oooo)
                ((o)o)  ((o)oo)
                (o(o))  ((oo)o)
                        (o(o)o)
                        (o(oo))
                        (oo(o))
The a(0) = 1 through a(4) = 6 trees with at most one leaf directly under any node:
  o  (o)  ((o))  ((o)o)   (((o))o)
                 (o(o))   (((o)o))
                 (((o)))  ((o)(o))
                          ((o(o)))
                          (o((o)))
                          ((((o))))
(End)

Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
Gi-Sang Cheon and Louis W. Shapiro, Protected points in ordered trees, Appl. Math. Letters, 21, 2008, 516-520.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.

Cf. A143362.
For exactly one leaf directly under any node we have A006013.
The unordered version is A007562, ranked by A316470.
Allowing lone children gives A319378.
A000108 counts ordered rooted trees, unordered A000081.
A358453 counts transitive ordered trees, unordered A290689.
A358460 counts locally disjoint ordered trees, unordered A316473.
Cf. A318185, A324756, A324767, A324840, A324844.

p:=z^2*G^3-2*z*G^2-2*z^2*G^2+3*z*G+G+z^2*G-1-2*z=0: G:=RootOf(p,G): Gser:= series(G,z=0,33): seq(coeff(Gser,z,n),n=0..28);

a[n_Integer] := a[n] = Round[SeriesCoefficient[2 (x + 1 - Sqrt[x^2 - x + 1] Cos[ArcTan[(3 x Sqrt[12 x^3 - 96 x^2 - 24 x + 15])/(2 x^3 - 30 x^2 - 3 x + 2)]/3])/(3 x), {x, 0, n}]]; Table[a[n], {n, 0, 20}] (* Vladimir Reshetnikov, Apr 10 2022 *)
RecurrenceTable[{25 (n + 5) (n + 6) a[n + 5] - 10 (n + 5) (5 n + 21) a[n + 4] - 2 (77 n^2 + 613 n + 1185) a[n + 3] + 2 (50 n^2 + 253 n + 312) a[n + 2] + 4 (2 n + 1) (7 n + 9) a[n + 1] - 4 n (2 n + 1) a[n] == 0, a[0] == 1, a[1] == 1, a[2] == 1, a[3] == 3, a[4] == 6}, a[n], {n, 0, 27}] (* Vladimir Reshetnikov, Apr 11 2022 *)
ait[n_]:=ait[n]=If[n==1,{{}},Join@@Table[Select[Tuples[ait/@c],MemberQ[#,{}]&],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[ait[n]],{n,15}] (* Gus Wiseman, Nov 19 2022 *)

a(n) = A143362(n,0) for n>=1.
G.f.: G=G(z) satisfies z^2*G^3-2z(1+z)G^2+(1+3z+z^2)G-(1+2z)=0.
G.f.: (x+1-sqrt(x^2-x+1)*cos(arctan((3*x*sqrt(12*x^3-96*x^2-24*x+15))/(2*x^3-30*x^2-3*x+2))/3))*2/(3*x). - Vladimir Reshetnikov, Apr 10 2022
Recurrence: 25*(n+5)*(n+6)*a(n+5) - 10*(n+5)*(5*n+21)*a(n+4) - 2*(77*n^2+613*n+1185)*a(n+3) + 2*(50*n^2+253*n+312)*a(n+2) + 4*(2*n+1)*(7*n+9)*a(n+1) - 4*n*(2*n+1)*a(n) = 0. - Vladimir Reshetnikov, Apr 11 2022
From Muhammed Sefa Saydam, Jul 12 2025: (Start)
a(n) =  Sum_{k=2..n+2} A046736(k) * A046736(n-k+3) , for n >= 0 and A046736(1) = 1.
a(n) = A049125(n) + Sum_{k=1..n-2} A049125(k) * A046736(n-k+2), for n >= 3.
a(n) = A049125(n) + Sum_{k=1..n-2} a(k) * a(n-k-1), for n >= 3. (End)

A317748 Irregular triangle where T(n,k) is the number of factorizations of n into factors > 1 with GCD d = A027750(n, k).

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 2, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 3, 1, 0, 1, 0, 1, 2, 0, 1, 0, 0, 1, 0, 1, 2, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 3, 3, 0, 0, 0, 0, 0, 1, 0, 1, 1

Offset: 1

Gus Wiseman, Aug 06 2018

			Triangle begins:
   1:  0
   2:  0  1
   3:  0  1
   4:  0  1  1
   5:  0  1
   6:  1  0  0  1
   7:  0  1
   8:  0  2  0  1
   9:  0  1  1
  10:  1  0  0  1
  11:  0  1
  12:  2  1  0  0  0  1
  13:  0  1
  14:  1  0  0  1
  15:  1  0  0  1
  16:  0  3  1  0  1
  17:  0  1
  18:  2  0  1  0  0  1
  19:  0  1
  20:  2  1  0  0  0  1

Row lengths are A000005. Row sums are A001055. First column is A281116. Number of nonzero terms in each row is A317751.
Cf. A007562, A007716, A014963, A027750, A045778, A050370, A162247, A289509, A303386, A303546.
Cf. A317752, A317755, A317757.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
goc[n_,m_]:=Length[Select[facs[n],And[And@@(Divisible[#,m]&/@#),GCD@@(#/m)==1]&]];
Table[goc[n,d],{n,30},{d,Divisors[n]}]

Name edited by Peter Munn, Mar 05 2025

A316500 Number of unlabeled rooted identity trees with n nodes in which the branches of any node with more than one branch have empty intersection.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 11, 22, 46, 96, 205, 442, 976, 2146, 4789, 10719, 24202, 54841, 124967, 285724, 656011, 1510929, 3491151, 8088692, 18790084

Offset: 1

Gus Wiseman, Jul 05 2018

			The a(7) = 11 rooted identity trees:
  ((((((o))))))
  ((((o(o)))))
  (((o((o)))))
  ((o(((o)))))
  ((o(o(o))))
  (((o)((o))))
  (o((((o)))))
  (o((o(o))))
  (o(o((o))))
  ((o)(((o))))
  (o(o)((o)))

Cf. A000081, A004111, A007562, A078374, A289509, A316469, A316471, A316474, A316501, A316503.

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

A316501 Number of unlabeled rooted trees with n nodes in which the branches of any node with more than one distinct branch have empty intersection.

Original entry on oeis.org

1, 1, 2, 4, 9, 19, 45, 103, 250, 611, 1528, 3853, 9875, 25481, 66382, 174085, 459541, 1219462

Offset: 1

Gus Wiseman, Jul 05 2018

			The a(6) = 19 rooted trees:
  (((((o)))))
  ((((oo))))
  (((o(o))))
  (((ooo)))
  ((o((o))))
  ((o(oo)))
  (((o)(o)))
  ((oo(o)))
  ((oooo))
  (o(((o))))
  (o((oo)))
  (o(o(o)))
  (o(ooo))
  ((o)((o)))
  (oo((o)))
  (oo(oo))
  (o(o)(o))
  (ooo(o))
  (ooooo)

Cf. A000081, A007562, A289509, A302796, A316470, A316473, A316475, A316500, A316502.

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

A319379 Number of plane trees with n nodes where the sequence of branches directly under any given node is a chain of multisets.

Original entry on oeis.org

1, 1, 2, 4, 9, 19, 43, 93, 207, 452, 997, 2176, 4776, 10418, 22781, 49674, 108421

Offset: 1

Gus Wiseman, Sep 17 2018

			The a(6) = 19 chain trees:
  (((((o)))))  ((((oo))))  (((ooo)))  ((oooo))  (ooooo)
               (((o)(o)))  ((o)(oo))  (o(ooo))
               (((o(o))))  ((o(oo)))  (oo(oo))
               ((o((o))))  ((oo(o)))  (ooo(o))
               (o(((o))))  (o((oo)))
                           (o(o)(o))
                           (o(o(o)))
                           (oo((o)))

Gus Wiseman, The a(9) = 207 chain trees.

Cf. A000081, A000108, A001003, A005043, A007562, A118376, A143363, A316470, A319122, A319378, A319380, A319381.

submultisetQ[M_,N_]:=Or[Length[M]==0,MatchQ[{Sort[List@@M],Sort[List@@N]},{{x_,Z___},{_,x_,W___}}/;submultisetQ[{Z},{W}]]];
chnplane[n_]:=If[n==1,{{}},Join@@Table[Select[Tuples[chnplane/@c],And@@submultisetQ@@@Partition[#,2,1]&],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[chnplane[n]],{n,10}]

A319380 Number of plane trees with n nodes where the sequence of branches directly under any given node is a chain of distinct multisets.

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 9, 17, 30, 53, 94, 169, 303, 543, 968, 1728, 3080, 5491, 9776, 17415, 31008

Offset: 1

Gus Wiseman, Sep 17 2018

			The a(8) = 17 locally identity chain trees:
  (((((((o)))))))  (((((o(o))))))  (((o(o(o)))))  (o(o(o(o))))
                   ((((o((o))))))  ((o((o(o)))))  (o(o)(o(o)))
                   (((o(((o))))))  ((o(o((o)))))
                   ((o((((o))))))  (((o)(o(o))))
                   (o(((((o))))))  (o(((o(o)))))
                                   (o((o((o)))))
                                   (o(o(((o)))))
                                   ((o)(o((o))))
                                   (((o))(o(o)))

Gus Wiseman, The a(12) = 169 identity chain trees.

Cf. A000081, A000108, A001003, A005043, A007562, A118376, A316470, A319122, A319379, A319381.

submultisetQ[M_,N_]:=Or[Length[M]==0,MatchQ[{Sort[List@@M],Sort[List@@N]},{{x_,Z___},{_,x_,W___}}/;submultisetQ[{Z},{W}]]];
idchnplane[n_]:=If[n==1,{{}},Join@@Table[Select[Tuples[idchnplane/@c],And[UnsameQ@@#,And@@submultisetQ@@@Partition[#,2,1]]&],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[idchnplane[n]],{n,10}]

cp's OEIS Frontend

A007439 Number of planted trees: all sub-rooted trees from any node are identical; non-root, non-leaf nodes an even distance from the root are of degree 2.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

Extensions

A007560 Number of planted identity trees where non-root, non-leaf nodes an even distance from root are of degree 2.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A144018 Triangle T(n,k), n >= 1, 1 <= k <= n, read by rows, where sequence a_k of column k has a_k(0)=0, followed by (k+1)-fold 1 and a_k(n) shifts k places left under Euler transform.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A320767 Inverse Euler transform applied once to {1,-1,0,0,0,...}, twice to {1,0,0,0,0,...}, or three times to {1,1,1,1,1,...}.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A143363 Number of ordered trees with n edges and having no protected vertices. A protected vertex in an ordered tree is a vertex at least 2 edges away from its leaf descendants.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A317748 Irregular triangle where T(n,k) is the number of factorizations of n into factors > 1 with GCD d = A027750(n, k).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Extensions

A316500 Number of unlabeled rooted identity trees with n nodes in which the branches of any node with more than one branch have empty intersection.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A316501 Number of unlabeled rooted trees with n nodes in which the branches of any node with more than one distinct branch have empty intersection.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica