A281119 -id:A281119 - cp's OEIS frontend

A318577 Number of complete multimin tree-factorizations of n.

0, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 4, 1, 1, 1, 11, 1, 3, 1, 4, 1, 1, 1, 19, 1, 1, 3, 4, 1, 4, 1, 45, 1, 1, 1, 17, 1, 1, 1, 19, 1, 4, 1, 4, 4, 1, 1, 96, 1, 3, 1, 4, 1, 11, 1, 19, 1, 1, 1, 26, 1, 1, 4, 197, 1, 4, 1, 4, 1, 4, 1, 104, 1, 1, 3, 4, 1, 4, 1, 96, 11, 1, 1, 26, 1, 1, 1, 19, 1, 19, 1, 4, 1, 1, 1, 501, 1, 3, 4, 17

Offset: 1

Gus Wiseman, Sep 11 2018

nonn

A multimin factorization of n is an ordered factorization of n into factors greater than 1 such that the sequence of minimal primes dividing each factor is weakly increasing. A multimin tree-factorization of n is either the number n itself or a sequence of at least two multimin tree-factorizations, one of each factor in a multimin factorization of n. A multimin tree-factorization is complete if the leaves are all prime numbers.

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

Cf. A000311, A001003, A001055, A020639, A255397, A281113, A281118, A281119, A295281, A317545, A319118, A319121.

facs[n_]:=If[n<=1,{{}},Join@@Table[(Prepend[#1,d]&)/@Select[facs[n/d],Min@@#1>=d&],{d,Rest[Divisors[n]]}]];
mmftrees[n_]:=Prepend[Join@@(Tuples[mmftrees/@#]&/@Select[Join@@Permutations/@Select[facs[n],Length[#]>1&],OrderedQ[FactorInteger[#][[1,1]]&/@#]&]),n];
Table[Length[Select[mmftrees[n],FreeQ[#,_Integer?(!PrimeQ[#]&)]&]],{n,100}]

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

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

A319119 Number of multimin tree-factorizations of Heinz numbers of integer partitions of n.

Original entry on oeis.org

1, 3, 9, 37, 173, 921, 5185, 30497, 184469, 1140413, 7170085, 45704821

Offset: 1

Gus Wiseman, Sep 10 2018

A multimin factorization of n is an ordered factorization of n into factors greater than 1 such that the sequence of minimal primes dividing each factor is weakly increasing. A multimin tree-factorization of n is either the number n itself or a sequence of multimin tree-factorizations, one of each factor in a multimin factorization of n with at least two factors.

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

			The a(3) = 9 multimin tree-factorizations:
  5, 6, 8,
  (2*3), (2*4), (4*2), (2*2*2),
  (2*(2*2)), ((2*2)*2).
Or as series-reduced plane trees of multisets:
  3, 12, 111,
  (1,2), (1,11), (11,1), (1,1,1),
  (1,(1,1)), ((1,1),1).

Cf. A001055, A020639, A196545, A255397, A281113, A281118, A281119, A295279, A317545, A317546, A319118.

facs[n_]:=If[n<=1,{{}},Join@@Table[(Prepend[#1,d]&)/@Select[facs[n/d],Min@@#1>=d&],{d,Rest[Divisors[n]]}]];
mmftrees[n_]:=Prepend[Join@@(Tuples[mmftrees/@#]&/@Select[Join@@Permutations/@Select[facs[n],Length[#]>1&],OrderedQ[FactorInteger[#][[1,1]]&/@#]&]),n];
Table[Sum[Length[mmftrees[k]],{k,Times@@Prime/@#&/@IntegerPartitions[n]}],{n,7}]

a(11)-a(12) from Robert Price, Sep 14 2018

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).

A319121 Number of complete multimin tree-factorizations of Heinz numbers of integer partitions of n.

Original entry on oeis.org

1, 2, 5, 18, 74, 344, 1679, 8548, 44690, 238691, 1295990, 7132509

Offset: 1

Gus Wiseman, Sep 11 2018

A multimin factorization of n is an ordered factorization of n into factors greater than 1 such that the sequence of minimal primes dividing each factor is weakly increasing. A multimin tree-factorization of n is either the number n itself or a sequence of at least two multimin tree-factorizations, one of each factor in a multimin factorization of n. A multimin tree-factorization is complete if the leaves are all prime numbers.

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

			The a(3) = 5 trees are: 5, (2*3), (2*2*2), (2*(2*2)), ((2*2)*2).
The a(4) = 18 trees (normalized with prime(n) -> n):
  4,
  (13), (22), (112), (1111),
  (1(12)), ((12)1), ((11)2),
  (11(11)), (1(11)1), ((11)11), (1(111)), ((111)1), ((11)(11)),
  (1(1(11))), (1((11)1)), ((1(11))1), (((11)1)1).

Cf. A000311, A001003, A001055, A020639, A255397, A281113, A281118, A281119, A295281, A317545, A317546, A318577, A319118, A319119.

facs[n_]:=If[n<=1,{{}},Join@@Table[(Prepend[#1,d]&)/@Select[facs[n/d],Min@@#1>=d&],{d,Rest[Divisors[n]]}]];
mmftrees[n_]:=Prepend[Join@@(Tuples[mmftrees/@#]&/@Select[Join@@Permutations/@Select[facs[n],Length[#]>1&],OrderedQ[FactorInteger[#][[1,1]]&/@#]&]),n];
Table[Sum[Length[Select[mmftrees[k],FreeQ[#,_Integer?(!PrimeQ[#]&)]&]],{k,Times@@Prime/@#&/@IntegerPartitions[n]}],{n,10}]

a(11)-a(12) from Robert Price, Sep 14 2018

A375120 Number of complete binary unordered tree-factorizations of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 4, 1, 1, 1, 2, 1, 3, 1, 3, 1, 1, 1, 6, 1, 1, 1, 4, 1, 3, 1, 2, 2, 1, 1, 9, 1, 2, 1, 2, 1, 4, 1, 4, 1, 1, 1, 9, 1, 1, 2, 6, 1, 3, 1, 2, 1, 3, 1, 15, 1, 1, 2, 2, 1, 3, 1, 9, 2, 1, 1, 9, 1, 1, 1

Offset: 1

Baron Kurt Hannsz, Jul 30 2024

nonn

For prime n, the factorization tree is a single vertex in just one way so that a(n) = 1.
For composite n, the two subtrees at n are a split of n into two factors n = d * (n/d), without order, so that a(n) = Sum_{d|n, 2 <= d <= n/d} a(d)*a(n/d).
a(1) = 1 is by convention, reckoning 1 as having a single empty factorization.
Greg Martin observed: if p is prime then a(p^k) equals the k-th 'half-Catalan number' A000992. - Peter Luschny, Nov 04 2024

			For n = 4, the a(4) = 1 sole factor tree is
     4     4 = 2*2
    / \
   2   2
For n=12, the a(12) = 2 factor trees are
    12          12
   /  \        /  \
  2    6      3    4
      / \         / \
     2   3       2   2
The tree structures are the same but the values are not the same and are therefore distinct factorizations.

Cf. A281119, A292505, A007964 (a(n)=1), A058080 (a(n)>1), A000992.

@cached_function
def a(n):
    if is_prime(n) or n == 1: return 1
    T = [t for t in divisors(n) if 1 < t <= n/t]
    return sum(a(d)*a(n//d) for d in T)
print([a(n) for n in range(1, 88)])  # Peter Luschny, Nov 03 2024

cp's OEIS Frontend

A318577 Number of complete multimin tree-factorizations of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A319119 Number of multimin tree-factorizations of Heinz numbers of integer partitions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A319136 Number of complete planar branching factorizations of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A319121 Number of complete multimin tree-factorizations of Heinz numbers of integer partitions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A375120 Number of complete binary unordered tree-factorizations of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

SageMath