The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A335342 Number of free trees with exactly n nodes with fewer than three neighbors. 2
 1, 1, 2, 4, 9, 25, 70, 226, 753, 2675, 9785, 37087, 143487, 566952, 2274967, 9257906, 38113299, 158535204, 665364565, 2814924441, 11993967450, 51433198599, 221839745468, 961884808879, 4190783204515, 18339291329225 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS Generates and uses values from A108521, rooted trees with exactly n generators, a generator being a leaf or node with just one child. LINKS Robert A. Russell, Table of n, a(n) for n = 1..60 R. A. Russell, How many trees have n nodes with fewer than three neighbors?, MathOverflow, June 2020. FORMULA G.f.: A(x) + (x/2-1)*A^2(x) + (x/2)*A(x^2), where A(x) is the g.f. for A108521. EXAMPLE For n=4, we have 1) a node with four neighbors, 2) two adjacent nodes with three neighbors each, 3) two adjacent nodes with two neighbors each, and 4) two adjacent nodes, one having two neighbors and the other three neighbors. MATHEMATICA a = 1; a[n_] := a[n] = 1+a[n-1] + Total[Product[Binomial[a[i]-1+Count[#, i], Count[#, i]], {i, DeleteCases[DeleteDuplicates[#], 1]}] & /@ IntegerPartitions[n, {2, n-1}]]; (* A108521 *) b = 1; b[n_] := b[n] = If[n > 2, 1, 0] + If[EvenQ[n], a[n/2] (a[n/2] + 1)/2, a[(n-1)/2] (a[(n-1)/2]+1)/2] + If[n > 3, Total[If[Max[#] <= If[EvenQ[n], n/2-1, (n-1)/2], Product[Binomial[a[i] - 1 + Count[#, i], Count[#, i]], {i, DeleteCases[DeleteDuplicates[#], 1]}], 0] & /@ IntegerPartitions[n, {3, n-1}]], 0]; Table[b[n], {n, 40}] (* a[n] = A108521[n]; d[n] are coefficients of A^2(x) in g.f. *) a = 0; a = 1; a[n_] := a[n] = a[n-1] + (DivisorSum[n, a[#] # &, #

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 28 02:01 EDT 2023. Contains 362992 sequences. (Running on oeis4.)