A006241 Number of minimal plane trees with n terminal nodes. (Formerly M0133)

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,4

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)

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

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]

Example

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

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 *)

Crossrefs

Cf. A001003, A281145.

Sequence in context: A140352 A277130 A082588 * A336105 A282601 A363273

Adjacent sequences: A006238 A006239 A006240 * A006242 A006243 A006244

Keyword

nonn

Author

N. J. A. Sloane

Extensions

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

Status

approved