A006241 Number of minimal plane trees with n terminal nodes.

1, 1, 1, 2, 1, 3, 1, 6, 2, 3, 1, 20, 1, 3, 3, 54, 1, 34, 1, 44, 3, 3, 1, 764, 2, 3, 10, 140, 1, 283, 1, 4470, 3, 3, 3, 10416, 1, 3, 3, 10820, 1, 2227, 1, 2060, 62, 3, 1, 958476, 2, 250, 3, 8204, 1, 59154, 3, 316004, 3, 3, 1, 3457904, 1, 3, 158, 30229110, 3

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

In equation (4.4) Lew says a(p^3) = 3+3^p, but this is incorrect, it should be a(p^3) = 2+2^p. - Sean A. Irvine, Feb 07 2017

From Gus Wiseman, Jan 15 2017: (Start)

Number of same-trees of weight n with all leaves equal to 1. A same-tree is either: (case 1) a positive integer, or (case 2) a finite sequence of two or more same-trees all having the same weight, where the weight in case 2 is the sum of weights.

For n>1, a(n) is also equal to the number of same-trees of weight n with all leaves greater than 1 (see example). (End)

Examples

			The a(12)=20 same-trees with all leaves greater than 1 are:
12, (3333), (222222), ((33)(33)), ((33)(222)), ((33)6), ((222)(33)), ((222)(222)), ((222)6), (6(33)), (6(222)), (66), ((22)(22)(22)), ((22)(22)4), ((22)4(22)), ((22)44), (4(22)(22)), (4(22)4), (44(22)), (444). - _Gus Wiseman_, Jan 15 2017
		

References

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

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• J. S. Lew, Polynomial enumeration of multidimensional lattices, Math. Systems Theory, 12 (1978), 253-270.
• Gus Wiseman, Same trees with all leaves equal to one n=1..15
• Index entries for sequences related to trees

Crossrefs

Cf. A001003, A281145.

Programs

Maple

a:= proc(n) option remember; `if`(n=1, 1, add(
      a(n/d)^d, d=numtheory[divisors](n) minus {1}))
    end:
seq(a(n), n=1..70);  # Alois P. Heinz, Feb 21 2017

Mathematica

Array[If[#1===1,1,Sum[#0[#1/d]^d,{d,Rest[Divisors[#1]]}]]&,200] (* Gus Wiseman, Jan 15 2017 *)

Formula

a(1)=a(2)=a(3)=a(5)=a(7)=1, a(4)=2, a(6)=3, a(n) = Sum_{1 != d | n} a(n / d)^d [From Lew]. - Sean A. Irvine, Feb 07 2017 [typo corrected by Ilya Gutkovskiy, Apr 24 2019]

Extensions

a(8), a(27), and a(50) corrected by Sean A. Irvine, Feb 07 2017