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

Author

Gus Wiseman, Mar 21 2019

Keywords

• nonn
• easy

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)

Examples

			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
		

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

Crossrefs

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

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

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

Programs

Magma

[1] cat [Fibonacci(n-1): n in [2..50]]; // G. C. Greubel, Oct 24 2023

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

PARI

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

SageMath

[int(n==1) +fibonacci(n-1) for n in range(1,51)] # G. C. Greubel, Oct 24 2023

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

Extensions

More terms from Jinyuan Wang, Jun 27 2020