A267632 -id:A267632 - cp's OEIS frontend

A082550 Number of sets of distinct positive integers whose arithmetic mean is an integer, the largest integer of the set being n.

1, 1, 3, 3, 7, 11, 19, 31, 59, 103, 187, 343, 631, 1171, 2191, 4095, 7711, 14571, 27595, 52431, 99879, 190651, 364723, 699071, 1342183, 2581111, 4971067, 9586983, 18512791, 35791471, 69273667, 134217727, 260301175, 505290271, 981706831, 1908874583, 3714566311

Offset: 1

Naohiro Nomoto, May 03 2003

Equivalently, number of nonempty subsets of [n] the sum of whose elements is divisible by n. - Dimitri Papadopoulos, Jan 18 2016

			a(5) = 7: the seven sets are (1+2+3+4+5)/5 = 3, 5/1 = 5, (1+5)/2 = 3, (1+3+5)/3 = 3, (3+5)/2 = 4, (3+4+5)/3 = 4, (1+2+4+5)/4 = 3.

Cf. A008965, A051293, A063776, A309402.

Row sums of A267632.

Table[Length[Select[Select[Subsets[Range[n]],Max[#]==n&], IntegerQ[ Mean[ #]]&]], {n,22}] (* Harvey P. Dale, Jul 23 2011 *)
Table[Total[Table[Length[Select[Select[Subsets[Range[n]], Length[#] == k &],IntegerQ[Total[#]/n] &]], {k, n}]], {n, 10}] (* Dimitri Papadopoulos, Jan 18 2016 *)

a(n) = sumdiv(n, d, (d%2)* 2^(n/d)*eulerphi(d))/n - 1; \\ Michel Marcus, Feb 10 2016

from sympy import totient, divisors
def A082550(n): return (sum(totient(d)<>(~n&n-1).bit_length(),generator=True))<<1)//n-1 # Chai Wah Wu, Feb 22 2023

a(n) = A063776(n) - 1.
a(n) = A051293(n+1) - A051293(n). - Reinhard Zumkeller, Feb 19 2006
a(n) = A008965(n) for odd n. - Dimitri Papadopoulos, Jan 18 2016
G.f.: -x/(1 - x) - Sum_{m >= 0} (phi(2*m + 1)/(2*m + 1)) * log(1 - 2*x^(2*m + 1)). - Petros Hadjicostas, Jul 13 2019
a(n) = A309402(n,n). - Alois P. Heinz, Jul 28 2019

a(22) from Harvey P. Dale, Jul 23 2011

a(23)-a(32) from Dimitri Papadopoulos, Jan 18 2016

A032801 Number of unordered sets a, b, c, d of distinct integers from 1..n such that a+b+c+d = 0 (mod n).

Original entry on oeis.org

0, 0, 0, 0, 1, 3, 5, 9, 14, 22, 30, 42, 55, 73, 91, 115, 140, 172, 204, 244, 285, 335, 385, 445, 506, 578, 650, 734, 819, 917, 1015, 1127, 1240, 1368, 1496, 1640, 1785, 1947, 2109, 2289, 2470, 2670, 2870, 3090, 3311, 3553, 3795, 4059, 4324, 4612, 4900, 5212, 5525

Offset: 1

N. J. A. Sloane

From Petros Hadjicostas, Jul 12 2019: (Start)
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).
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).
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.
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.
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).
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).
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.
(End)
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

E. V. McLaughlin, Numbers of factorizations in non-unique factorial domains, Senior Thesis, Allegeny College, Meadville, PA, April 2004.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Eric Stephen Barnes, The construction of perfect and extreme forms I, Acta Arith., 5 (1959); see pp. 65-66.
David Broadhurst and Xavier Roulleau, Number of partitions of modular integers, arXiv:2502.19523 [math.NT], 2025. See pp. 4, 14, 19.
K. G. Ramanathan, Some applications of Ramanujan's trigonometrical sum C_m(n), Proc. Indian Acad. Sci., Sect. A 20 (1944), 62-69; see p. 66.
R. D. von Sterneck, Ein Analogon zur additiven Zahlentheorie, Sitzungsber. Akad. Wiss. Sapientiae Math.-Naturwiss. Kl. 111 (1902), 1567-1601 (Abt. IIa). [Accessible only in the USA through the HathiTrust Digital Library.]
R. D. von Sterneck, Über ein Analogon zur additiven Zahlentheorie, Jahresbericht der Deutschen Mathematiker-Vereinigung 12 (1903), 110-113. [This is a summary of the 1902 paper.]
Index entries for linear recurrences with constant coefficients, signature (2,0,-2,2,-2,0,2,-1).

Cf. A001399, A001400, A004526, A008646, A054533, A058212, A008610.

Column k=4 of A267632.

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;

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

G.f.: x^5*(1+x-x^2+x^3)/((-1+x)^4*(1+x)^2*(1+x^2)). - Herbert Kociemba, Oct 22 2016
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
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

Offset changed by David A. Corneth, Oct 23 2016

A309122 Sum of the sizes of all subsets of [n] whose sum is divisible by n.

Original entry on oeis.org

1, 1, 6, 6, 20, 34, 70, 124, 270, 516, 1034, 2060, 4108, 8198, 16440, 32760, 65552, 131142, 262162, 524312, 1048740, 2097162, 4194326, 8388856, 16777300, 33554444, 67109418, 134217764, 268435484, 536872072, 1073741854, 2147483632, 4294969404, 8589934608

Offset: 1

Alois P. Heinz, Jul 13 2019

nonn

The bivariate g.f. of array T(n,k) = A267632(n,k) is Sum_{n, k >= 1} T(n,k) * x^n * y^k = -x/(1 - x) - Sum_{s >= 1} (phi(s)/s) * log(1 - x^s + (-x*y)^s). Differentiating w.r.t. y and setting y = 1, we get the g.f. of a(n) = k * Sum_{1 <= k <= n} T(n,k) (see below). - Petros Hadjicostas, Jul 13 2019

			a(5) = 20 = 0 + 1 + 2 + 2 + 3 + 3 + 4 + 5 = |{}| + |{5}| + |{1,4}| + |{2,3}| + |{1,4,5}| + |{2,3,5}| + |{1,2,3,4}| + |{1,2,3,4,5}|.

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A000010, A053636, A267632, A309128.

b:= proc(n, m, s) option remember; `if`(n=0, [`if`(s=0, 1, 0), 0],
      b(n-1, m, s) +(g-> g+[0, g[1]])(b(n-1, m, irem(s+n, m))))
    end:
a:= proc(n) option remember; forget(b); b(n$2, 0)[2] end:
seq(a(n), n=1..40);

b[n_, m_, s_] := b[n, m, s] = If[n == 0, {If[s == 0, 1, 0], 0},
     b[n-1, m, s] + Function[g, g + {0, g[[1]]}][b[n-1, m, Mod[s+n, m]]]];
a[n_] := b[n, n, 0][[2]];
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Mar 19 2022, after Alois P. Heinz *)

a(n) = Sum_{k=1..n} k * A267632(n,k).
From Petros Hadjicostas, Jul 13 2019: (Start)
G.f.: Sum_{s >= 1} phi(s) * (-x)^(s-1)/(1 - x^s + (-x)^s) = -Sum_{m >= 1} phi(2*m) * x^(2*m-1) + Sum_{m >= 0} phi(2*m+1) * x^(2*m)/(1 - 2*x^(2*m+1)).
a(2*m + 1) = A053636(2*m + 1)/2 = (1/2) * Sum_{d|2*m+1} phi(d) * 2^((2*m+1)/d) for m >= 0.
a(2*m) = -phi(2*m) +  A053636(2*m)/2 for m >= 1.
(End)

A322596 Square array read by descending antidiagonals (n >= 0, k >= 0): let b(n,k) = (n+k)!/((n+1)!*k!); then T(n,k) = b(n,k) if b(n,k) is an integer, and T(n,k) = floor(b(n,k)) + 1 otherwise.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 3, 4, 3, 1, 1, 1, 3, 5, 5, 3, 1, 1, 1, 4, 7, 9, 7, 4, 1, 1, 1, 4, 10, 14, 14, 10, 4, 1, 1, 1, 5, 12, 21, 26, 21, 12, 5, 1, 1, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 1, 6, 19, 42, 66, 77, 66, 42, 19, 6, 1, 1, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1, 1

Offset: 0

Franck Maminirina Ramaharo, Jan 22 2019

For n >= 1, T(n,k) is the number of nodes in n-dimensional space for Mysovskikh's cubature formula which is exact for any polynomial of degree k of n variables.

			Array begins:
  1, 1, 1,  1,  1,   1,   1,    1,    1,    1, ...
  1, 1, 2,  2,  3,   3,   4,    4,    5,    5, ...
  1, 1, 2,  4,  5,   7,  10,   12,   15,   19, ...
  1, 1, 3,  5,  9,  14,  21,   30,   42,   55, ...
  1, 1, 3,  7, 14,  26,  42,   66,   99,  143, ...
  1, 1, 4, 10, 21,  42,  77,  132,  215,  334, ...
  1, 1, 4, 12, 30,  66, 132,  246,  429,  715, ...
  1, 1, 5, 15, 42,  99, 215,  429,  805, 1430, ...
  1, 1, 5, 19, 55, 143, 334,  715, 1430, 2702, ...
  1, 1, 6, 22, 72, 201, 501, 1144, 2431, 4862, ...
  ...
As triangular array, this begins:
  1;
  1, 1;
  1, 1,  1;
  1, 2,  1,  1;
  1, 2,  2,  1,  1;
  1, 3,  4,  3,  1,  1;
  1, 3,  5,  5,  3,  1,  1;
  1, 4,  7,  9,  7,  4,  1,  1;
  1, 4, 10, 14, 14, 10,  4,  1, 1;
  1, 5, 12, 21, 26, 21, 12,  5, 1, 1;
  1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1;
  ...

Ronald Cools, Encyclopaedia of Cubature Formulas
Ivan P. Mysovskikh, On the construction of cubature formulae for very simple domains, USSR Computational Mathematics and Mathematical Physics, Volume 4, Issue 1, 1964, 1-17.

Main diagonal: A000108.

Cf. A007318, A037306, A046854, A047996, A065941, A241926, A267632.

b(n, k) := (n + k)!/((n + 1)!*k!)$
T(n, k) := if integerp(b(n, k)) then b(n, k) else floor(b(n, k)) + 1$
create_list(T(k, n - k), n, 0, 15, k, 0, n);

cp's OEIS Frontend

A082550 Number of sets of distinct positive integers whose arithmetic mean is an integer, the largest integer of the set being n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A032801 Number of unordered sets a, b, c, d of distinct integers from 1..n such that a+b+c+d = 0 (mod n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A309122 Sum of the sizes of all subsets of [n] whose sum is divisible by n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A322596 Square array read by descending antidiagonals (n >= 0, k >= 0): let b(n,k) = (n+k)!/((n+1)!*k!); then T(n,k) = b(n,k) if b(n,k) is an integer, and T(n,k) = floor(b(n,k)) + 1 otherwise.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maxima