

A324969


Number of unlabeled rooted identity trees with n vertices whose nonleaf 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 nonleaf 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 nonleaf 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(n1) 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[n1]}];
Table[Length[durtid[n]], {n, 15}]


PROG

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


CROSSREFS

The MatulaGoebel 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



