|
%I #84 Sep 07 2022 11:15:25
%S 0,0,0,0,1,3,5,9,14,22,30,42,55,73,91,115,140,172,204,244,285,335,385,
%T 445,506,578,650,734,819,917,1015,1127,1240,1368,1496,1640,1785,1947,
%U 2109,2289,2470,2670,2870,3090,3311,3553,3795,4059,4324,4612,4900,5212,5525
%N Number of unordered sets a, b, c, d of distinct integers from 1..n such that a+b+c+d = 0 (mod n).
%C From _Petros Hadjicostas_, Jul 12 2019: (Start)
%C By reading carefully the proof of Lemma 5.1 (pp. 65-66) in Barnes (1959), we see that he actually proved a general result (even though he does not state it in the lemma). For 1 <= k <= n, let T(n, k) be the number of unordered sets b_1, b_2, ..., b_k of k distinct integers from 1..n such that b_1 + b_2 + ... + b_k = 0 (mod n). The proof of Lemma 5.1 in the paper implies that T(n, k) = (1/n) * Sum_{s | gcd(n, k)} (-1)^(k - (k/s)) * phi(s) * binomial(n/s, k/s).
%C For fixed k >= 1, the g.f. of the sequence (T(n, k): n >= 1) (with T(n, k) = 0 for 1 <= n < k) is (x^k/k) * Sum_{s|k} phi(s) * (-1)^(k - (k/s)) / (1 - x^s)^(k/s).
%C For k = 4, we get T(n, k=4) = (1/n) * Sum_{d | gcd(n, 4)} (-1)^(4/s) * phi(d) * binomial(n/d, 4/d), which agrees with Barnes' 3-part formula in Lemma 5.1 and with the formula in _N. J. A. Sloane_'s Maple program below. It also agrees with _Colin Barker_'s formula below.
%C For k = 4, the g.f. is (x^4/4) * Sum_{s|4} phi(s) * (-1)^(4/s) /(1 - x^s)^(4/s), which agrees with _Herbert Kociemba_'s g.f. below.
%C Barnes' (1959) formula is a special case of Theorem 4 (p. 66) in Ramanathan (1944). If R(n, k, v) is the number of unordered sets b_1, b_2, ..., b_k of k distinct integers from 1..n such that b_1 + b_2 + ... + b_k = v (mod n), then he proved that R(n, k, v) = (1/n) * Sum_{s | gcd(n,k)} (-1)^(k - (k/s)) * binomial(n/s, k/s) * C_s(v), where C_s(v) = A054533(s, v) is Ramanujan's sum (even though it was discovered first around 1900 by the Austrian mathematician R. D. von Sterneck).
%C Because C_s(v = 0) = phi(s), we get Barnes' (implicit) result; i.e., R(n, k, v=0) = T(n, k) and a(n) = R(n, k=4, v=0) = T(n, k=4).
%C For k=2, we have R(n, k=2, v=0) = T(n, k=2) = A004526(n-1) for n >= 1. For k=3, we have R(n, k=3, v=0) = T(n, k=3) = A058212(n) for n >= 1. For k=5, we have R(n, k=5, v=0) = T(n, k=5) = A008646(n-5) for n >= 5.
%C (End)
%C Von Sterneck (1902, 1903) dealt with this problem. In his notation, we need to find (n)_i, the number of integer solutions of the congruence n = x_1 + ... + x_i (mod M) such that 0 <= x_1 < x_2 < ... < x_i < M, where (his n) = 0, (his M) = (our n), and (his i) = 4. He gave several formulas for solving this problem for various cases of his M (M = prime, M = product of two primes, M = power of 2, etc.). - _Petros Hadjicostas_, Aug 20 2019
%D E. V. McLaughlin, Numbers of factorizations in non-unique factorial domains, Senior Thesis, Allegeny College, Meadville, PA, April 2004.
%H Vincenzo Librandi, <a href="/A032801/b032801.txt">Table of n, a(n) for n = 1..1000</a>
%H Eric Stephen Barnes, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa5/aa516.pdf">The construction of perfect and extreme forms I</a>, Acta Arith., 5 (1959); see pp. 65-66.
%H K. G. Ramanathan, <a href="https://www.ias.ac.in/article/fulltext/seca/020/01/0062-0069">Some applications of Ramanujan's trigonometrical sum C_m(n)</a>, Proc. Indian Acad. Sci., Sect. A 20 (1944), 62-69; see p. 66.
%H R. D. von Sterneck, <a href="https://babel.hathitrust.org/cgi/pt?id=mdp.39015073682448&view=1up&seq=1599">Ein Analogon zur additiven Zahlentheorie</a>, Sitzungsber. Akad. Wiss. Sapientiae Math.-Naturwiss. Kl. 111 (1902), 1567-1601 (Abt. IIa). [Accessible only in the USA through the <a href="https://www.hathitrust.org/accessibility">HathiTrust Digital Library</a>.]
%H R. D. von Sterneck, <a href="https://eudml.org/doc/144877">Über ein Analogon zur additiven Zahlentheorie</a>, Jahresbericht der Deutschen Mathematiker-Vereinigung 12 (1903), 110-113. [This is a summary of the 1902 paper.]
%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-2,2,-2,0,2,-1).
%F G.f.: x^5*(1+x-x^2+x^3)/((-1+x)^4*(1+x)^2*(1+x^2)). - _Herbert Kociemba_, Oct 22 2016
%F a(n) = (-6 * (4 + 2*(-1)^n + (-i)^n + i^n) + (25 + 3*(-1)^n)*n - 12*n^2 + 2*n^3)/48, where i = sqrt(-1). - _Colin Barker_, Oct 23 2016
%F a(n) = -A008610(-n), per formulae of Ralf Stephan (A008610) and C. Barker (above). Also, A008610(n) - a(n+4) = (1+(-1)^signum(n mod 4))/2, i.e., (1,0,0,0,1,0,0,0,...) repeating (offset 0). - _Gregory Gerard Wojnar_, Jul 09 2022
%p f := n-> if n mod 2 <> 0 then (n-1)*(n-2)*(n-3)/24 elif n mod 4 = 0 then (n-4)*(n^2-2*n+6)/24 else (n-2)*(n^2-4*n+6)/24; fi;
%t CoefficientList[Series[(x^3 / 4) (1 / (1 - x)^4 + 1 / (1 - x^2)^2 - 2 / (1 - x^4)), {x, 0, 60}],x] (* _Vincenzo Librandi_, Jul 13 2019 *)
%Y Cf. A001399, A001400, A004526, A008646, A054533, A058212, A008610.
%Y Column k=4 of A267632.
%K nonn,easy
%O 1,6
%A _N. J. A. Sloane_
%E Offset changed by _David A. Corneth_, Oct 23 2016
|
