A216648 -id:A216648 - cp's OEIS frontend

A061775 Number of nodes in rooted tree with Matula-Goebel number n.

1, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 5, 5, 6, 5, 6, 6, 6, 6, 6, 7, 6, 7, 6, 6, 7, 6, 6, 7, 6, 7, 7, 6, 6, 7, 7, 6, 7, 6, 7, 8, 7, 7, 7, 7, 8, 7, 7, 6, 8, 8, 7, 7, 7, 6, 8, 7, 7, 8, 7, 8, 8, 6, 7, 8, 8, 7, 8, 7, 7, 9, 7, 8, 8, 7, 8, 9, 7, 7, 8, 8, 7, 8, 8, 7, 9, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 7, 8, 8, 8, 9, 7, 7, 9

Offset: 1

N. J. A. Sloane, Jun 22 2001

nonn

Let p(1)=2, ... denote the primes. The label f(T) for a rooted tree T is 1 if T has 1 node, otherwise f(T) = Product p(f(T_i)) where the T_i are the subtrees obtained by deleting the root and the edges adjacent to it. (Cf. A061773 for illustration).

Each n occurs A000081(n) times.

			a(4) = 3 because the rooted tree corresponding to the Matula-Goebel number 4 is "V", which has one root-node and two leaf-nodes, three in total.
See also the illustrations in A061773.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Keith Briggs, Matula numbers and rooted trees
Emeric Deutsch, Tree statistics from Matula numbers, arXiv preprint arXiv:1111.4288 [math.CO], 2011.
F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Index entries for sequences related to Matula-Goebel numbers

One more than A196050.
Sum of entries in row n of irregular table A214573.
Number of entries in row n of irregular tables A182907, A206491, A206495 and A212620.
One less than the number of entries in row n of irregular tables A184187, A193401 and A193403.
Cf. A005517 (the position of the first occurrence of n).
Cf. A005518 (the position of the last occurrence of n).
Cf. A091233 (their difference plus one).
Cf. A214572 (Numbers k such that a(k) = 8).
Cf. also A000081, A061773, A049084, A020639, A049076, A078442, A091238, A091204, A091205, A109082, A127301, A109129, A193402, A193405, A193406, A196047, A196068, A198333, A206487, A206494, A206496, A214569, A214571, A213670, A214568, A228599, A245817, A245818.
Cf. also A075166, A075167, A216648, A216649.

import Data.List (genericIndex)
a061775 n = genericIndex a061775_list (n - 1)
a061775_list = 1 : g 2 where
   g x = y : g (x + 1) where
      y = if t > 0 then a061775 t + 1 else a061775 u + a061775 v - 1
          where t = a049084 x; u = a020639 x; v = x `div` u
-- Reinhard Zumkeller, Sep 03 2013

with(numtheory): a := proc (n) local u, v: u := n-> op(1, factorset(n)): v := n-> n/u(n): if n = 1 then 1 elif isprime(n) then 1+a(pi(n)) else a(u(n))+a(v(n))-1 end if end proc: seq(a(n), n = 1..108); # Emeric Deutsch, Sep 19 2011

a[n_] := Module[{u, v}, u = FactorInteger[#][[1, 1]]&; v = #/u[#]&; If[n == 1, 1, If[PrimeQ[n], 1+a[PrimePi[n]], a[u[n]]+a[v[n]]-1]]]; Table[a[n], {n, 108}] (* Jean-François Alcover, Jan 16 2014, after Emeric Deutsch *)

A061775(n) = if(1==n, 1, if(isprime(n), 1+A061775(primepi(n)), {my(pfs,t,i); pfs=factor(n); pfs[,1]=apply(t->A061775(t),pfs[,1]); (1-bigomega(n)) + sum(i=1, omega(n), pfs[i,1]*pfs[i,2])}));
for(n=1, 10000, write("b061775.txt", n, " ", A061775(n)));
\\ Antti Karttunen, Aug 16 2014

from functools import lru_cache
from sympy import isprime, factorint, primepi
@lru_cache(maxsize=None)
def A061775(n):
    if n == 1: return 1
    if isprime(n): return 1+A061775(primepi(n))
    return 1+sum(e*(A061775(p)-1) for p, e in factorint(n).items()) # Chai Wah Wu, Mar 19 2022

a(1) = 1; if n = p_t (= the t-th prime), then a(n) = 1+a(t); if n = uv (u,v>=2), then a(n) = a(u)+a(v)-1.
a(n) = A091238(A091204(n)). - Antti Karttunen, Jan 2004
a(n) = A196050(n)+1. - Antti Karttunen, Aug 16 2014

More terms from David W. Wilson, Jun 25 2001

Extended by Emeric Deutsch, Sep 19 2011

A216649 Triangle T(n,k) in which n-th row lists in increasing order all positive integers with a representation as totally balanced 2n digit binary string such that all consecutive totally balanced substrings are in nondecreasing order; n>=1, 1<=k<=A000081(n+1).

Original entry on oeis.org

2, 10, 12, 42, 44, 52, 56, 170, 172, 180, 184, 204, 212, 216, 232, 240, 682, 684, 692, 696, 716, 724, 728, 744, 752, 820, 824, 852, 856, 872, 880, 920, 936, 944, 976, 992, 2730, 2732, 2740, 2744, 2764, 2772, 2776, 2792, 2800, 2868, 2872, 2900, 2904, 2920, 2928

Offset: 1

Alois P. Heinz, Sep 12 2012

There is a simple bijection between the elements of row n and the rooted trees with n+1 nodes. The tree has a root node. Each matching pair (1,0) in the binary string representation encodes an additional node, the totally balanced substrings encode lists of subtrees.

			172 is element of row 4, the binary string representation (with totally balanced substrings enclosed in parentheses) is (10)(10)(1(10)0).  The encoded rooted tree is:
.    o
.   /|\
.  o o o
.      |
.      o
Triangle T(n,k) begins:
2;
10,     12;
42,     44,   52,   56;
170,   172,  180,  184,  204,  212,  216,  232,  240;
682,   684,  692,  696,  716,  724,  728,  744,  752,  820,  824, ...
2730, 2732, 2740, 2744, 2764, 2772, 2776, 2792, 2800, 2868, 2872, ...
Triangle T(n,k) in binary:
10;
1010,       1100;
101010,     101100,     110100,     111000;
10101010,   10101100,   10110100,   10111000,   11001100,   11010100, ...
1010101010, 1010101100, 1010110100, 1010111000, 1011001100, 1011010100, ...

Alois P. Heinz, Rows n = 1..11, flattened

First column gives: A020988.
Last elements of rows give: A020522.
Row lengths are: A000081(n+1).
Subsequence of A014486, A031443.
Cf. A061773, A216349, A216350, A216648.

F:= proc(n) option remember; `if`(n=1, [10], sort(map(h->
      parse(cat(1, sort(h)[], 0)), g(n-1, n-1)))) end:
g:= proc(n, i) option remember; `if`(i=1, [[10$n]], [seq(seq(seq(
      [seq (F(i)[w[t]-t+1], t=1..j),v[]], w=combinat[choose](
      [$1..nops(F(i))+j-1], j)), v=g(n-i*j, i-1)), j=0..n/i)])
    end:
b:= proc(n) local h, i, r; h, r:= n/10, 0; for i from 0
      while h>1 do r:= r+2^i*irem(h, 10, 'h') od; r
    end:
T:= proc(n) option remember; map(b, F(n+1))[] end:
seq(T(n), n=1..6);

T(n,k) = A216648(n+1,k)/2 - 2^(2*n).

A242353 Number T(n,k) of two-colored rooted trees of order n and structure k; triangle T(n,k), n>=1, 1<=k<=A000081(n), read by rows.

Original entry on oeis.org

2, 4, 8, 6, 16, 12, 16, 8, 32, 24, 32, 16, 32, 24, 20, 24, 10, 64, 48, 64, 32, 64, 48, 40, 48, 20, 64, 48, 64, 32, 64, 48, 48, 36, 40, 32, 12, 128, 96, 128, 64, 128, 96, 80, 96, 40, 128, 96, 128, 64, 128, 96, 96, 72, 80, 64, 24, 128, 96, 128, 64, 128, 96, 80

Offset: 1

Martin Paech, May 11 2014

The underlying partitions of n-1 (cf. A000041) for the construction of the trees with n nodes are generated in descending order, the elements within a partition are sorted in ascending order, e.g.,
n = 1
  {0} |-> () |-> 10_2
n = 2
  {1} |-> (()) |-> 1100_2
n = 3
  {2} > {1, 1} |-> ((())) > (()()) |-> 111000_2 > 110100_2
n = 4
  {3} > {1, 2} > {1, 1, 1} |-> (((()))) > ((()())) > (()(())) > (()()()) |-> 11110000_2 > 11101000_2 > 11011000_2 > 11010100_2
The decimal equivalents of the binary encoded rooted trees in row n are the descending ordered elements of row n in A216648.

			Let {u, d} be a set of two colors, corresponding each with the up-spin and down-spin electrons in the underlying physical problem. (We consider each rooted tree as a cutout of the Bethe lattice in infinite dimensions.) Then for
n = 1 with A000081(1) = 1
  u(), d() are the 2 two-colored trees of the first and only structure k = 1 (sum is 2 = A038055(1)); for
n = 2 with A000081(2) = 1
  u(u()), u(d()), d(u()), d(d()) are the 4 two-colored trees of the first and only structure k = 1 (sum is 4 = A038055(2)); for
n = 3 with A000081(3) = 2
  u(u(u())), u(u(d())), u(d(u())), u(d(d())), d(u(u())), d(u(d())), d(d(u())), d(d(d())) are the 8 two-colored trees of the structure k = 1 and
  u(u()u()), u(u()d()), u(d()d()), d(u()u()), d(u()d()), d(d()d()) are the 6 two-colored trees of the structure k = 2 (sum is 14 = A038055(3)).
Triangle T(n,k) begins:
2;
4;
8,   6;
16, 12, 16,  8;
32, 24, 32, 16, 32, 24, 20, 24, 10;

G. Gruber, Entwicklung einer graphbasierten Methode zur Analyse von Hüpfsequenzen auf Butcherbäumen und deren Implementierung in Haskell, Diploma thesis, Marburg, 2011
Eva Kalinowski, Mott-Hubbard-Isolator in hoher Dimension, Dissertation, Marburg: Fachbereich Physik der Philipps-Universität, 2002.

Martin Paech, Rows n = 1..14, flattened
E. Kalinowski and W. Gluza, Evaluation of High Order Terms for the Hubbard Model in the Strong-Coupling Limit, arXiv:1106.4938, 2011 (Physical Review B 85, 045105, Jan 2012)
E. Kalinowski and M. Paech, Table of two-colored Butcher trees B(n,k,m) up to order n = 5.
M. Paech, A sonification of this sequence, created with MUSICALGORITHMS, using simple 'division operation' instead of modulo scaling (3047 elements, 240 bpm).
M. Paech, E. Kalinowski, W. Apel, G. Gruber, R. Loogen, and E. Jeckelmann, Ground-state energy and beyond: High-accuracy results for the Hubbard model on the Bethe lattice in the strong-coupling limit, DPG Spring Meeting, Berlin, TT 45.91 (2012)

Row sums give A038055.
Row length is A000081.
Total number of elements up to and including row n is A087803.
Cf. A216648.

A242354 Number T(n,k) of four-colored rooted trees of order n and structure k; triangle T(n,k), n>=1, 1<=k<=A000081(n), read by rows.

Original entry on oeis.org

4, 16, 64, 40, 256, 160, 256, 80, 1024, 640, 1024, 320, 1024, 640, 544, 640, 140, 4096, 2560, 4096, 1280, 4096, 2560, 2176, 2560, 560, 4096, 2560, 4096, 1280, 4096, 2560, 2560, 1600, 2176, 1280, 224, 16384, 10240, 16384, 5120, 16384, 10240, 8704, 10240, 2240

Offset: 1

Martin Paech, May 16 2014

The underlying partitions of n-1 (cf. A000041) for the construction of the trees with n nodes are generated in descending order, the elements within a partition are sorted in ascending order, e.g.,
n = 1
  {0} |-> () |-> 10_2
n = 2
  {1} |-> (()) |-> 1100_2
n = 3
  {2} > {1, 1} |-> ((())) > (()()) |-> 111000_2 > 110100_2
n = 4
  {3} > {1, 2} > {1, 1, 1} |-> (((()))) > ((()())) > (()(())) > (()()()) |-> 11110000_2 > 11101000_2 > 11011000_2 > 11010100_2
The decimal equivalents of the binary encoded rooted trees in row n are the descending ordered elements of row n in A216648.

			Let {h, u, d, p} be a set of four colors, corresponding to the four possible "states" of each tree node (lattice site) in the underlying physical problem, namely its occupation with no electron (hole), with one up-spin electron, with one down-spin electron, or with one up-spin and one down-spin electron (pair). (We consider each rooted tree as a cutout of the Bethe lattice in infinite dimensions.) Then for
n = 1 with A000081(1) = 1
  h(), u(), d(), p() are the 4 four-colored trees of the first and only structure k = 1 (sum is 4 = A136793(1)); for
n = 2 with A000081(2) = 1
  h(h()), h(u()), h(d()), h(p()),
  u(h()), u(u()), u(d()), u(p()),
  d(h()), d(u()), d(d()), d(p()),
  p(h()), p(u()), p(d()), p(p()) are the 16 four-colored trees of the first and only structure k = 1 (sum is 16 = A136793(2)); for
n = 3 with A000081(3) = 2
  h(h(h())), h(h(u())), h(h(d())), h(h(p())),
  h(u(h())), ...
                              ..., p(d(p())),
  p(p(h())), p(p(u())), p(p(d())), p(p(p())) are the 64 four-colored trees of the structure k = 1 and
  h(h()h()), h(h()u()), h(h()d()), h(h()p()),
  h(u()u()), h(u()d()), h(u()p()),
  h(d()d()), h(d()p()),
  h(p()p()),
  ...,
  p(h()h()), p(h()u()), p(h()d()), p(h()p()),
  p(u()u()), p(u()d()), p(u()p()),
  p(d()d()), p(d()p()),
  p(p()p()) are the 40 four-colored trees of the structure k = 2 (sum is 104 = A136793(3)).
Triangle T(n,k) begins:
4;
16;
64, 40;
256, 160, 256, 80;
1024, 640, 1024, 320, 1024, 640, 544, 640, 140;

G. Gruber, Entwicklung einer graphbasierten Methode zur Analyse von Hüpfsequenzen auf Butcherbäumen und deren Implementierung in Haskell, Diploma thesis, Marburg, 2011
Eva Kalinowski, Mott-Hubbard-Isolator in hoher Dimension, Dissertation, Marburg: Fachbereich Physik der Philipps-Universität, 2002.

Martin Paech, Rows n = 1..10, flattened
E. Kalinowski and W. Gluza, Evaluation of High Order Terms for the Hubbard Model in the Strong-Coupling Limit, arXiv:1106.4938, 2011 (Physical Review B 85, 045105, Jan 2012)
E. Kalinowski and M. Paech, Table of four-colored Butcher trees B(n,k,m) up to order n = 4.
M. Paech, E. Kalinowski, W. Apel, G. Gruber, R. Loogen, and E. Jeckelmann, Ground-state energy and beyond: High-accuracy results for the Hubbard model on the Bethe lattice in the strong-coupling limit, DPG Spring Meeting, Berlin, TT 45.91 (2012)

Row sums give A136793.
Row length is A000081.
Total number of elements up to and including row n is A087803.
Cf. A216648, A242353.

cp's OEIS Frontend

A061775 Number of nodes in rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A216649 Triangle T(n,k) in which n-th row lists in increasing order all positive integers with a representation as totally balanced 2n digit binary string such that all consecutive totally balanced substrings are in nondecreasing order; n>=1, 1<=k<=A000081(n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A242353 Number T(n,k) of two-colored rooted trees of order n and structure k; triangle T(n,k), n>=1, 1<=k<=A000081(n), read by rows.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A242354 Number T(n,k) of four-colored rooted trees of order n and structure k; triangle T(n,k), n>=1, 1<=k<=A000081(n), read by rows.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs