A277130 -id:A277130 - cp's OEIS frontend

A277120 Number of branching factorizations of n.

0, 1, 1, 2, 1, 3, 1, 5, 2, 3, 1, 11, 1, 3, 3, 15, 1, 11, 1, 11, 3, 3, 1, 45, 2, 3, 5, 11, 1, 19, 1, 51, 3, 3, 3, 62, 1, 3, 3, 45, 1, 19, 1, 11, 11, 3, 1, 195, 2, 11, 3, 11, 1, 45, 3, 45, 3, 3, 1, 113, 1, 3, 11, 188, 3, 19, 1, 11, 3, 19, 1, 345, 1, 3, 11, 11, 3

Offset: 1

Michel Marcus, Oct 01 2016

nonn

Per the formula, a(n) = 1 at prime n. As the sequence extends, additional values become more frequent than 1. These values can be characterized, for example, a(n) = 19 is seen at n corresponding to A007304, a(n) = 3 is seen at n corresponding to A006881, a(n) = 113 is seen at n corresponding to A085987. - Bill McEachen, Dec 28 2023
From Antti Karttunen, Jan 02 2024: (Start)
The value of a(n) depends only on the prime signature of n. In other words, for all i, j >= 1, it holds that A101296(i) = A101296(j) => a(i) = a(j). Moreover, it seems that the converse proposition also holds, that for all i, j >= 1, a(i) = a(j) => A101296(i) = A101296(j), i.e., for each distinct prime signature there exists a distinct value of a(n). This has been empirically checked up to the first 21001 prime signatures in A025487 (see A366884), and can be proved if one can show that the latter sequence (equally: A366377) is injective. If this conjecture holds, it would imply an unlimited number of statements like those given in the previous comment (see the formula section of A101296).
Questions: Are there any terms of the form 10k+4 or 10k+6? What is the asymptotic density of terms of the form 10k+5 (those ending with digit "5")? Compare to the data shown in A366884.
For squarefree n > 1, a(n) is never even, and apparently, never a multiple of five. See comments in A052886.
(End)

			In this scheme, the following factorizations of 12 are counted as distinct: 12, 2 x 6, 2 x (2 x 3), 2 x (3 x 2), 3 x 4, 3 x (2 x 2), 4 x 3, (2 x 2) x 3, 6 x 2, (2 x 3) x 2, (3 x 2) x 2, thus a(12) = 11. - _Antti Karttunen_, Nov 02 2016, based on the illustration given at page 14 of Knopfmacher & Mays paper.
The following factorizations of 30 are counted as distinct: 30, 2 x 15, 15 x 2, 3 x 10, 10 x 3, 5 x 6, 6 x 5, 2 x (3 x 5), 2 x (5 x 3), 3 x (2 x 5), 3 x (5 x 2), 5 x (2 x 3), 5 x (3 x 2), (2 x 3) x 5, (2 x 5) x 3, (3 x 2) x 5, (3 x 5) x 2, (5 x 2) x 3, (5 x 3) x 2, thus a(30) = 19. - _Antti Karttunen_, Jan 02 2024

Daniel Mondot, Table of n, a(n) for n = 1..9999
H.-K. Hwang, Théorèmes limites pour les structures combinatoires et les fonctions arithmétiques, PhD thesis, in Ecole Polytechnique, 1994. See page 198.
A. Knopfmacher, M. E. Mays, A survey of factorization counting functions, International Journal of Number Theory, 1(4):563-581,(2005). See page 14.
Index entries for sequences computed from exponents in factorization of n

Cf. A007317, A052886, A074206, A101296, A277130, A366377 [= a(A108951(n))], A366884 [= a(A025487(n))].

After n=1 differs from A104725 for the next time at n=32, where a(32) = 51, while A104725(32) = 52.

#include 
#define MAX 10000
/* Number of branching factorizations of n. */
unsigned long n, m, a, b, p, x, nbr[MAX];
int main(void)
{
  for (x=n=1; nDaniel Mondot, Oct 01 2016 */

v[n_] := v[n] = If[n == 1, 0, 1 + Sum[If[d == 1 || d^2 > n, 0, If[d^2 == n, 1, 2]*v[d]*v[n/d]], {d, Divisors[n]}]]; Table[v[n], {n, 1, 100}] (* Vaclav Kotesovec, Jan 13 2024, after Antti Karttunen *)

A277120(n) = if(1==n, 0, 1+sumdiv(n, d, if((1==d)||(d*d)>n,0,if((d*d)==n,1,2)*A277120(d)*A277120(n/d)))); \\ Antti Karttunen, Nov 02 2016, after Daniel Mondot's C-program above.

seq(n)={my(v=vector(n)); for(n=2, n, v[n] = 1 + sumdiv(n, d, v[d]*v[n/d])); v} \\ Andrew Howroyd, Nov 17 2018

a(1) = 0; for n > 1, a(n) = 1 + Sum_{d|n, 1 < d < n} a(d)*a(n/d). - Antti Karttunen, Nov 02 2016, after Daniel Mondot's C program, simplified Dec 30 2023.

For all n >= 1, a(prime^n) = A007317(n), and a(product of n distinct primes) = A052886(n). - Antti Karttunen, Dec 31 2023

More terms from Daniel Mondot, Oct 01 2016

A319122 Number of phylogenetic plane trees on n labels.

Original entry on oeis.org

1, 3, 25, 387, 8521, 241683, 8383705, 343826787, 16273985641, 873119718963, 52360707915385, 3470858539699587, 252000934472119561, 19888355652445884243, 1695252683833578455065, 155208762048402360698787, 15190477481877333732410281, 1582657042668691276257233523

Offset: 1

Gus Wiseman, Sep 11 2018

nonn

A phylogenetic plane tree on n labels is either the set of labels itself or a finite sequence of at least two phylogenetic plane trees, one on each block of an ordered set partition of the labels.

			The a(2) = 3 phylogenetic plane trees are {1,2}, ({1},{2}), ({2},{1}).

Cf. A000108, A000670, A001003, A005804, A074206, A118376, A277130, A281118, A281119, A319137.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
t[n_]:=t[n]=1+Sum[Times@@t/@f,{f,Join@@Permutations/@Select[sps[Range[n]],Length[#]>1&]}];
Array[t,8]

A319123 Number of series-reduced plane trees with n leaves such that each branch directly under any given node has a different number of leaves.

Original entry on oeis.org

1, 1, 3, 7, 21, 75, 277, 1083, 4419, 18493, 77729, 332557, 1444477, 6307225, 27912147, 123878207, 554733045, 2492087531, 11280537097, 51120499279, 233319480419, 1065835004917, 4895443823281, 22505853359485, 103958158302085, 480365303903637, 2229412587062123

Offset: 1

Gus Wiseman, Sep 11 2018

nonn

			The a(4) = 7 plane trees:
  (oooo)
  (o(ooo))
  ((ooo)o)
  (o(o(oo)))
  (o((oo)o))
  ((o(oo))o)
  (((oo)o)o)

Cf. A000108, A001003, A007853, A074206, A118376, A273873, A277130, A281113, A304173, A304175, A319122.

b[n_]:=b[n]=1+Sum[Times@@b/@f,{f,Join@@Permutations/@Select[IntegerPartitions[n],And[Length[#]>1,UnsameQ@@#]&]}];
Array[b,30]

A319137 Number of strict planar branching factorizations of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 3, 1, 3, 1, 9, 1, 3, 3, 7, 1, 9, 1, 9, 3, 3, 1, 37, 1, 3, 3, 9, 1, 25, 1, 21, 3, 3, 3, 57, 1, 3, 3, 37, 1, 25, 1, 9, 9, 3, 1, 161, 1, 9, 3, 9, 1, 37, 3, 37, 3, 3, 1, 153, 1, 3, 9, 75, 3, 25, 1, 9, 3, 25, 1, 345, 1, 3, 9, 9, 3, 25, 1, 161

Offset: 1

Gus Wiseman, Sep 11 2018

nonn

			The a(12) = 9 trees:
  12,
  (2*6), (3*4), (4*3),(6*2),
  (2*(2*3)), (2*(3*2)), ((2*3)*2), ((3*2)*2).

Cf. A000108, A001055, A045778, A074206, A118376, A277130, A281113, A281118, A292504, A295279, A295281, A317144, A319122, A319123, A319138.

ordfacs[n_]:=If[n<=1,{{}},Join@@Table[(Prepend[#1,d]&)/@ordfacs[n/d],{d,Rest[Divisors[n]]}]]
sotfs[n_]:=Prepend[Join@@Table[Tuples[sotfs/@f],{f,Select[ordfacs[n],And[Length[#]>1,UnsameQ@@#]&]}],n];
Table[Length[sotfs[n]],{n,100}]

a(prime^n) = A319123(n + 1).

a(product of n distinct primes) = A319122(n).

A319138 Number of complete strict planar branching factorizations of n.

Original entry on oeis.org

0, 1, 1, 0, 1, 2, 1, 0, 0, 2, 1, 4, 1, 2, 2, 0, 1, 4, 1, 4, 2, 2, 1, 8, 0, 2, 0, 4, 1, 18, 1, 0, 2, 2, 2, 28, 1, 2, 2, 8, 1, 18, 1, 4, 4, 2, 1, 16, 0, 4, 2, 4, 1, 8, 2, 8, 2, 2, 1, 84, 1, 2, 4, 0, 2, 18, 1, 4, 2, 18, 1, 112, 1, 2, 4, 4, 2, 18, 1, 16, 0, 2, 1

Offset: 1

Gus Wiseman, Sep 11 2018

nonn

A strict planar branching factorization of n is either the number n itself or a sequence of at least two strict planar branching factorizations, one of each factor in a strict ordered factorization of n. A strict planar branching factorization is complete if the leaves are all prime numbers.

			The a(12) = 4 trees: (2*(2*3)), (2*(3*2)), ((2*3)*2), ((3*2)*2).

Cf. A000108, A045778, A074206, A118376, A277130, A281113, A281118, A295279, A295281, A317144, A319122, A319123, A319136, A319137.

ordfacs[n_]:=If[n<=1,{{}},Join@@Table[(Prepend[#1,d]&)/@ordfacs[n/d],{d,Rest[Divisors[n]]}]]
sotfs[n_]:=Prepend[Join@@Table[Tuples[sotfs/@f],{f,Select[ordfacs[n],And[Length[#]>1,UnsameQ@@#]&]}],n];
Table[Length[Select[sotfs[n],FreeQ[#,_Integer?(!PrimeQ[#]&)]&]],{n,100}]

a(prime^n) = A000007(n - 1).

a(product of n distinct primes) = A032037(n).

A319136 Number of complete planar branching factorizations of n.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 3, 1, 2, 1, 9, 1, 2, 2, 11, 1, 9, 1, 9, 2, 2, 1, 44, 1, 2, 3, 9, 1, 18, 1, 45, 2, 2, 2, 66, 1, 2, 2, 44, 1, 18, 1, 9, 9, 2, 1, 225, 1, 9, 2, 9, 1, 44, 2, 44, 2, 2, 1, 132, 1, 2, 9, 197, 2, 18, 1, 9, 2, 18, 1, 450, 1, 2, 9, 9, 2, 18, 1, 225

Offset: 1

Gus Wiseman, Sep 11 2018

nonn

A planar branching factorization of n is either the number n itself or a sequence of at least two planar branching factorizations, one of each factor in an ordered factorization of n. A planar branching factorization is complete if the leaves are all prime numbers.

			The a(12) = 9 trees:
  (2*2*3), (2*3*2), (3*2*2),
  (2*(2*3)), (2*(3*2)), (3*(2*2)), ((2*2)*3), ((2*3)*2), ((3*2)*2).

Cf. A000108, A001055, A007716, A074206, A118376, A277130, A281118, A281119, A292505, A317144, A319122, A319138.

ordfacs[n_]:=If[n<=1,{{}},Join@@Table[(Prepend[#1,d]&)/@ordfacs[n/d],{d,Rest[Divisors[n]]}]]
otfs[n_]:=Prepend[Join@@Table[Tuples[otfs/@f],{f,Select[ordfacs[n],Length[#]>1&]}],n];
Table[Length[Select[otfs[n],FreeQ[#,_Integer?(!PrimeQ[#]&)]&]],{n,100}]

a(prime^n) = A001003(n - 1).

a(product of n distinct primes) = A032037(n).

cp's OEIS Frontend

A277120 Number of branching factorizations of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Mathematica

PARI

PARI

Formula

Extensions

A319122 Number of phylogenetic plane trees on n labels.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A319123 Number of series-reduced plane trees with n leaves such that each branch directly under any given node has a different number of leaves.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A319137 Number of strict planar branching factorizations of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A319138 Number of complete strict planar branching factorizations of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A319136 Number of complete planar branching factorizations of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula