login
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.
20

%I #34 Oct 20 2024 14:01:18

%S 1,1,2,3,6,8,14,19,31,43,65,88,132,177,253,340,478,633,874,1150,1562,

%T 2045,2736,3553,4713,6082,7969,10234,13301,16973,21889,27789,35577,

%U 44961,57179,71906,90950,113874,143204,178592,223505,277599,345822,427934,530797

%N 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.

%C From _Yifan Xie_, Sep 25 2024: (Start)

%C 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)}.

%C 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)

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

%C 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.

%C 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 .

%C 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.

%C 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)

%H Alois P. Heinz, <a href="/A182269/b182269.txt">Table of n, a(n) for n = 0..10000</a>

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%F Euler transform of A038548.

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

%F G.f.: Product_{k>=1} (Product_{j=1..k} 1/(1 - x^(k*j))). - _Vaclav Kotesovec_, Aug 19 2019

%e a(0) = 1: 0 = the empty sum.

%e a(1) = 1: 1 = 1*1.

%e a(2) = 2: 2 = 1*1 + 1*1 = 1*2.

%e a(3) = 3: 3 = 1*1 + 1*1 + 1*1 = 1*1 + 1*2 = 1*3.

%e 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.

%p with(numtheory):

%p a:= proc(n) option remember; `if`(n=0, 1, add(add(

%p d*ceil(tau(d)/2), d=divisors(j)) *a(n-j), j=1..n)/n)

%p end:

%p seq(a(n), n=0..60);

%t 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_ *)

%t 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 *)

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

%K nonn

%O 0,3

%A _Alois P. Heinz_, Apr 22 2012