A324969 - OEIS

A324969

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

%I #33 Mar 09 2024 11:35:44

%S 1,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,

%T 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,

%U 1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155

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

%C 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.

%C Appears to be essentially the same as the Fibonacci sequence A000045. - _R. J. Mathar_, Mar 28 2019

%C From _Michael Somos_, Nov 22 2019: (Start)

%C 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.

%C 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)

%H G. C. Greubel, <a href="/A324969/b324969.txt">Table of n, a(n) for n = 1..1000</a>

%H Joshua P. Bowman, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL27/Bowman/bowman4.html">Compositions with an Odd Number of Parts, and Other Congruences</a>, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 21.

%H Jia Huang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Huang/huang8.html">Partially Palindromic Compositions</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 11.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,1).

%F From _Michael Somos_, Nov 22 2019: (Start)

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

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

%F 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

%e The a(1) = 1 through a(7) = 8 trees:

%e o (o) ((o)) (o(o)) ((o(o))) (o(o(o))) ((o(o(o))))

%e (((o))) (o((o))) (((o(o)))) (o((o(o))))

%e ((((o)))) ((o((o)))) (o(o((o))))

%e (o(((o)))) ((((o(o)))))

%e (((((o))))) (((o((o)))))

%e ((o(((o)))))

%e (o((((o)))))

%e ((((((o))))))

%e 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

%t (* First program *)

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

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

%t (* Second program *)

%t Join[{1}, Fibonacci[Range[50]]] (* _G. C. Greubel_, Oct 24 2023 *)

%o (PARI) {a(n) = if( n<=1, n==1, fibonacci(n-1))}; /* _Michael Somos_, Nov 22 2019 */

%o (Magma) [1] cat [Fibonacci(n-1): n in [2..50]]; // _G. C. Greubel_, Oct 24 2023

%o (SageMath) [int(n==1) +fibonacci(n-1) for n in range(1,51)] # _G. C. Greubel_, Oct 24 2023

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

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

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

%K nonn,easy

%O 1,4

%A _Gus Wiseman_, Mar 21 2019

%E More terms from _Jinyuan Wang_, Jun 27 2020