cp's OEIS Frontend

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.

%I A182269 #34 Oct 20 2024 14:01:18
%S A182269 1,1,2,3,6,8,14,19,31,43,65,88,132,177,253,340,478,633,874,1150,1562,
%T A182269 2045,2736,3553,4713,6082,7969,10234,13301,16973,21889,27789,35577,
%U A182269 44961,57179,71906,90950,113874,143204,178592,223505,277599,345822,427934,530797
%N 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.
%C A182269 From _Yifan Xie_, Sep 25 2024: (Start)
%C A182269 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 A182269 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 A182269 Taking the sums of B and C, c_1 + c_2 + ... + c_n = n. (1)
%C A182269 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 A182269 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 A182269 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 A182269 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 A182269 Alois P. Heinz, <a href="/A182269/b182269.txt">Table of n, a(n) for n = 0..10000</a>
%H A182269 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%F A182269 Euler transform of A038548.
%F A182269 G.f.: Product_{k>0} 1/(1-x^k)^A038548(k).
%F A182269 G.f.: Product_{k>=1} (Product_{j=1..k} 1/(1 - x^(k*j))). - _Vaclav Kotesovec_, Aug 19 2019
%e A182269 a(0) = 1: 0 = the empty sum.
%e A182269 a(1) = 1: 1 = 1*1.
%e A182269 a(2) = 2: 2 = 1*1 + 1*1 = 1*2.
%e A182269 a(3) = 3: 3 = 1*1 + 1*1 + 1*1 = 1*1 + 1*2 = 1*3.
%e A182269 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 A182269 with(numtheory):
%p A182269 a:= proc(n) option remember;  `if`(n=0, 1, add(add(
%p A182269        d*ceil(tau(d)/2), d=divisors(j)) *a(n-j), j=1..n)/n)
%p A182269     end:
%p A182269 seq(a(n), n=0..60);
%t A182269 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 A182269 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 A182269 Cf. A000005, A006171, A038548, A066739, A182270, A211856, A211857.
%K A182269 nonn
%O A182269 0,3
%A A182269 _Alois P. Heinz_, Apr 22 2012