A292505 -id:A292505 - cp's OEIS frontend

A316784 Number of orderless identity tree-factorizations of n.

1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 2, 3, 1, 4, 1, 4, 2, 2, 1, 10, 1, 2, 2, 4, 1, 8, 1, 6, 2, 2, 2, 13, 1, 2, 2, 10, 1, 8, 1, 4, 4, 2, 1, 26, 1, 4, 2, 4, 1, 10, 2, 10, 2, 2, 1, 28, 1, 2, 4, 13, 2, 8, 1, 4, 2, 8, 1, 46, 1, 2, 4, 4, 2, 8, 1, 26, 3, 2, 1

Offset: 1

Gus Wiseman, Jul 13 2018

nonn

A factorization of n is a finite nonempty multiset of positive integers greater than 1 with product n. An orderless identity tree-factorization of n is either (case 1) the number n itself or (case 2) a finite set of two or more distinct orderless identity tree-factorizations, one of each factor in a factorization of n.

a(n) depends only on the prime signature of n. - Andrew Howroyd, Nov 18 2018

			The a(24)=10 orderless identity tree-factorizations:
  24
  (4*6)
  (3*8)
  (2*12)
  (2*3*4)
  (4*(2*3))
  (3*(2*4))
  (2*(2*6))
  (2*(3*4))
  (2*(2*(2*3)))

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

Cf. A001055, A001678, A004111, A292504, A292505, A295279, A300660, A316782.

postfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[postfacs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
oltsfacs[n_]:=If[n<=1,{{}},Prepend[Select[Union@@Function[q,Sort/@Tuples[oltsfacs/@q]]/@DeleteCases[postfacs[n],{n}],UnsameQ@@#&],n]];
Table[Length[oltsfacs[n]],{n,100}]

seq(n)={my(v=vector(n), w=vector(n)); w[1]=v[1]=1; for(k=2, n, w[k]=v[k]+1; forstep(j=n\k*k, k, -k, my(i=j, e=0); while(i%k==0, i/=k; e++; v[j] += binomial(w[k], e)*v[i]))); w} \\ Andrew Howroyd, Nov 18 2018

a(p^n) = A300660(n) for prime p. - Andrew Howroyd, Nov 18 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).

A320266 Number of balanced orderless tree-factorizations of n.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 6, 1, 4, 1, 4, 2, 2, 1, 8, 2, 2, 3, 4, 1, 5, 1, 9, 2, 2, 2, 11, 1, 2, 2, 8, 1, 5, 1, 4, 4, 2, 1, 17, 2, 4, 2, 4, 1, 8, 2, 8, 2, 2, 1, 13, 1, 2, 4, 19, 2, 5, 1, 4, 2, 5, 1, 24, 1, 2, 4, 4, 2, 5, 1, 17, 6, 2, 1, 13, 2

Offset: 1

Gus Wiseman, Oct 08 2018

nonn

A rooted tree is balanced if all leaves are the same distance from the root.
An orderless tree-factorization of n is either (case 1) the number n itself or (case 2) a finite multiset of two or more orderless tree-factorizations, one of each factor in a factorization of n.
a(n) depends only on the prime signature of n. - Andrew Howroyd, Nov 18 2018

			The a(36) = 11 balanced orderless tree-factorizations:
  36,
  (2*18), (3*12), (4*9), (6*6),
  (2*2*9), (2*3*6), (3*3*4),
  (2*2*3*3), ((2*2)*(3*3)), ((2*3)*(2*3)).

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

Cf. A000669, A001055, A048816, A050336, A281118, A292505, A119262, A120803, A141268, A292504, A319312, A320160, A320267.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
oltfacs[n_]:=If[n<=1,{{}},Prepend[Union@@Function[q,Sort/@Tuples[oltfacs/@q]]/@DeleteCases[facs[n],{n}],n]];
Table[Length[Select[oltfacs[n],SameQ@@Length/@Position[#,_Integer]&]],{n,100}]

MultEulerT(u)={my(v=vector(#u)); v[1]=1; for(k=2, #u, forstep(j=#v\k*k, k, -k, my(i=j, e=0); while(i%k==0, i/=k; e++; v[j]+=binomial(e+u[k]-1, e)*v[i]))); v}
seq(n)={my(u=vector(n, i, 1), v=vector(n)); while(u, v+=u; u[1]=1; u=MultEulerT(u)-u); v} \\ Andrew Howroyd, Nov 18 2018

a(p^n) = A320160(n) for prime p. - Andrew Howroyd, Nov 18 2018

A320267 Number of balanced complete orderless tree-factorizations of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 3, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 3, 1, 1, 1

Offset: 1

Gus Wiseman, Oct 08 2018

nonn

a(1) = 1 by convention.
A rooted tree is balanced if all leaves are the same distance from the root.
An orderless tree-factorization (see A292504 for definition) is complete if all leaves are prime numbers.
a(n) depends only on the prime signature of n. - Andrew Howroyd, Nov 18 2018

			The a(96) = 5 balanced complete orderless tree-factorizations:
     (2*2*2*2*2*3)
   ((2*2)*(2*2*2*3))
   ((2*3)*(2*2*2*2))
   ((2*2*2)*(2*2*3))
  ((2*2)*(2*2)*(2*3))

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

Cf. A001055, A048816, A050336, A281118, A292505, A119262, A120803, A292504, A320160, A320266.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
oltfacs[n_]:=If[n<=1,{{}},Prepend[Union@@Function[q,Sort/@Tuples[oltfacs/@q]]/@DeleteCases[facs[n],{n}],n]];
Table[Length[Select[oltfacs[n],And[SameQ@@Length/@Position[#,_Integer],FreeQ[#,_Integer?(!PrimeQ[#]&)]]&]],{n,100}]

MultEulerT(u)={my(v=vector(#u)); v[1]=1; for(k=2, #u, forstep(j=#v\k*k, k, -k, my(i=j, e=0); while(i%k==0, i/=k; e++; v[j]+=binomial(e+u[k]-1, e)*v[i]))); v}
seq(n)={my(u=vector(n, i, i==1 || isprime(i)), v=vector(n)); while(u, v+=u; u[1]=1; u=MultEulerT(u)-u); v} \\ Andrew Howroyd, Nov 18 2018

a(p^n) = A120803(n) for prime p. - Andrew Howroyd, Nov 18 2018

A316977 Number of series-reduced rooted trees whose leaves are {1, 1, 2, 2, 3, 3, ..., n, n}.

Original entry on oeis.org

1, 12, 575, 66080, 13830706, 4566898564, 2181901435364, 1422774451251512, 1213875872220833664, 1312273759143855989808, 1752860078230602866012288, 2834766624822130489716563008, 5458358420687156358967526721408, 12339106957086349462329140342122112

Offset: 1

Gus Wiseman, Jul 17 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches.

			The a(2) = 12 trees are (1(1(22))), (1(2(12))), (1(122)), (2(1(12))), (2(2(11))), (2(112)), ((11)(22)), ((12)(12)), (11(22)), (12(12)), (22(11)), (1122).

Cf. A000081, A000669, A007717, A020555, A050535, A094574, A292504, A316655, A316972, A316974.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
gro[m_]:=If[Length[m]==1,m,Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])]];
Table[Length[gro[Ceiling[Range[1/2,n,1/2]]]],{n,4}]

\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(2*n), vars=vector(2*n-2,i,sv(2+i))); v[1]=sv(1); for(n=2, #v, v[n] = substvec(polcoef( sExp(x*Ser(v[1..n])), n ), vars[1..n-2], vector(n-2))); sCartProd(x*Ser(v), 1/(1-x^2*symGroupCycleIndex(2)) + O(x*x^(2*n)))}
seq(n)={my(p=substvec(cycleIndexSeries(n), [sv(1), sv(2)], [1,1])); vector(n, n, polcoef(p,2*n))} \\ Andrew Howroyd, Jan 02 2021

a(n) = A292505(A061742(n)). - Andrew Howroyd, Nov 19 2018

Terms a(6) and beyond from Andrew Howroyd, Jan 02 2021

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

A316784 Number of orderless identity tree-factorizations of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A319136 Number of complete planar branching factorizations of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A320266 Number of balanced orderless tree-factorizations of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A320267 Number of balanced complete orderless tree-factorizations of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A316977 Number of series-reduced rooted trees whose leaves are {1, 1, 2, 2, 3, 3, ..., n, n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

SageMath