A324968 -id:A324968 - cp's OEIS frontend

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

Gus Wiseman, Mar 21 2019

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)

			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

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

The Matula-Goebel numbers of these trees are given by A324968.
Cf. A000045, A000081, A004111, A276625, A290689.
Cf. A317713, A324923, A324936, A324971, A324978.

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

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

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

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

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

More terms from Jinyuan Wang, Jun 27 2020

A325660 Number of ones in the q-signature of n.

Original entry on oeis.org

0, 1, 2, 0, 3, 1, 1, 0, 0, 2, 4, 1, 2, 1, 1, 0, 2, 0, 1, 2, 2, 3, 1, 1, 0, 2, 0, 1, 3, 1, 5, 0, 2, 2, 3, 0, 2, 1, 1, 2, 3, 2, 2, 3, 1, 1, 2, 1, 0, 0, 3, 2, 1, 0, 1, 1, 2, 3, 3, 1, 1, 4, 1, 0, 2, 2, 2, 2, 1, 3, 3, 0, 3, 2, 0, 1, 4, 1, 4, 2, 0, 3, 2, 2, 4, 2, 2

Offset: 1

Gus Wiseman, May 13 2019

nonn

Every positive integer has a unique q-factorization (encoded by A324924) into factors q(i) = prime(i)/i, i > 0. For example:
   11 = q(1) q(2) q(3) q(5)
   50 = q(1)^3 q(2)^2 q(3)^2
  360 = q(1)^6 q(2)^3 q(3)
Then a(n) is the number of factors of multiplicity one in the q-factorization of n.
Also the number of rooted trees appearing only once in the multiset of terminal subtrees of the rooted tree with Matula-Goebel number n.

Cf. A001694, A055231, A056169, A056239, A112798, A118914, A124010.
Matula-Goebel numbers: A007097, A061775, A109129, A196050, A317713, A324968.
q-factorization: A324922, A324923, A324924, A325614, A325661.

difac[n_]:=If[n==1,{},With[{i=PrimePi[FactorInteger[n][[1,1]]]},Sort[Prepend[difac[n*i/Prime[i]],i]]]];
Table[Count[Length/@Split[difac[n]],1],{n,100}]

A324970 Matula-Goebel numbers of rooted identity trees where not all terminal subtrees are different.

Original entry on oeis.org

15, 30, 33, 39, 47, 55, 65, 66, 78, 87, 93, 94, 110, 113, 123, 130, 137, 141, 143, 145, 155, 165, 167, 174, 186, 195, 205, 211, 226, 235, 237, 246, 257, 274, 282, 286, 290, 303, 310, 313, 317, 319, 327, 330, 334, 339, 341, 377, 381, 390, 395, 397, 403, 410

Offset: 1

Gus Wiseman, Mar 21 2019

nonn

A rooted identity tree is an unlabeled rooted tree with no repeated branches directly under the same root.

			The sequence of trees together with the Matula-Goebel numbers begins:
   15: ((o)((o)))
   30: (o(o)((o)))
   33: ((o)(((o))))
   39: ((o)(o(o)))
   47: (((o)((o))))
   55: (((o))(((o))))
   65: (((o))(o(o)))
   66: (o(o)(((o))))
   78: (o(o)(o(o)))
   87: ((o)(o((o))))
   93: ((o)((((o)))))
   94: (o((o)((o))))
  110: (o((o))(((o))))
  113: ((o(o)((o))))
  123: ((o)((o(o))))
  130: (o((o))(o(o)))
  137: (((o)(((o)))))
  141: ((o)((o)((o))))
  143: ((((o)))(o(o)))
  145: (((o))(o((o))))
  155: (((o))((((o)))))
  165: ((o)((o))(((o))))
  167: (((o)(o(o))))
  174: (o(o)(o((o))))
  186: (o(o)((((o)))))
  195: ((o)((o))(o(o)))

Gus Wiseman, The first 36 trees together with their Matula-Goebel numbers.

Cf. A000081, A004111, A007097, A196050, A276625, A317713, A324850, A324923, A324935, A324936, A324968, A324971, A324978.

mgtree[n_Integer]:=If[n==1,{},mgtree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],And[And@@Cases[mgtree[#],q:{}:>UnsameQ@@q,{0,Infinity}],!UnsameQ@@Cases[mgtree[#],{},{0,Infinity}]]&]

Complement of A324935 in A276625.

A324978 Matula-Goebel numbers of rooted trees that are not identity trees but whose non-leaf terminal subtrees are all different.

Original entry on oeis.org

4, 7, 8, 12, 14, 16, 17, 19, 20, 21, 24, 28, 32, 34, 35, 37, 38, 40, 42, 43, 44, 48, 51, 52, 53, 56, 57, 59, 64, 67, 68, 70, 71, 73, 74, 76, 77, 80, 84, 85, 86, 88, 89, 91, 95, 96, 102, 104, 106, 107, 112, 114, 116, 118, 124, 128, 129, 131, 133, 134, 136, 139

Offset: 1

Gus Wiseman, Mar 21 2019

nonn

An unlabeled rooted tree is an identity tree if there are no repeated branches directly under the same root.

			The sequence of trees together with the Matula-Goebel numbers begins:
   4: (oo)
   7: ((oo))
   8: (ooo)
  12: (oo(o))
  14: (o(oo))
  16: (oooo)
  17: (((oo)))
  19: ((ooo))
  20: (oo((o)))
  21: ((o)(oo))
  24: (ooo(o))
  28: (oo(oo))
  32: (ooooo)
  34: (o((oo)))
  35: (((o))(oo))
  37: ((oo(o)))
  38: (o(ooo))
  40: (ooo((o)))
  42: (o(o)(oo))
  43: ((o(oo)))

Gus Wiseman, The first 36 trees together with their Matula-Goebel numbers.

Cf. A000081, A004111, A007097, A196050, A276625, A317713, A324850, A324923, A324935, A324936, A324968, A324969, A324970, A324971, A324979.

mgtree[n_]:=If[n==1,{},mgtree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],And[!And@@Cases[mgtree[#],q:{}:>UnsameQ@@q,{0,Infinity}],UnsameQ@@Cases[mgtree[#],{},{0,Infinity}]]&]

Complement of A276625 in A324935.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A325660 Number of ones in the q-signature of n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A324970 Matula-Goebel numbers of rooted identity trees where not all terminal subtrees are different.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A324978 Matula-Goebel numbers of rooted trees that are not identity trees but whose non-leaf terminal subtrees are all different.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula