login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A324969 Number of unlabeled rooted identity trees with n vertices whose non-leaf terminal subtrees are all different. 5
1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

A rooted identity tree is an unlabeled rooted tree with no repeated branches directly under the same root. This sequence counts rooted identity trees satisfying the additional condition that all non-leaf terminal subtrees are different.

Appears to be essentially the same as the Fibonacci sequence A000045. - R. J. Mathar, Mar 28 2019

From Michael Somos, Nov 22 2019: (Start)

A terminal subtree T' of a tree T is a subtree all of whose vertices except one have the same degree in T' as in T itself.

The conjecture of Mathar is true. Proof: Given a rooted identity tree T, a terminal subtree T' with more than one vertex contains at least one edge that is also a terminal subtree of T'. Thus, if T has more than one branch with more than one vertex, then it fails the additional condition since it would have at least two non-leaf terminal subtrees (namely edges) that are the same.  Also, T can't have under its root more than one branch with exactly one vertex because it is an identity tree. Now we know that under the root of T is exactly one branch of the same kind as T or else it has exactly one other branch with exactly one vertex. The leads immediately to the same recurrence as A000045 the Fibonacci sequence except for n=3. (End)

LINKS

Table of n, a(n) for n=1..41.

FORMULA

G.f.: (x - x^3) / (1 - x - x^2) = x*(1 + x/(1 - x/(1 - x/(1 + x)))). a(n) = A000045(n-1) if n>=2. - Michael Somos, Nov 22 2019

EXAMPLE

The a(1) = 1 through a(7) = 8 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))))))

G.f. = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 5*x^6 + 8*x^7 + 13*x^8 + ... - Michael Somos, Nov 22 2019

MATHEMATICA

durtid[n_]:=Join@@Table[Select[Union[Sort/@Tuples[durtid/@ptn]], UnsameQ@@#&&UnsameQ@@Cases[#, {__}, {0, Infinity}]&], {ptn, IntegerPartitions[n-1]}];

Table[Length[durtid[n]], {n, 15}]

PROG

(PARI) {a(n) = if( n<=1, n==1, fibonacci(n-1))}; /* Michael Somos, Nov 22 2019 */

CROSSREFS

The Matula-Goebel numbers of these trees are given by A324968.

Cf. A000045, A000081, A004111, A276625, A290689, A317713, A324923, A324936, A324971, A324978.

Sequence in context: A236191 A333378 A000045 * A020695 A212804 A132916

Adjacent sequences:  A324966 A324967 A324968 * A324970 A324971 A324972

KEYWORD

nonn

AUTHOR

Gus Wiseman, Mar 21 2019

EXTENSIONS

More terms from Jinyuan Wang, Jun 27 2020

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 24 20:13 EDT 2020. Contains 337321 sequences. (Running on oeis4.)