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

Triangle obtained from A047996 by dropping the first column (k=0), and row (n=0).

T(n, k) = number of different ways the number n can be expressed as ordered sums of k positive integers, counting only once those ordered sums that can be transformed into each other by a cyclic permutation.

These might be described as cyclic compositions, or more loosely as cyclic partitions. - N. J. A. Sloane, Sep 05 2012

The row polynomials P(n,x) := Sum_{k=0..p(n)-1} a(n,k)*x^k, n >= 1, appear in the numerator of the g.f. G(p(n),x) for the numbers N(p(n),m) of inequivalent m-bead necklaces of two colors with p(n) beads of one color and m-p(n) beads of the other color. Here p(n)=A000040(n) (prime numbers). Equivalently, N(p(n),m) counts inequivalent necklaces with p(n) beads which are labeled with nonnegative numbers, such that the sum of the labels is m. For a proof of this equivalent formulation see a comment in A032191. Inequivalence is meant with respect to the cyclic group C_p(n).

This necklace g.f. is G(p(n),x) = P(n,x)/((1-x^p(n))*(1-x)^(p(n)-1)), n >= 1. The row polynomials P(n,x) are defined above. This g.f. is Z(C_p(n),x), the two variable (x[1] and x[p(n)]) cycle index polynomial for the cyclic group of prime order p(n), with substitution x[1]->1/(1-x^1)and x[p(n)]->1/(1-x^p(n)). This follows by Polya enumeration if the above mentioned labeled necklace problem is solved.

The row length sequence for this array a(n,k) is A000040(n) (n-th prime number), [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...].

The rows of this signed array are symmetric: a(n,k) = a(n,p(n)-1-k), n >= 2, k = 0..(p(n)-1)/2. See the explicit formula below.

The formulas for a(n,k), given below, produces in fact integers.

G.f. for column k, k>=0 (without leading zeros): sum(A103718(k,m)*p(n)^m,m=0..k)/k! produces for all n> pi(n) integers, where pi(n):=A000720(n), primes not exceeeding n.

"CIK[ 7 ]" (necklace, indistinct, unlabeled, 7 parts) transform of 1, 1, 1, 1, ...

The g.f. is Z(C_7,x)/x^7, the 7-variate cycle index polynomial for the cyclic group C_7, with substitution x[i]->1/(1-x^i), i=1,...,7. Therefore by Polya enumeration a(n+7) is the number of cyclically inequivalent 7-necklaces whose 7 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... See A102190 for Z(C_7,x) and 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, Dec 08 2017: (Start)

For p prime, if a_p(n) is the number of necklaces with p black beads and n-p white beads, then (a_p(n): n>=1) = CIK[p](1, 1, 1, 1, ...). Since CIK[k](B(x)) = (1/k)*Sum_{d|k} phi(d)*B(x^d)^{k/d} with k = p and B(x) = x + x^2 + x^3 + ... = x/(1-x), we get Sum_{n>=1} a_p(n)*x^n = ((p-1)/(1 - x^p) + 1/(1 - x)^p)*x^p/p, which is Herbert Kociemba's general formula for the g.f. when p is prime.

We immediately get a_p(n) = ((p-1)/p)*I(p|n) + (1/p)*C(n-1,p-1) = ((p-1)/p)*I(p|n) + (1/n)*C(n,p) = ceiling(C(n,p)/n), which is a generalization of the conjecture made by N. J. A. Sloane and Wolfdieter Lang. (Here, I(condition) = 1 if the condition holds, and 0 otherwise. Also, as usual, for integers n and k, C(n,k) = 0 if 0 <= n < k.)

Since the sequence (a_p(n): n>=1) is column k = p of A047996(n,k) = T(n,k), we get from the documentation of the latter sequence that a_p(n) = T(n, p) = (1/n)*Sum_{d|gcd(n,p)} phi(d)*C(n/d, p/d), from which we get another proof of the formulae for a_p(n).

(End)

The g.f. is Z(C_8,x)/x^8, the 8-variate cycle index polynomial for the cyclic group C_8, with substitution x[i]->1/(1-x^i), i=1,...,8. Therefore by Polya enumeration a(n+8) is the number of cyclically inequivalent 8-necklaces whose 8 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... See A102190 for Z(C_8,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, Aug 31 2018: (Start)

The CIK[k] transform of sequence (c(n): n>=1) has generating function A_k(x) = (1/k)*Sum_{d|k} phi(d)*C(x^d)^{k/d}, where C(x) = Sum_{n>=1} c(n)*x^n is the g.f. of (c(n): n>=1).

When c(n) = 1 for all n >= 1, we get C(x) = x/(1-x) and A_k(x) = (x^k/k)*Sum_{d|k} phi(d)*(1-x^d)^{-k/d}, which is the g.f. of the number a_k(n) of necklaces of n beads of 2 colors with k of them black and n-k of them white.

Using Taylor expansions, we can easily prove that a_k(n) = (1/k)*Sum_{d|gcd(n,k)} phi(d)*binomial(n/d - 1, k/d - 1) = (1/n)*Sum_{d|gcd(n,k)} phi(d)*binomial(n/d, k/d), which is Robert A. Russell's formula in the Mathematica code below.

For this sequence k = 8, and thus we get the formulae below.

(End)

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

Columns can be computed by a method analogous to that of Fripertinger for isometry classes of linear codes, disallowing scalar transformation of individual coordinates.

Regarding the formula for column k = 1, note that A241926(q - 1, n) counts, up to coordinate permutation, one-dimensional subspaces of (F_q)^n generated by a vector with no zero component.

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