cp's OEIS Frontend

Equivalently, T(n,k) = number of necklaces with k black beads and n-k white beads (binary necklaces of weight k).

The same sequence arises if we take the table U(n,k) = number of necklaces with n black beads and k white beads and read it by antidiagonals (cf. A241926). - Franklin T. Adams-Watters, May 02 2014

U(n,k) is also equal to the number of ways to express 0 as a sum of k elements in Z/nZ. - Jens Voß, Franklin T. Adams-Watters, N. J. A. Sloane, Apr 30 2014 - May 05 2014. See link ("A Note on Modular Partitions and Necklaces") for proof.

The generating function for column k is given by the substitution x_j -> x^j/(1-x^j) in the cycle index of the Symmetric Group of order k. - R. J. Mathar, Nov 15 2018

From Petros Hadjicostas, Jul 12 2019: (Start)

Regarding the comments above by Voss, Adams-Watters, and Sloane, note that Fredman (1975) proved that the number S(n, k, v) of vectors (a_0, ..., a_{n-1}) of nonnegative integer components that satisfy a_0 + ... + a_{n-1} = k and Sum_{i=0..n-1} i*a_i = v (mod n) is given by S(n, k, v) = (1/(n + k)) * Sum_{d | gcd(n, k)} A054535(d, v) * binomial((n + k)/d, k/d) = S(k, n, v).

This result was also proved by Elashvili et al. (1999), who also proved that S(n, k, v) = Sum_{d | gcd(n, k, v)} S(n/d, k/d, 1). Here, S(n, k, 0) = A241926(n, k) = U(n, k) = T(n + k, k) (where T(n, k) is the current array). Also, S(n, k, 1) = A245558(n, k). See also Panyushev (2011) for more general results and for generating functions.

Finally, note that A054535(d, v) = c_d(v) = Sum_{s | gcd(d,v)} s*Moebius(d/s). These are the Ramanujan sums, which equal also the von Sterneck function c_d(v) = phi(d) * Moebius(d/gcd(d, v))/phi(d/gcd(d, v)). We have A054535(d, v) = A054534(v, d).

It would be interesting to see whether there is a proof of the results by Fredman (1975), Elashvili et al. (1999), and Panyushev (2011) for a general v using Molien series as it is done by Sloane (2014) for the case v = 0 (in which case, A054535(d, 0) = phi(d)). (Even though the columns of array A054535(d, v) start at v = 1, we may start the array at column v = 0 as well.)

(End)

U(n, k) is the number of equivalence classes of k-tuples of residues modulo n, identifying those that differ componentwise by a constant and those that differ by a permutation. - Álvar Ibeas, Sep 21 2021

From Wolfdieter Lang, Jan 06 2017: (Start)

Periodicity: c_n(k+n) = c_n(k). See the Apostol reference p. 161.

Multiplicativity: c_n(k)*c_m(k) = c_{n*m}(k), if gcd(n,m) = 1. For the proof see the Hardy reference, p. 138.

Dirichlet g.f. for fixed k: D(n,s) := Sum_{n>=1} c_n(k)/n^s = sigma_{1-s}(k)/zeta(s) = sigma_{s-1}(k)/(k^(s-1)*zeta(s)) for s > 1, with sigma_m(k) the sum of the m-th power of the divisors of k. See the Hardy reference, eqs. (9.6.1) and (9.6.2), pp. 139-140, or Hardy-Wright, Theorem 292, p. 250.

Sum_{n>=1} c_n(k)/n = 0. See the Hardy reference, p. 141. (End)

Right border gives A000010. - Omar E. Pol, May 08 2018

Fredman (1975) proved that the number S(n, k, v) of vectors (a_0, ..., a_{n-1}) of nonnegative integer components that satisfy a_0 + ... + a_{n-1} = k and Sum_{i=0..n-1} i*a_i = v (mod n) is given by S(n, k, v) = (1/(n + k)) * Sum_{d | gcd(n, k)} T(d, v) * binomial((n + k)/d, k/d) = S(k, n, v). This was also proved by Elashvili et al. (1999), who also proved that S(n, k, v) = Sum_{d | gcd(n, k, v)} S(n/d, k/d, 1). Here, S(n, k, 1) = A051168(n + k, k). - Petros Hadjicostas, Jul 09 2019

We have T(n, k) = c_n(k) = Sum_{m=1..n, (m,n)=1} exp(2 Pi i m k / n) and A054532(n, k) = c_k(n) = Sum_{m=1..k, (m,k)=1} exp(2 Pi i m n / k) for n >= 1 and 1 <= k <= n. - Petros Hadjicostas, Jul 27 2019

Replace the first column in A077049 with any k-th column in A177121 to get a new array. Then the matrix inverse of the new array will have the k-th column of A054535 (this array) as its first column. - Mats Granvik, May 03 2010

We have T(n, k) = c_n(k) = Sum_{m=1..n, (m,n)=1} exp(2 Pi i m k / n) and

A054534(n, k) = c_k(n) = Sum_{m=1..k, (m,k)=1} exp(2 Pi i m n / k). That is, the current array is the transpose of array A054534. Dirichlet g.f.'s for these two arrays are given below by R. J. Mathar and Mats Granvik. - Petros Hadjicostas, Jul 27 2019

T(n, k) = c_k(n) = sum of the n-th powers of the k-th primitive roots of unity. - Petros Hadjicostas, Jul 27 2019

Mobius transform of 1,2,0,0,0,0,... (A130779). - R. J. Mathar, Mar 24 2012

a(n,0) = phi(n), where phi(n) is Euler's totient function A000010(n).

a(n,1) = mu(n), where mu(n) is the Möbius function A008683(n).

Row less the last element is palindrome for n=odd or n=power of 2 where n is the row number (observation-conjecture).

From Petros Hadjicostas, Jul 13 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).

According to the definition of this sequence, for 1 <= k <= n, T(n, k) 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 = 0 (mod n). The proof of Lemma 5.1 in Barnes (1959) implies that T(n, k) = (1/n) * Sum_{s | gcd(n, k)} (-1)^(k - (k/s)) * phi(s) * binomial(n/s, k/s) for 1 <= k <= n.

For fixed k >= 1, the g.f. of the column (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), which generalizes Herbert Kociemba's formula from A032801.

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) = A054535(s, v) = Sum_{d | gcd(s,v)} d * Moebius(s/d) is Ramanujan's sum (even though it was first discovered 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) for 1 <= k <= n.

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=4, we have R(n, k=4, v=0) = A032801(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.

The reason we have T(2*m+1, k) = A037306(2*m+1, k) = A047996(2*m+1, k) for m >= 0 and k >= 1 is the following. When n = 2*m + 1, all divisors s of gcd(n, k) are odd. In such a case, k - (k/s) is even for all k >= 1, and thus (-1)^(k - (k/s)) = 1, and thus T(n = 2*m+1, k) = (1/n) * Sum_{s | gcd(n, k)} phi(s) * binomial(n/s, k/s) = A037306(2*m+1, k) = A047996(2*m+1, k).

By summing the products of the g.f. of column k times y^k from k = 1 to k = infinity, we get the bivariate g.f. for the array: Sum_{n, k >= 1} T(n, k)*x^n*y^k = Sum_{s >= 1} (phi(s)/s) * log((1 - x^s + (-x*y)^s)/(1 - x^s)) = -x/(1 - x) - Sum_{s >= 1} (phi(s)/s) * log(1 - x^s + (-x*y)^s).

Letting y = 1 in the above bivariate g.f., we get the g.f. of the sequence (Sum_{1 <= k <= n} T(n, k): n >= 1) is -x/(1 - x) - Sum_{s >= 1} (phi(s)/s) * log(1 - x^s + (-x)^s) = -x/(1 - x) + Sum_{m >= 0} (phi(2*m + 1)/(2*m + 1)) * log(1 - 2*x^(2*m+1)), which is the g.f. of sequence A082550. Hence, sequence A082550 consists of the row sums.

There is another important interpretation of this array T(n, k) which is related to some of the references for sequence A047996, but because the discussion is too lengthy, we omit the details.

(End)