| Displaying 1-4 of 4 results found.
page
1
(Largest Matula-Goebel number encoding a tree with n nodes) - (smallest Matula-Goebel number encoding a tree with n nodes).
+10
6
1, 1, 2, 4, 11, 53, 307, 2177, 19503, 219489, 3041937, 50727755, 997525229, 22742733167, 592821131015, 17461204518199
REFERENCES
F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968).
Number of nodes in rooted tree with GF2X-Matula number n.
+10
6
1, 2, 3, 3, 5, 4, 4, 4, 6, 6, 4, 5, 6, 5, 7, 5, 9, 7, 5, 7, 7, 5, 8, 6, 5, 7, 8, 6, 6, 8, 5, 6, 7, 10, 9, 8, 7, 6, 8, 8, 7, 8, 7, 6, 10, 9, 5, 7, 7, 6, 11, 8, 7, 9, 6, 7, 10, 7, 7, 9, 6, 6, 9, 7, 11, 8, 8, 11, 7, 10, 8, 9, 6, 8, 12, 7, 9, 9, 8, 9, 11, 8, 9, 9, 13, 8, 10, 7, 8, 11, 8, 10, 8, 6, 9, 8
EXAMPLE
GF2X-Matula numbers for unoriented rooted trees are constructed otherwise just like the standard Matula-Goebel numbers (cf. A061773), but instead of normal factorization in N, one factorizes in polynomial ring GF(2)[X] as follows. Here IR(n) is the n-th irreducible polynomial ( A014580(n)) and X stands for GF(2)[X]-multiplication ( A048720): ................................................o...................o
................................................|...................|
............o...............o...o........o......o...............o...o
............|...............|...|........|......|...............|...|
...o........o......o...o....o...o....o...o......o......o.o.o....o...o
...|........|.......\./......\./......\./.......|.......\|/......\./.
x..x........x........x........x........x........x........x........x..
1..2 = IR(1)..3 = IR(2)..4 = 2 X 2....5 = 3 X 3....6 = 2 X 3....7 = IR(3)..8 = 2 X 2 X 2..9 = 3 X 7
Counting the vertices (marked with x's and o's) of each tree above, we get the eight initial terms of this sequence: 1,2,3,3,5,4,4,4,6.
Smallest GF2X-Matula number i which encodes a tree of n nodes, i.e., for which A091238(i) = n.
+10
3
1, 2, 3, 6, 5, 9, 15, 23, 17, 34, 51, 75, 85, 153, 255, 359, 257, 514, 771, 1275, 1285, 2313, 3855, 5911, 4369, 8738, 13107, 19275, 21845, 39321, 65535
Largest GF2X-Matula number i which encodes a tree of n nodes, i.e., for which A091238(i) = n.
+10
2
1, 2, 4, 11, 47, 319, 3053, 40345
Search completed in 0.056 seconds
|