A182269 Number of representations of n as a sum of products of pairs of positive integers, considered to be equivalent when terms or factors are reordered.

1, 1, 2, 3, 6, 8, 14, 19, 31, 43, 65, 88, 132, 177, 253, 340, 478, 633, 874, 1150, 1562, 2045, 2736, 3553, 4713, 6082, 7969, 10234, 13301, 16973, 21889, 27789, 35577, 44961, 57179, 71906, 90950, 113874, 143204, 178592, 223505, 277599, 345822, 427934, 530797

Offset: 0

Author

Alois P. Heinz, Apr 22 2012

Keywords

• nonn

Comments

From Yifan Xie, Sep 25 2024: (Start)

a(n) is the number of distinct sets A = {b_1, b_2, ..., b_n} such that 2*n positive integers x_1, x_2, ..., x_(2*n) exist where A = {x_1+x_2, x_3+x_4, ..., x_(2*n-1)+x_(2*n)} = {x_1*x_2, x_3*x_4, ..., x_(2*n-1)*x_(2*n)}.

Proof: Suppose that the number of sets A is b(n). Denote (x_(2*i-1)-1)*(x_(2*i)-1) by c_i. (1 <= i <= n)

Taking the sums of B and C, c_1 + c_2 + ... + c_n = n. (1)

Consider b_1, ..., b_n as n vertices, then the map B -> C is a directed graph G on these vertices, where each vertex has a source and a sink, so it can either be a cycle itself or decomposed into two or more cycles.

For the first case, the condition is equivalent to every proper subset of A' = {b_1, ..., b_n} is invalid for the corresponding n. Using (1), every partial sum of c_i is not equal to the number of addends. Therefore, c_i != 1. Then there must exist c_j = 0, hence c_i != 2. Then there must exist another c_k = 0, hence c_i != 3, and so on. Thus c_1, c_2, ..., c_n must be a permutation of 0, 0, ..., 0, n. Suppose that c_n = n, x_1 = x_3 = ... = x_(2*n-3) = 1. Since n has floor((A000005(n)+1)/2) ways to be expressed as the product of two positive integers, each product n = y*z means that x_(2*i-1) = y+1, x_(2*i) = z+1, thus there exists (y+1)*(z+1) in A, 1 + x_(2*l) = (a+1)*(b+1), 1*x_(2*l) = (a+1)*(b+1)-1, there exists (a+1)*(b+1)-1 in A, and so on until a+b+2 = (a+1)*(b+1)-1. In conclusion, there are floor((A000005(n)+1)/2) distinct A's in the second case, each of which is a group of consecutive integers. Denote the array by n = a*b .

For the second case, the array A can be decomposed into smaller arrays representing smaller n's, without breaking the structures of B and C. This process will finally end with all smaller arrays in the first case. Using the same notation, the arrays can be expressed as n = y_1*z_1 + y_2*z_2 + ... + y_s*z*s.

Therefore b(n) is the number of representations of n as a sum of products of pairs of unordered positive integers, hence b(n) = a(n). (End)

Examples

			a(0) = 1: 0 = the empty sum.
a(1) = 1: 1 = 1*1.
a(2) = 2: 2 = 1*1 + 1*1 = 1*2.
a(3) = 3: 3 = 1*1 + 1*1 + 1*1 = 1*1 + 1*2 = 1*3.
a(4) = 6: 4 = 1*1 + 1*1 + 1*1 + 1*1 = 1*1 + 1*1 + 1*2 = 1*1 + 1*3 = 1*2 + 1*2 = 2*2 = 1*4.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000
• N. J. A. Sloane, Transforms

Crossrefs

Cf. A000005, A006171, A038548, A066739, A182270, A211856, A211857.

Programs

Maple

with(numtheory):
a:= proc(n) option remember;  `if`(n=0, 1, add(add(
       d*ceil(tau(d)/2), d=divisors(j)) *a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..60);

Mathematica

a[n_] := a[n] = If[n == 0, 1, Sum[Sum[d*Ceiling[DivisorSigma[0, d]/2], {d, Divisors[j]}]*a[n-j], {j, 1, n}]/n]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Sep 09 2014, after Alois P. Heinz *)
nmax = 50; CoefficientList[Series[Product[Product[1/(1 - x^(k*j)), {j, 1, Min[k, nmax/k]}], {k, 1, nmax}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Aug 19 2019 *)

Formula

Euler transform of A038548.

G.f.: Product_{k>0} 1/(1-x^k)^A038548(k).

G.f.: Product_{k>=1} (Product_{j=1..k} 1/(1 - x^(k*j))). - Vaclav Kotesovec, Aug 19 2019