A324969 Number of unlabeled rooted identity trees with n vertices whose non-leaf terminal subtrees are all different.

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

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

G. C. Greubel, Table of n, a(n) for n = 1..1000

Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 21.

Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 11.

Index entries for linear recurrences with constant coefficients, signature (1,1).

Formula

From Michael Somos, Nov 22 2019: (Start)

G.f.: x*(1 - x^2) / (1 - x - x^2) = x*(1 + x/(1 - x/(1 - x/(1 + x)))).

a(n) = A000045(n-1) if n>=2. (End)

E.g.f.: -1 + x + exp(x/2)*(cosh(sqrt(5)*x/2) - (1/sqrt(5))*sinh(sqrt(5)*x/2)). - G. C. Greubel, Oct 24 2023

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

(* First program *)
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}]
(* Second program *)
Join[{1}, Fibonacci[Range[50]]] (* G. C. Greubel, Oct 24 2023 *)

Prog

(PARI) {a(n) = if( n<=1, n==1, fibonacci(n-1))}; /* Michael Somos, Nov 22 2019 */
(Magma) [1] cat [Fibonacci(n-1): n in [2..50]]; // G. C. Greubel, Oct 24 2023
(SageMath) [int(n==1) +fibonacci(n-1) for n in range(1, 51)] # G. C. Greubel, Oct 24 2023

Crossrefs

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

Cf. A000045, A000081, A004111, A276625, A290689.

Cf. A317713, A324923, A324936, A324971, A324978.

Sequence in context: A236191 A333378 A000045 * A020695 A212804 A132916

Adjacent sequences: A324966 A324967 A324968 * A324970 A324971 A324972

Keyword

nonn,easy

Author

Gus Wiseman, Mar 21 2019

Extensions

More terms from Jinyuan Wang, Jun 27 2020

Status

approved