cp's OEIS Frontend

The g.f. is Z(C_9,x)/x^9, the 9-variate cycle index polynomial for the cyclic group C_9, with substitution x[i]->1/(1-x^i), i=1,...,9. Therefore by Polya enumeration a(n+9) is the number of cyclically inequivalent 9-necklaces whose 9 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... See A102190 for Z(C_9,x). See the comment in A032191 on the equivalence of this problem with the one given in the `Name' line. - Wolfdieter Lang, Feb 15 2005

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

The g.f. is Z(C_10,x)/x^10, the 10-variate cycle index polynomial for the cyclic group C_10, with substitution x[i]->1/(1-x^i), i=1,...,10. By Polya enumeration, a(n+10) is the number of cyclically inequivalent 10-necklaces whose 10 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... See A102190 for Z(C_10,x). See the comment in A032191 on the equivalence of this problem with the one given in the `Name' line. - Wolfdieter Lang, Feb 15 2005

The g.f. is Z(C_11,x)/x^11, the 11-variate cycle index polynomial for the cyclic group C_11, with substitution x[i]->1/(1-x^i), i=1..11. By Polya enumeration, a(n+11) is the number of cyclically inequivalent 11-necklaces whose 11 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... See A102190 for Z(C_11,x). See the comment in A032191 on the equivalence of this problem with the one given in the `Name' line. - Wolfdieter Lang, Feb 15 2005

The g.f. is Z(C_12,x)/x^12, the 12-variate cycle index polynomial for the cyclic group C_12, with substitution x[i]->1/(1-x^i), i=1,...,12. Therefore by Polya enumeration a(n+12) is the number of cyclically inequivalent 12-necklaces whose 12 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... See A102190 for Z(C_12,x). See the comment in A032191 on the equivalence of this problem with the one given in the `Name' line. - Wolfdieter Lang, Feb 15 2005