A104725 -id:A104725 - cp's OEIS frontend

A160086 a(n) = A104725(n) - A074206(n).

0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 3, 0, 0, 0, 7, 0, 3, 0, 3, 0, 0, 0, 25, 0, 0, 1, 3, 0, 6, 0, 36, 0, 0, 0, 36, 0, 0, 0, 25, 0, 6, 0, 3, 3, 0, 0, 152, 0, 3, 0, 3, 0, 25, 0, 25, 0, 0, 0, 69, 0, 0, 3, 171, 0, 6, 0, 3, 0, 6, 0, 279, 0, 0, 3, 3, 0, 6, 0, 152, 7, 0, 0, 69, 0, 0, 0, 25, 0, 69, 0, 3, 0, 0, 0

Offset: 0

Augustine O. Munagi, May 01 2009

nonn

a(n) is also the excess of the number of labeled factorizations of n over the number of ordered factorizations (see the Munagi link for definition of labeled factorization)

			a(8)=1 because A074206(8)=4 and A104725(8)=5, so a(8)=5-4. The only labeled factorization of 8 which is not an ordered factorization is (2_1.2_3)(2_2). a(9)=0 because A074206(9)=2=A104725(9). The labeled factorizations of 9, namely (9_1) and (3_1)(3_2), are also ordered factorizations.

Antti Karttunen, Table of n, a(n) for n = 0..10000 (computed from the b-files of A074206 and A104725)
A. O. Munagi, Labeled factorization of integers, Electron. J. Combin. 16 (2009), no. 1, Research Paper 50, 17pp.

Cf. A074206, A104725.

a:=proc(n::integer) local u, r, i, j, k; if n<2 then return 0; end if; u:=map(x->x[2], ifactors(n)[2]); r:=add(u[i], i=1..nops(u)); add(add((-1)^i*binomial(k, i)*product(binomial(u[j]+k-i-1, u[j]), j=1..nops(u)), i=0..k-1)*(bell(k-1)-1), k=1..r); end proc: seq(a(n),n=0..99);

a(n) = Sum(ordfac(n,k)*(Bell(k-1)-1),k=1..Omega(n)), where ordfac(n,k)=number of ordered factorizations of n into k factors.

A160085 Number of ordered complementing systems of subsets of {0, 1, ..., n-1} (see A104725).

Original entry on oeis.org

0, 1, 1, 1, 3, 1, 5, 1, 13, 3, 5, 1, 33, 1, 5, 5, 75, 1, 33, 1, 33, 5, 5, 1, 261, 3, 5, 13, 33, 1, 61, 1, 541, 5, 5, 5, 375, 1, 5, 5, 261, 1, 61, 1, 33, 33, 5, 1, 2405, 3, 33, 5, 33, 1, 261, 5, 261, 5, 5, 1, 717, 1, 5, 33, 4683, 5, 61, 1, 33, 5, 61, 1, 4549, 1, 5, 33, 33, 5, 61, 1, 2405

Offset: 0

Augustine O. Munagi, May 01 2009

nonn

Also number of permuted labeled factorizations of n (see the Munagi link for definition and examples)

			a(6) = 5: there are 3 complementing systems of subsets of {0,1,2,3,4,5} namely {{0,1,2,3,4,5}}, {{0,1,2},{0,3}} and {{0,1},{0,2,4}} (see A104725). Permuting the components gives 2 additional systems: {{0,3},{0,1,2}} and {{0,2,4},{0,1}}. Thus since {{0,1,2},{0,3}} is a complementing system of subsets of {0,1,2,3,4,5} we have 0 = 0 + 0, 1 = 1 + 0, 2 = 2 + 0, 3 = 0 + 3, 4 = 1 + 3, 5 = 2 + 3.

A. O. Munagi, k-Complementing Subsets of Nonnegative Integers, International Journal of Mathematics and Mathematical Sciences, 2005:2 (2005), 215-224.
A. O. Munagi, Labeled factorization of integers, Electron. J. Combin. 16 (2009), no. 1, Research Paper 50, 17pp.

Cf. A104725.

a:=proc(n::integer) local u, r, i, j, k; if n<1 then return 0; elif n=1 then return 1; end if; u:=map(x->x[2], ifactors(n)[2]); r:=add(u[i], i=1..nops(u)); add(add(k!*add((-1)^i*binomial(t, i)*product(binomial(u[j]+t-i-1, u[j]), j=1..nops(u)), i=0..t-1)*stirling2(t-1,k-1), t=k..r),k=1..r); end proc: seq(a(n),n=0..99);

a(0) = 0, a(1) = 1, a(n) = Sum_{j=1..A001222(n)} (Sum_{k=1..j} k!Stirling2(j-1,k-1)), n > 1, where ordfac(n,k) = number of ordered factorizations of n into k factors.

A173492 Partial sums of A104725.

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 9, 10, 15, 17, 20, 21, 32, 33, 36, 39, 54, 55, 66, 67, 78, 81, 84, 85, 130, 132, 135, 140, 151, 152, 171, 172, 224, 227, 230, 233, 295, 296, 299, 302, 347, 348, 367, 368, 379, 390, 393, 394, 594, 596, 607, 610, 621, 622, 667, 670, 715, 718, 721

Offset: 0

Jonathan Vos Post, Feb 19 2010

nonn

Partial sums of number of complementing systems of subsets of {0, 1, ..., n-1}. The subsequence of squares in this partial sum begins: 1, 9, 36, 81, 1849. The subsequence of primes in this partial sum begins: 2, 3, 5, 17, 67, 151, 227, 233, 347, 367, 379, 607, 839, 1087, 1109, 1733.

			a(85) = 0 + 1 + 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 + 52 + 3 + 3 + 3 + 62 + 1 + 3 + 3 + 45 + 1 + 19 + 1 + 11 + 11 + 3 + 1 + 200 + 2 + 11 + 3 + 11 + 1 + 45 + 3 + 45 + 3 + 3 + 1 + 113 + 1 + 3 + 11 + 203 + 3 + 19 + 1 + 11 + 3 + 19 + 1 + 355 + 1 + 3 + 11 + 11 + 3 + 19 + 1 + 200 + 15 + 3 + 1 + 113 + 3.

Cf. A104725, A074206, A002033.

a(n) = SUM[i=0..n] A104725(i).

A277120 Number of branching factorizations of n.

Original entry on oeis.org

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

A131420 A tabular sequence of arrays counting ordered factorizations over least prime signatures. The unordered version is described by sequence A129306.

Original entry on oeis.org

1, 2, 3, 4, 8, 13, 8, 20, 44, 75, 26, 16, 48, 132, 308, 541, 76, 176, 32, 112, 368, 1076, 2612, 4683, 208, 604, 1460, 252, 818, 64, 256, 876, 3408, 10404, 25988, 47293, 544, 1888, 5740, 14300, 768, 2316, 3172, 7880, 128, 576, 2496, 10096, 36848, 116180

Offset: 1

Alford Arnold, Jul 10 2007

nonn

The display has 1 2 3 5 7 11 15 ... terms per column. (cf. A000041)
The arrays begin
1.....2.....4......8......16.....32.....64......128
......3.....8.....20......48....112....256......576
...........13.....44.....132....368....976.....2496
..................75.....308...1076...3408....10096
.........................541...2612..10404....36848
...............................4683..25988...116180
.....................................47293...296564
.............................................545835
..................26......76....208....544
.........................176....604...1888
...............................1460...5740
.....................................14300
................................252....768
......................................2316
................................818...3172
......................................7880
with column sums
1....5....25....173....1297....12225....124997 => A035341
Column i corresponds to partitions of i. The rows correspond successively to the partitions {i}, {i-1,1},{i-2,1,1},{i-3,1,1,1}, ..., {i-7,1,1,1,1,1,1,1}, {i-2,2}, {i-3,2,1}, {i-4,2,1,1}, {i-5,2,1,1,1}, {i-3,3}, {i-3,3,1}, {i-4,2,2}, {i-5,2,2,1}. - Roger Lipsett, Feb 26 2016

			36 = 2*2*3*3 and is in A025487. There are 26 ways to factor 36 so a(11) = 26.

Cf. A000041, A000670, A002033, A025487, A035098, A035341, A050324, A074206, A095705, A098348, A104725, A108464, A129306.

gozinta counts ordered factorizations of an integer, and if lst is a partition we have
gozinta[1] = 1;
gozinta[n_] := gozinta[n] = 1 + Sum[gozinta[n/i], {i, Rest@Most@Divisors@n}]
a[lst_] := gozinta[Times @@ (Array[Prime, Length@lst]^lst)] (* Roger Lipsett, Feb 26 2016 *)

Corrected entries in table in comments section - Roger Lipsett, Feb 26 2016

cp's OEIS Frontend

A160086 a(n) = A104725(n) - A074206(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A160085 Number of ordered complementing systems of subsets of {0, 1, ..., n-1} (see A104725).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A173492 Partial sums of A104725.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A277120 Number of branching factorizations of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Mathematica

PARI

PARI

Formula

Extensions

A131420 A tabular sequence of arrays counting ordered factorizations over least prime signatures. The unordered version is described by sequence A129306.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions