A127301 -id:A127301 - cp's OEIS frontend

A014486 List of totally balanced sequences of 2n binary digits written in base 10. Binary expansion of each term contains n 0's and n 1's and reading from left to right (the most significant to the least significant bit), the number of 0's never exceeds the number of 1's.

0, 2, 10, 12, 42, 44, 50, 52, 56, 170, 172, 178, 180, 184, 202, 204, 210, 212, 216, 226, 228, 232, 240, 682, 684, 690, 692, 696, 714, 716, 722, 724, 728, 738, 740, 744, 752, 810, 812, 818, 820, 824, 842, 844, 850, 852, 856, 866, 868, 872, 880, 906, 908, 914

Offset: 0

Wouter Meeussen

The binary Dyck-Language (A063171) in decimal representation.
These encode width 2n mountain ranges, rooted planar trees of n+1 vertices and n edges, planar planted trees with n nodes, rooted plane binary trees with n+1 leaves (2n edges, 2n+1 vertices, n internal nodes, the root included), Dyck words, binary bracketings, parenthesizations, non-crossing handshakes and partitions and many other combinatorial structures in Catalan family, enumerated by A000108.
Is Sum_{k=1..n} a(k) / n^(5/2) bounded? - Benoit Cloitre, Aug 18 2002
This list is the intersection of A061854 and A031443. - Jason Kimberley, Jan 18 2013
The sequence does start at n = 0, since in the binary interpretation of the Dyck language (e.g., as parenthesizations where "1" stands for "(" and "0" stands for ")") having a(0) = 0 will do since it would stand for the empty string where the "0"s and "1"s are balanced (hence the parentheses are balanced). - Daniel Forgues, Feb 17 2013
It appears that for n>=1 this sequence can be obtained by concatenating the terms of the irregular array whose n-th row length is A000108(n) and that is defined recursively by B(n,0) = A020988(n) and B(n,k) = B(n, k-1) + D(n, k-1) where D(x,y) = (2^(2*(A089309(B(x,y))-1))-1)*(2/3) + 2^A007814(B(x,y)). - Raúl Mario Torres Silva and Michel Marcus, May 01 2020
This encoding is related to the ranking by standard ordered tree numbers in that (1) the binary encoding of trees ordered by standard ranking is given by A358505, while (2) the standard ranking of trees ordered by binary encoding is given by A358523. - Gus Wiseman, Nov 21 2022

			a(19) = 226_10 = 11100010_2 = A063171(19) as bracket expression: ( ( ( ) ) )( ) and as a binary tree, proceeding from left to right in depth-first fashion, with 1's in binary expansion standing for internal (branching) nodes and 0's for leaves:
  0   0
   \ /
    1   0 0  (0)
     \ /   \ /
      1     1
       \   /
         1
Note that in this coding scheme the last leaf of the binary trees (here in parentheses) is implicit. This tree can be also converted to a particular S-expression in languages like Lisp, Scheme and Prolog, if we interpret its internal nodes (1's) as cons cells with each leftward leaning branch being the "car" and the rightward leaning branch the "cdr" part of the pair, with the terminal nodes (0's) being ()'s (NILs). Thus we have (cons (cons (cons () ()) ()) (cons () ())) = '( ( ( () . () ) . () ) . ( () . () ) ) = (((())) ()) i.e., the same bracket expression as above, but surrounded by extra parentheses. This mapping is performed by the Scheme function A014486->parenthesization given below.
From _Gus Wiseman_, Nov 21 2022: (Start)
The terms and corresponding ordered rooted trees begin:
    0: o
    2: (o)
   10: (oo)
   12: ((o))
   42: (ooo)
   44: (o(o))
   50: ((o)o)
   52: ((oo))
   56: (((o)))
  170: (oooo)
  172: (oo(o))
  178: (o(o)o)
  180: (o(oo))
  184: (o((o)))
(End)

Donald E. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, Section 7.2.1.6, pp. 443 (Algorithm P).

Paolo Xausa, Table of n, a(n) for n = 0..23713 (terms 0..2500 from Franklin T. Adams-Watters).
Jason Bell, Thomas Finn Lidbetter, and Jeffrey Shallit, Additive Number Theory via Approximation by Regular Languages, arXiv:1804.07996 [cs.FL], 2018.
N. G. De Bruijn and B. J. M. Morselt, A note on plane trees, J. Combinatorial Theory 2 (1967), 27-34.
Gennady Eremin, Dynamics of balanced parentheses, lexicographic series and Dyck polynomials, arXiv:1909.07675 [math.CO], 2019.
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20.
Antti Karttunen, Catalan ranking and unranking functions, OEIS Wiki.
Antti Karttunen, Illustration of 626 initial terms (up to size n=7) with various combinatorial interpretations of Catalan numbers encoded by this sequence.
Antti Karttunen, a089408.c - C program for computing this sequence and many of the related automorphisms.
Antti Karttunen, Some notes on Catalan's Triangle.
Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625 [math.CO], 2020-2021.
D. L. Kreher and D. R. Stinson, Combinatorial Algorithms, Generation, Enumeration and Search, CRC Press, 1998.
Thomas Finn Lidbetter, Counting, Adding, and Regular Languages, Master's Thesis, University of Waterloo, Ontario, Canada, 2018.
R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016.
OEIS Wiki, Combinatorial interpretations of Catalan numbers
Frank Ruskey, Algorithmic Solution of Two Combinatorial Problems.
R. P. Stanley, Hipparchus, Plutarch, Schroeder and Hough, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.
R. P. Stanley, Exercises on Catalan and Related Numbers.
Paolo Xausa, A Mathematica implementation of Knuth's algorithms P and U.
Index entries for encodings of plane rooted trees (various subsets of this sequence).
Index entries for sequences related to parenthesizing
Index entries for signature-permutations induced by Catalan automorphisms (permutations of natural numbers induced by various bijective operations acting on these structures)
Index entries for the sequences induced by list functions of Lisp (sequences induced by various other operations on these codes or the corresponding structures).

Characteristic function: A080116. Inverse function: A080300.
The terms of binary width 2n are counted by A000108(n). Subset of A036990. Number of peaks in each mountain (number of leaves in rooted plane general trees): A057514. Number of trailing zeros in the binary expansion: A080237. First differences: A085192.
Cf. also A009766, A014137, A071156, A079436, A085184, A213704.
Cf. A020988, A089309, A007814.
Branches of the ordered tree are counted by A057515.
Edges of the ordered tree are counted by A072643.
The Matula-Goebel number of the ordered tree is A127301.
The standard ranking of the ordered tree is A358523.
The depth of the ordered tree is A358550.
Nodes of the ordered tree are counted by A358551.
Cf. A000081, A001263, A358505, A358524.

# Maple procedure CatalanUnrank is adapted from the algorithm 3.24 of the CAGES book and the Scheme function CatalanUnrank from Ruskey's thesis. See the a089408.c program for the corresponding C procedures.
CatalanSequences := proc(upto_n) local n,a,r; a := []; for n from 0 to upto_n do for r from 0 to (binomial(2*n,n)/(n+1))-1 do a := [op(a),CatalanUnrank(n,r)]; od; od; return a; end;
CatalanUnrank := proc(n,rr) local r,x,y,lo,m,a; r := (binomial(2*n,n)/(n+1))-(rr+1); y := 0; lo := 0; a := 0; for x from 1 to 2*n do m := Mn(n,x,y+1); if(r <= lo+m-1) then y := y+1; a := 2*a + 1; else lo := lo+m; y := y-1; a := 2*a; fi; od; return a; end;
Mn := (n,x,y) -> binomial(2*n-x,n-((x+y)/2)) - binomial(2*n-x,n-1-((x+y)/2));
# Alternative:
bin := n -> ListTools:-Reverse(convert(n, base, 2)):
isA014486 := proc(n): local B, s, b; s := 0;
    if n > 0 then
      for b in bin(n) do
          s := s + ifelse(b = 1, 1, -1);
           if 0 > s then return false fi;
      od fi;
  s = 0 end:
select(isA014486, [seq(0..240)]);  # Peter Luschny, Mar 13 2024

cat[ n_ ] := (2 n)!/n!/(n+1)!; b2d[li_List] := Fold[2#1+#2&, 0, li]
d2b[n_Integer] := IntegerDigits[n, 2]
tree[n_] := Join[Table[1, {i, 1, n}], Table[0, {i, 1, n}]]
nexttree[t_] := Flatten[Reverse[t]/. {a___, 0, 0, 1, b___}:> Reverse[{Sort[{a, 0}]//Reverse, 1, 0, b}]]
wood[ n_ /; n<8 ] := NestList[ nexttree, tree[ n ], cat[ n ]-1 ]
Table[ Reverse[ b2d/@wood[ j ] ], {j, 0, 6} ]//Flatten
(* Alternative code *)
tbQ[n_]:=Module[{idn2=IntegerDigits[n,2]},Count[idn2,1]==Length[idn2]/2&&Min[Accumulate[idn2/.{0->-1}]]>=0]; Join[{0},Select[Range[900],tbQ]] (* Harvey P. Dale, Jul 04 2013 *)
balancedQ[0] = True; balancedQ[n_] := Module[{s = 0}, Do[s += If[b == 1, 1, -1]; If[s < 0, Return[False]], {b, IntegerDigits[n, 2]}]; Return[s == 0] ]; A014486 = FromDigits /@ IntegerDigits[Select[Range[0, 1000], balancedQ ]] (* Jean-François Alcover, Mar 05 2016 *)
A014486Q[0] = True; A014486Q[n_] := Catch[Fold[If[# < 0, Throw[False], If[#2 == 0, # - 1, # + 1]] &, 0, IntegerDigits[n, 2]] == 0]; Select[Range[0, 880], A014486Q] (* JungHwan Min, Dec 11 2016 *)
(* Uses Algorithm P from Knuth's TAOCP section 7.2.1.6 - see References and Links. *)
alist[n_] := Block[{a = Flatten[Table[{1, 0}, n]], m = 2*n - 1, j, k},
    FromDigits[#, 2]& /@ Reap[
    While[True,
        Sow[a]; a[[m]] = 0;
        If[a[[m - 1]] == 0,
            a[[--m]] = 1, j = m - 1; k = 2*n - 1;
            While[j > 1 && a[[j]] == 1, a[[j--]] = 0; a[[k]] = 1; k -= 2];
            If[j == 1, Break[]];
            a[[j]] = 1; m = 2*n - 1]
    ]][[2, 1]]];
Join[{{0}, {2}}, Array[alist, 4, 2]] (* Paolo Xausa, Mar 16 2024 *)

isA014486(n)=my(v=binary(n),t=0);for(i=1,#v,t+=if(v[i],1,-1);if(t<0,return(0))); t==0 \\ Charles R Greathouse IV, Jun 10 2011

a_rows(N) = my(a=Vec([[0]], N)); for(r=1, N-1, my(b=a[r], c=List()); foreach(b, t, my(v=if(t, valuation(t, 2), 0)); for(i=0, v, listput(~c, (t<<2)+(2<Ruud H.G. van Tol, May 16 2024

from itertools import count, islice
from sympy.utilities.iterables import multiset_permutations
def A014486_gen(): # generator of terms
    yield 0
    for l in count(1):
        for s in multiset_permutations('0'*l+'1'*(l-1)):
            c, m = 0, (l<<1)-1
            for i in range(m):
                if s[i] == '1':
                    c += 2
                if cA014486_list = list(islice(A014486_gen(),30)) # Chai Wah Wu, Nov 28 2023

def is_A014486(n) :
    B = bin(n)[2::] if n != 0 else 0
    s = 0
    for b in B :
        s += 1 if b=='1' else -1
        if 0 > s : return False
    return 0 == s
def A014486_list(n): return [k for k in (1..n) if is_A014486(k) ]
A014486_list(888) # Peter Luschny, Aug 10 2012

Additional comments from Antti Karttunen, Aug 11 2000 and May 25 2004

Added a(0)=0 (which had been removed in June 2011), Joerg Arndt, Feb 27 2013

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

Original entry on oeis.org

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

A072796 Self-inverse permutation of natural numbers induced by the Catalan bijection swapping the two leftmost subtrees in the general tree context of the parenthesizations encoded by A014486. See illustrations in the comments.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 5, 7, 8, 9, 10, 14, 16, 19, 11, 15, 12, 17, 18, 13, 20, 21, 22, 23, 24, 25, 26, 27, 37, 38, 42, 44, 47, 51, 53, 56, 60, 28, 29, 39, 43, 52, 30, 40, 31, 45, 46, 32, 48, 49, 50, 33, 41, 34, 54, 55, 35, 57, 58, 59, 36, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71

Offset: 0

Antti Karttunen, Jun 12 2002

nonn

This bijection effects the following transformation on the unlabeled rooted plane general trees (letters A, B, C, etc. refer to arbitrary subtrees located on those vertices):
    A        A      A     B       B     A       A  B  C       B  A  C
    |  -->   |       \   /   -->   \   /         \ | /   -->   \ | /
    |        |        \./           \./           \|/           \|/     etc.
I.e., it keeps "planted" (root degree = 1) trees intact, and swaps the two leftmost toplevel subtrees of the general trees that have a root degree > 1.
On the level of underlying binary trees that general trees map to (see, e.g., 1967 paper by N. G. De Bruijn and B. J. M. Morselt, or consider lists vs. dotted pairs in Lisp programming language), this bijection effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node).
    B   C           A   C
     \ /             \ /
  A   x    -->    B   x                 A   ()        A   ()
   \ /             \ /                   \ /    -->    \ /
    x               x                     x             x
(a . (b . c)) -> (b . (a . c))         (a . ()) ---> (a . ())
Note that the first clause corresponds to what is called "generator pi_0" in Thompson's group V. (See also A074679, A089851 and A154121 for other related generators.)
Look at the example section to see how this will produce the given sequence of integers.
Applying this permutation recursively down the right hand side branch of the binary trees (or equivalently, along the topmost level of the general trees) produces permutations A057509 and A057510 (that occur at the same index 2 in tables A122203 and A122204) that effect "shallow rotation" on general trees and parenthesizations. Applying it recursively down the both branches of binary trees (as in pre- or postorder traversal) produces A057511 and A057512 (that occur at the same index 2 in tables A122201 and A122201) that effect "deep rotation" on general trees and parenthesizations.
For this permutation, A127301(a(n)) = A127301(n) for all n, which in turn implies A129593(a(n)) = A129593(n) for all n, likewise for all such recursively generated bijections as A057509 - A057512. Compare also to A072797.

			To obtain the signature permutation, we apply these transformations to the binary trees as encoded and ordered by A014486 and for each n, a(n) will be the position of the tree to which the n-th tree is transformed to, as follows:
.
                   one tree of one internal
  empty tree         (non-leaf) node
      x                      \/
n=    0                      1
a(n)= 0                      1               (both are always fixed)
.
the next 7 trees, with 2-3 internal nodes, in range [A014137(1), A014137(2+1)-1] = [2,8] are:
.
                          \/     \/                 \/     \/
       \/     \/         \/       \/     \/ \/     \/       \/
      \/       \/       \/       \/       \_/       \/       \/
n=     2        3        4        5        6        7        8
.
and the new shapes after swapping the two subtrees in positions marked "A" and "B" in the diagram given in the comments are:
.
                          \/               \/       \/     \/
       \/     \/         \/     \/ \/       \/     \/       \/
      \/       \/       \/       \_/       \/       \/       \/
a(n)=  2        3        4        6        5        7        5
thus we obtain the first nine terms of this sequence: 0, 1, 2, 3, 4, 6, 5, 7, 8.

Antti Karttunen, Table of n, a(n) for n = 0..196
J. W. Cannon, W. J. Floyd, and W. R. Parry, Notes on Richard Thompson's Groups F and T
J. W. Cannon, W. J. Floyd, and W. R. Parry, Introductory notes on Richard Thompson's groups, L'Enseignement Mathématique, Vol. 42 (1996), pp. 215-256.
N. G. De Bruijn and B. J. M. Morselt, A note on plane trees, J. Combinatorial Theory 2 (1967), 27-34.
Antti Karttunen, Catalan Automorphisms

Row 2 of A089840. Row 3613 of A122203 and row 3617 of A122204.
Fixed point counts and cycle counts are given in A073190 and A073191.
Cf. A014486, A072797, A057509, A057510, A057511, A057512, A127301, A129593, A129608.

Comment section edited and Examples added by Antti Karttunen, Jan 26 2024

A072797 Self-inverse permutation of natural numbers induced by a Catalan bijection acting on binary trees as encoded by A014486. See comments and examples for details.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 7, 6, 8, 9, 10, 11, 12, 13, 17, 18, 16, 14, 15, 20, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 45, 46, 48, 49, 50, 44, 47, 42, 37, 38, 43, 39, 40, 41, 54, 55, 53, 51, 52, 57, 56, 58, 59, 61, 60, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71

Offset: 0

Antti Karttunen, Jun 12 2002

nonn

This bijection effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node).
   A   B           A   C
    \ /             \ /
     x   C    -->    x   B               ()  A        ()   A
      \ /             \ /                 \ /    -->    \ /
       x               x                   x             x
  ((a . b) . c) --> ((a . c) . b)      (() . a) ---> (() . a)
See the example for an explanation of how to obtain a given integer sequence from this definition.
Notably for this permutation, A127301(a(n)) = A127301(n) does not always hold, even though for all n, A129593(a(n)) = A129593(n). - Antti Karttunen, Jan 14 2024

			To obtain the signature permutation, we apply these transformations to the binary trees as encoded and ordered by A014486 and for each n, a(n) will be the position of the tree to which the n-th tree is transformed to, as follows:
.
                   one tree of one internal
  empty tree         (non-leaf) node
      x                      \/
n=    0                      1
a(n)= 0                      1               (both are always fixed)
.
the next 7 trees, with 2-3 internal nodes, in range [A014137(1), A014137(2+1)-1] = [2,8] are:
.
                          \/     \/                 \/     \/
       \/     \/         \/       \/     \/ \/     \/       \/
      \/       \/       \/       \/       \_/       \/       \/
n=     2        3        4        5        6        7        8
.
and the new shapes after swapping the two subtrees in positions marked "B" and "C" in the diagram given in the comments are:
.
                          \/     \/       \/               \/
       \/     \/         \/       \/     \/       \/ \/     \/
      \/       \/       \/       \/       \/       \_/       \/
a(n)=  2        3        4        5        7        6        8
thus we obtain the first nine terms of this sequence: 0, 1, 2, 3, 4, 5, 7, 6, 8.

Row 8 of A089840.
Cf. A014486, A057163, A072796, A127301, A129593.
Counts for the fixed points and for the number of distinct cycles (in each subrange limited by A014137) are given by A073190 and A073191.

a(n) = A057163(A072796(A057163(n))).

Further comments added by Antti Karttunen, Jun 04 2011 and Mar 30 2024

A206487 Number of ordered trees isomorphic (as rooted trees) to the rooted tree having Matula number n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 2, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 4, 1, 3, 2, 6, 1, 1, 2, 2, 2, 6, 3, 2, 4, 4, 2, 6, 2, 3, 3, 2, 2, 5, 1, 3, 2, 6, 1, 4, 2, 4, 2, 4, 1, 12, 3, 2, 3, 1, 4, 6, 1, 3, 2, 6, 3, 10, 2, 6, 3, 3, 2, 12, 2, 5, 1, 4, 1, 12, 2, 4, 4, 4, 4, 12, 4, 3, 2, 4, 2, 6, 1, 3, 3, 6, 4, 6, 1, 8, 6, 2, 3, 10, 2, 6, 6, 5, 6, 6, 2, 6, 6, 2, 2, 20, 1, 6, 4, 3, 1, 12, 1, 1, 4, 12, 1, 12, 2, 2, 4, 4, 2, 6, 2, 12, 4, 6, 4, 15, 4, 4, 3, 9, 2, 12, 6, 4, 3, 6, 2, 24, 3, 4, 2, 6

Offset: 1

Emeric Deutsch, Apr 14 2012

nonn

The Matula-Goebel number of a rooted tree is defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m>=2 there corresponds the product of the Matula-Goebel numbers of the m branches of T.

a(n) = the number of times n occurs in A127301. - Antti Karttunen, Jan 03 2013

			a(4)=1 because the rooted tree with Matula number 4 is V and there is no other ordered tree isomorphic to V. a(6)=2 because the rooted tree corresponding to n = 6 is obtained by joining the trees A - B and C - D - E at their roots A and C. Interchanging their order, we obtain another ordered tree, isomorphic (as rooted tree) to the first one.

E. Deutsch, Rooted tree statistics from Matula numbers, 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. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
P. Schultz, Enumeration of rooted trees with an application to group presentations, Discrete Math., 41, 1982, 199-214.
Index entries for sequences related to Matula-Goebel numbers

Cf. A127301.
Positions of 1's are 1 and A214577.
Positions of first appearances are A358507, unsorted A358508.
A000108 counts ordered rooted trees, unordered A000081.
A061775 and A196050 count nodes and edges in Matula-Goebel trees.
Cf. A001263, A003238, A014486, A358506.

with(numtheory): F := proc (n) options operator, arrow: factorset(n) end proc: PD := proc (n) local k, m, j: for k to nops(F(n)) do m[k] := 0: for j while is(n/F(n)[k]^j, integer) = true do m[k] := m[k]+1 end do end do: [seq([F(n)[q], m[q]], q = 1 .. nops(F(n)))] end proc: a := proc (n) if n = 1 then 1 elif bigomega(n) = 1 then a(pi(n)) else mul(a(PD(n)[j][1])^PD(n)[j][2], j = 1 .. nops(F(n)))*factorial(add(PD(n)[k][2], k = 1 .. nops(F(n))))/mul(factorial(PD(n)[k][2]), k = 1 .. nops(F(n))) end if end proc: seq(a(n), n = 1 .. 160);

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]
MGTree[n_Integer]:=If[n===1,{},MGTree/@primeMS[n]]
treeperms[t_]:=Times@@Cases[t,b:{}:>Length[Permutations[b]],{0,Infinity}];
Table[treeperms[MGTree[n]],{n,100}] (* Gus Wiseman, Nov 21 2022 *)

a(1)=1; denoting by p(t) the t-th prime, if n = p(n_1)^{k_1}...p(n_r)^{k_r}, then a(n) = a(n_1)^{k_1}...a(n_r)^{k_r}*(k_1 + ... + k_r)!/[(k_1)!...(k_r)!] (see Theorem 1 in the Schultz reference, where the exponents k_j of N(n_j) have been inadvertently omitted).

cp's OEIS Frontend

A153826 Index sequence to A089840: positions of bijections that preserve A127301 (the non-oriented form of general trees).

Views

Author

Keywords

Comments

Links

Crossrefs

A243492 Difference A243491(n) - A127301(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A243491 Matula-Goebel signature computed for trees rearranged by Catalan automorphism *A069787: a(n) = A127301(A069787(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A243496 Matula-Goebel signature computed for the oriented trees that stay same when "deep-rotated": a(n) = A127301(A243495(n)), listed in the same order as those tree are encoded in A014486.

Views

Author

Keywords

Comments

Crossrefs

Programs

Scheme

A243493 Value of Matula-Goebel signature at the fixed points of A069787: a(n) = A127301(A243490(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A014486 List of totally balanced sequences of 2n binary digits written in base 10. Binary expansion of each term contains n 0's and n 1's and reading from left to right (the most significant to the least significant bit), the number of 0's never exceeds the number of 1's.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

SageMath

Extensions

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

A072796 Self-inverse permutation of natural numbers induced by the Catalan bijection swapping the two leftmost subtrees in the general tree context of the parenthesizations encoded by A014486. See illustrations in the comments.

Views

Author