A214577 -id:A214577 - cp's OEIS frontend

A317884 Number of series-reduced achiral free pure multifunctions (with empty expressions allowed) with one atom and n positions.

1, 1, 1, 2, 4, 8, 14, 26, 47, 87, 160, 295, 540, 997, 1832, 3369, 6197, 11406, 20975, 38594, 70991, 130610, 240275, 442043, 813184, 1496053, 2752251, 5063319, 9314879, 17136632, 31526032, 57998423, 106699160, 196294065, 361120800, 664352454, 1222204958

Offset: 1

Gus Wiseman, Aug 09 2018

nonn

A series-reduced achiral expression (SRAE) is either (case 1) the leaf symbol "o", or (case 2) a possibly empty but not unitary expression of the form h[g, ..., g], where h and g are SRAEs. The number of positions in an SRAE is the number of brackets [...] plus the number of o's.

Also the number of series-reduced achiral Mathematica expressions with one atom and n positions.

			The a(6) = 8 SRAEs:
  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[][][][][]

Andrew Howroyd, Table of n, a(n) for n = 1..500

Cf. A002033, A003238, A052893, A053492, A214577, A277996, A280000, A317853, A317875.

Cf. A317882, A317883, A317885.

a:= proc(n) option remember; `if`(n=1, 1, a(n-1)+add(a(j)*add(
      a(d), d=numtheory[divisors](n-j-1) minus {n-j-1}), j=1..n-1))
    end:
seq(a(n), n=1..45);  # Alois P. Heinz, Sep 05 2018

allAchExprSR[n_] := If[n == 1, {"o"}, Join @@ Cases[Table[PR[k, n - k - 1], {k, n - 1}], PR[h_, g_] :> Join @@ Table[Apply @@@ Tuples[{allAchExprSR[h], Select[Tuples[allAchExprSR /@ p], SameQ @@ # &]}], {p, If[g == 0, {{}}, Join @@ Permutations /@ Rest[IntegerPartitions[g]]]}]]]; Table[Length[allAchExprSR[n]], {n, 12}]
(* Second program: *)
a[n_] := a[n] = If[n == 1, 1, a[n-1] + Sum[a[j]*DivisorSum[
     n-j-1, If[# < n-j-1, a[#], 0]&], {j, 1, n-2}]];
Array[a, 45] (* Jean-François Alcover, May 17 2021, after Alois P. Heinz *)

seq(n)={my(p=O(x)); for(n=1, n, p = x + p*x*(1 + sum(k=2, n-2, subst(p + O(x^(n\k+1)), x, x^k)) ) + O(x*x^n)); Vec(p)} \\ Andrew Howroyd, Aug 19 2018

seq(n)={my(v=vector(n)); v[1]=1; for(n=2, #v, v[n]=v[n-1] + sum(i=1, n-2, v[i]*sumdiv(n-i-1, d, if(dAndrew Howroyd, Aug 19 2018

a(1) = 1; a(n > 1) = a(n-1) + Sum_{0 < k < n-1} a(k) * Sum_{d|(n-k-1), d < n-k-1} a(d).

Terms a(13) and beyond from Andrew Howroyd, Aug 19 2018

A317885 Number of series-reduced free pure achiral multifunctions with one atom and n positions.

Original entry on oeis.org

1, 0, 0, 1, 1, 1, 2, 3, 4, 7, 9, 14, 21, 32, 45, 69, 103, 153, 224, 338, 500, 746, 1107, 1645, 2447, 3652, 5413, 8052, 11993, 17834, 26500, 39447, 58655, 87240, 129772, 193001, 287034, 427014, 635048, 944501, 1404910, 2089633, 3107864, 4622670, 6875533

Offset: 1

Gus Wiseman, Aug 09 2018

nonn

A series-reduced free pure achiral multifunction (SRAM) is either (case 1) the leaf symbol "o", or (case 2) a nonempty and non-unitary expression of the form h[g, ..., g] where h and g are SRAMs. The number of positions in a SRAM is the number of brackets [...] plus the number of o's.

			The a(10) = 7 SRAMs:
  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[o,o,o,o,o][o,o]
  o[o,o,o,o,o,o,o,o]

Andrew Howroyd, Table of n, a(n) for n = 1..500

Cf. A001003, A001678, A002033, A003238, A052893, A053492, A067824, A167865, A214577, A317853, A317875.

Cf. A317882, A317883, A317884.

a[n_]:=If[n==1,1,Sum[a[k]*Sum[a[d],{d,Most[Divisors[n-k-1]]}],{k,n-2}]];
Array[a,12]

seq(n)={my(p=O(x)); for(n=1, n, p = x + p*x*sum(k=2, n-2, subst(p + O(x^(n\k+1)), x, x^k)) + O(x*x^n)); Vec(p)} \\ Andrew Howroyd, Aug 19 2018

seq(n)={my(v=vector(n)); v[1]=1; for(n=2, #v, v[n]=sum(i=1, n-2, v[i]*sumdiv(n-i-1, d, if(dAndrew Howroyd, Aug 19 2018

a(1) = 1; a(n > 1) = Sum_{0 < k < n - 1} a(k) * Sum_{d|(n - k - 1), d < n - k - 1} a(d).

Terms a(17) and beyond from Andrew Howroyd, Aug 19 2018

A318228 Number of inequivalent leaf-colorings of planted achiral trees with n nodes.

Original entry on oeis.org

1, 1, 3, 6, 13, 20, 43, 58, 115, 171, 323, 379, 1034, 1135, 2321, 4327, 8915, 9212, 33939, 34429, 128414, 234017, 417721, 418976, 2931624, 5096391, 11770830, 20357876, 64853630, 64858195

Offset: 1

Gus Wiseman, Aug 21 2018

In a planted achiral tree, all branches directly under any given branch are identical.

			Inequivalent representatives of the a(5) = 13 leaf-colorings:
  (1111)  ((111))  ((1)(1))  (((11)))  ((((1))))
  (1112)  ((112))  ((1)(2))  (((12)))
  (1122)  ((123))
  (1123)
  (1234)

Cf. A000081, A001190, A001678, A003238, A004111, A214577, A290689, A304486.

Cf. A318226, A318227, A318229, A318230, A318231, A318234, A339645.

\\ See links in A339645 for combinatorial species functions.
G(v)={my(t=2, p=sv(1)); for(i=1, #v, my(d=v[i]); if(d>1, p=sApplyCI(symGroupCycleIndex(d), d, p, t)); t=t*d+1); p}
cycleIndex(n)={my(recurse(r,v)=if(r==1, G(v), sumdiv(r-1, d, self()((r-1)/d, concat(d,v))))); recurse(n,[])}
a(n)={StructsByCycleIndex(n, cycleIndex(n), n)} \\ Andrew Howroyd, Dec 13 2020

a(9)-a(30) from Andrew Howroyd, Dec 11 2020

A318612 Matula-Goebel numbers of powerful rooted trees.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 16, 17, 19, 23, 25, 27, 31, 32, 36, 49, 53, 59, 64, 67, 72, 81, 83, 97, 100, 103, 108, 121, 125, 127, 128, 131, 144, 151, 196, 200, 216, 225, 227, 241, 243, 256, 277, 288, 289, 311, 324, 331, 343, 359, 361, 392, 400, 419, 431, 432

Offset: 1

Gus Wiseman, Aug 30 2018

nonn

A prime index of n is a number m such that prime(m) divides n. A positive integer n is a Matula-Goebel number of a powerful rooted tree iff either n = 1 or n is a prime number whose prime index is a Matula-Goebel number of a powerful rooted tree or n is a powerful number (meaning its prime multiplicities are all greater than 1) whose prime indices are all Matula-Goebel numbers of powerful rooted trees.

			The sequence of all powerful rooted trees together with their Matula-Goebel numbers begins:
   1: o
   2: (o)
   3: ((o))
   4: (oo)
   5: (((o)))
   7: ((oo))
   8: (ooo)
   9: ((o)(o))
  11: ((((o))))
  16: (oooo)
  17: (((oo)))
  19: ((ooo))
  23: (((o)(o)))
  25: (((o))((o)))
  27: ((o)(o)(o))
  31: (((((o)))))

Complement of A317719.

Cf. A000081, A001694, A061775, A111299, A214577, A276625, A303431, A317102, A317705, A317707.

powgoQ[n_]:=Or[n==1,If[PrimeQ[n],powgoQ[PrimePi[n]],And[Min@@FactorInteger[n][[All,2]]>1,And@@powgoQ/@PrimePi/@FactorInteger[n][[All,1]]]]];
Select[Range[1000],powgoQ]

A330218 Least BII-number of a set-system with n distinct representatives obtainable by permuting the vertices.

Original entry on oeis.org

0, 5, 12, 180, 35636, 13

Offset: 1

Gus Wiseman, Dec 09 2019

nonn

A set-system is a finite set of finite nonempty sets of positive integers.

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.

			The sequence of set-systems together with their BII-numbers begins:
      0: {}
      5: {{1},{1,2}}
     12: {{1,2},{3}}
    180: {{1,2},{1,3},{2,3},{4}}
  35636: {{1,2},{1,3},{2,3},{1,4},{2,4},{3,4},{5}}
     13: {{1},{1,2},{3}}

Positions of first appearances in A330231.
The MM-number version is A330230.
Achiral set-systems are counted by A083323.
BII-numbers of fully chiral set-systems are A330226.
Cf. A000120, A003238, A007716, A016031, A048793, A055621, A070939, A214577, A326031, A326702, A330098, A330101, A330195, A330217, A330229, A330233.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
graprms[m_]:=Union[Table[Sort[Sort/@(m/.Apply[Rule,Table[{p[[i]],i},{i,Length[p]}],{1}])],{p,Permutations[Union@@m]}]];
dv=Table[Length[graprms[bpe/@bpe[n]]],{n,0,1000}];
Table[Position[dv,i][[1,1]]-1,{i,First[Split[Union[dv],#1+1==#2&]]}]

A331967 Matula-Goebel numbers of lone-child-avoiding achiral rooted trees.

Original entry on oeis.org

1, 4, 8, 16, 32, 49, 64, 128, 256, 343, 361, 512, 1024, 2048, 2401, 2809, 4096, 6859, 8192, 16384, 16807, 17161, 32768, 51529, 65536, 96721, 117649, 130321, 131072, 148877, 262144, 516961, 524288, 823543, 1048576, 2097152, 2248091, 2476099, 2621161, 4194304

Offset: 1

Gus Wiseman, Feb 06 2020

nonn

Lone-child-avoiding means there are no unary branchings.
In an achiral rooted tree, the branches of any given vertex are all equal.
The Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of the branches of its root, which gives a bijective correspondence between positive integers and unlabeled rooted trees.
Consists of one and all numbers of the form prime(j)^k where k > 1 and j is already in the sequence.

			The sequence of all lone-child-avoiding achiral rooted trees together with their Matula-Goebel numbers begins:
      1: o
      4: (oo)
      8: (ooo)
     16: (oooo)
     32: (ooooo)
     49: ((oo)(oo))
     64: (oooooo)
    128: (ooooooo)
    256: (oooooooo)
    343: ((oo)(oo)(oo))
    361: ((ooo)(ooo))
    512: (ooooooooo)
   1024: (oooooooooo)
   2048: (ooooooooooo)
   2401: ((oo)(oo)(oo)(oo))
   2809: ((oooo)(oooo))
   4096: (oooooooooooo)
   6859: ((ooo)(ooo)(ooo))
   8192: (ooooooooooooo)
  16384: (oooooooooooooo)
  16807: ((oo)(oo)(oo)(oo)(oo))
  17161: ((ooooo)(ooooo))
  32768: (ooooooooooooooo)
  51529: (((oo)(oo))((oo)(oo)))
  65536: (oooooooooooooooo)
  96721: ((oooooo)(oooooo))

Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.
Gus Wiseman, The first 30 lone-child-avoiding achiral rooted trees.

A subset of A025475 (nonprime prime powers).
The enumeration of these trees by vertices is A167865.
Not requiring lone-child-avoidance gives A214577.
The semi-achiral version is A320269.
The semi-lone-child-avoiding version is A331992.
Achiral rooted trees are counted by A003238.
MG-numbers of planted achiral rooted trees are A280996.
MG-numbers of lone-child-avoiding rooted trees are A291636.
Cf. A001678, A007097, A061775, A196050, A276625, A291441, A320230, A320268, A331912, A331936, A331963, A331965, A331966, A331991.

msQ[n_]:=n==1||!PrimeQ[n]&&PrimePowerQ[n]&&And@@msQ/@PrimePi/@First/@FactorInteger[n];
Select[Range[10000],msQ]

Intersection of A214577 (achiral) and A291636 (lone-child-avoiding).

A358506 Matula-Goebel number of the n-th standard ordered rooted tree.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 6, 8, 7, 10, 9, 12, 10, 12, 12, 16, 11, 14, 15, 20, 15, 18, 18, 24, 14, 20, 18, 24, 20, 24, 24, 32, 13, 22, 21, 28, 25, 30, 30, 40, 21, 30, 27, 36, 30, 36, 36, 48, 22, 28, 30, 40, 30, 36, 36, 48, 28, 40, 36, 48, 40, 48, 48, 64, 13, 26, 33, 44

Offset: 1

Gus Wiseman, Nov 20 2022

nonn

First differs from A333219 at a(65) = 13, A333219(65) = 17.
The Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of the branches of its root, which gives a bijective correspondence between positive integers and unlabeled rooted trees.
We define the n-th standard ordered rooted tree to be obtained by taking the (n-1)-th composition in standard order (graded reverse-lexicographic, A066099) as root and replacing each part with its own standard ordered rooted tree. This ranking is an ordered variation of Matula-Goebel numbers, giving a bijective correspondence between positive integers and unlabeled ordered rooted trees.

			The first eight standard ordered trees are: o, (o), ((o)), (oo), (((o))), ((o)o), (o(o)), (ooo), with Matula-Goebel numbers: 1, 2, 3, 4, 5, 6, 6, 8.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

For binary instead of standard encoding we have A127301.
There are exactly A206487(n) appearances of n.
For binary instead of Matula-Goebel encoding we have A358505.
Positions of first appearances are A358522, sorted A358521.
A000108 counts ordered rooted trees, unordered A000081.
A214577 and A358377 rank trees with no permutations.
Cf. A001263, A014486, A061775, A196050, A358371, A358372, A358378, A358379, A358507, A358508.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
mgnum[t_]:=If[t=={},1,Times@@Prime/@mgnum/@t];
Table[mgnum[srt[n]],{n,100}]

A280994 Triangle read by rows giving Matula-Goebel numbers of planted achiral trees with n nodes.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 16, 17, 19, 23, 31, 32, 53, 59, 67, 25, 27, 49, 64, 83, 127, 131, 241, 277, 331, 97, 103, 128, 227, 311, 431, 709, 739, 1523, 1787, 2221, 81, 121, 256, 289, 361, 509, 563, 719, 1433, 2063, 3001, 5381, 5623, 12763, 15299, 19577

Offset: 1

Gus Wiseman, Jan 12 2017

An achiral tree is either (case 1) a single node or (case 2) a finite constant sequence (t,t,..,t) of achiral trees. Only in case 2 is an achiral tree considered to be a generalized Bethe tree (according to A214577).

			Triangle begins:
1,
2,
3, 4,
5, 7, 8,
9, 11, 16, 17, 19,
23, 31, 32, 53, 59, 67,
25, 27, 49, 64, 83, 127, 131, 241, 277, 331.

E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], 2011.

Cf. A003238 (row lengths), A214577, A061773, A061775, A004111, A007097, A196545, A275870.

nn=7;MGNumber[[]]:=1;MGNumber[x:[__]]:=If[Length[x]===1,Prime[MGNumber[x[[1]]]],Times@@Prime/@MGNumber/@x];
cits[n_]:=If[n===1,{1},Join@@Table[ConstantArray[#,(n-1)/d]&/@cits[d],{d,Divisors[n-1]}]];
Table[Sort[MGNumber/@(cits[n]/.(1->{}))],{n,nn}]

A280996 Prime Matula-Goebel numbers of generalized Bethe trees.

Original entry on oeis.org

2, 3, 5, 7, 11, 17, 19, 23, 31, 53, 59, 67, 83, 97, 103, 127, 131, 227, 241, 277, 311, 331, 419, 431, 509, 563, 661, 691, 709, 719, 739, 1433, 1523, 1543, 1619, 1787, 1879, 2063, 2221, 2309, 2437, 2897, 3001, 3637, 3671, 3803, 4091, 4637, 4943, 5189, 5381

Offset: 1

Gus Wiseman, Jan 12 2017

nonn

Also prime numbers p whose index pi(p) is the Matula-Goebel number of a planted achiral tree.

An alternative definition: prime(n) is in the sequence iff n is a perfect power of a prime number already in the sequence.

			a(n) = prime(Product_{i in y} a(i)) where y is the n-th partition in the following sequence, which spans all constant partitions: 1,2,11,3,4,111,22,5,1111,6,7,8,33,222,9,11111,44,...

Cf. A003238, A214577, A280994, A276625, A277098, A007097.

nn=10000;
BTQ[n_]:=Or[n===1,MatchQ[PrimePi/@FactorInteger[n][[All,1]],{_?BTQ}]];
Prime/@Select[Range[PrimePi[nn]],BTQ]

a(1) = 2; a(n+1) = prime(A214577(n)).

A298305 Matula-Goebel numbers of rooted trees with strictly thinning limbs.

Original entry on oeis.org

1, 2, 4, 6, 8, 9, 12, 16, 18, 24, 27, 28, 32, 36, 42, 48, 52, 54, 56, 63, 64, 72, 78, 81, 84, 92, 96, 98, 104, 108, 112, 117, 126, 128, 138, 144, 147, 152, 156, 162, 168, 182, 184, 189, 192, 196, 207, 208, 216, 224, 228, 234, 243, 252, 256, 273, 276, 288, 294

Offset: 1

Gus Wiseman, Jan 16 2018

nonn

An unlabeled rooted tree has strictly thinning limbs if its outdegrees are strictly decreasing from root to leaves.

			Sequence of trees begins:
1  o
2  (o)
4  (oo)
6  (o(o))
8  (ooo)
9  ((o)(o))
12 (oo(o))
16 (oooo)
18 (o(o)(o))
24 (ooo(o))
27 ((o)(o)(o))
28 (oo(oo))
32 (ooooo)
36 (oo(o)(o))
42 (o(o)(oo))
48 (oooo(o))
52 (oo(o(o)))
54 (o(o)(o)(o))
56 (ooo(oo))
63 ((o)(o)(oo))
64 (oooooo)
72 (ooo(o)(o))
78 (o(o)(o(o)))
81 ((o)(o)(o)(o))
84 (oo(o)(oo))
92 (oo((o)(o)))
96 (ooooo(o))
98 (o(oo)(oo))

Cf. A000081, A007097, A061775, A111299, A124343, A124346, A214577, A276625, A290760, A291636, A298126, A298120, A298304.

MGtree[n_]:=If[n===1,{},MGtree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
strthinQ[t_]:=And@@Cases[t,b_List:>Length[b]>Max@@Length/@b,{0,Infinity}];
Select[Range[200],strthinQ[MGtree[#]]&]

cp's OEIS Frontend

A317884 Number of series-reduced achiral free pure multifunctions (with empty expressions allowed) with one atom and n positions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A317885 Number of series-reduced free pure achiral multifunctions with one atom and n positions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A318228 Number of inequivalent leaf-colorings of planted achiral trees with n nodes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions

A318612 Matula-Goebel numbers of powerful rooted trees.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A330218 Least BII-number of a set-system with n distinct representatives obtainable by permuting the vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A331967 Matula-Goebel numbers of lone-child-avoiding achiral rooted trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A358506 Matula-Goebel number of the n-th standard ordered rooted tree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A280994 Triangle read by rows giving Matula-Goebel numbers of planted achiral trees with n nodes.