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

Number of double-stars (diameter 3 trees) with n nodes. For n >= 3, number of partitions of n-2 into two parts. - Washington Bomfim, Feb 12 2011

Number of roots of the n-th Bernoulli polynomial in the left half-plane. - Michel Lagneau, Nov 08 2012

From Gus Wiseman, Oct 17 2020: (Start)

Also the number of 3-part non-strict integer partitions of n - 1. The Heinz numbers of these partitions are given by A285508. The version for partitions of any length is A047967, with Heinz numbers A013929. The a(4) = 1 through a(15) = 6 partitions are (A = 10, B = 11, C = 12):

111 211 221 222 322 332 333 433 443 444 544 554

311 411 331 422 441 442 533 552 553 644

511 611 522 622 551 633 661 662

711 811 722 822 733 833

911 A11 922 A22

B11 C11

(End)

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

Table starts

..1...1....1.....1.....1......1......1.......1.......1.......1.......1........1

..1...2....2.....3.....3......4......4.......5.......5.......6.......6........7

..1...2....4.....5.....7.....10.....12......15......19......22......26.......31

..2...6...12....23....38.....60.....88.....125.....170.....226.....292......371

..2..11...34....88...187....358....625....1023....1584....2355....3374.....4700

..4..33..144...471..1237...2798...5648...10483...18174...29863...46918....71037

..6..86..576..2517..8235..22249..52208..110285..214440..390344..672932..1108883

.13.278.2613.14611.58524.186765.505857.1210780.2631514.5293759.9995616.17902216

The g.f. is Z(C_6,x)/x^6, the 6-variate cycle index polynomial for the cyclic group C_6, with substitution x[i]->1/(1-x^i), i=1,...,6. Therefore by Polya enumeration a(n+6) is the number of cyclically inequivalent 6-necklaces whose 6 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... See A102190 for Z(C_6,x). Note the equivalence of this formulation with the one given as this sequence's name: start with a black 6-necklace (all 6 beads have labels 0). Insert after each of the 6 black beads k white ones if the label was k and then disregard the labels. - Wolfdieter Lang, Feb 15 2005

The g.f. of the CIK[k] transform of the sequence (b(n): n>=1), which has g.f. B(x) = Sum_{n>=1} b(n)*x^n, is CIK[k](x) = (1/k)*Sum_{d|k} phi(d)*B(x^d)^{k/d}. Here, k = 6, b(n) = 1 for all n >= 1, and B(x) = x/(1-x), from which we get another proof of the g.f.s given below. - Petros Hadjicostas, Jan 07 2018

From Gus Wiseman, Oct 15 2020: (Start)

Also the number of 3-part compositions of n that are neither strictly increasing nor weakly decreasing. The set of numbers k such that row k of A066099 is such a composition is the complement of A333255 (strictly increasing) and A114994 (weakly decreasing) in A014311 (triples). The a(4) = 2 through a(9) = 14 compositions are:

(1,1,2) (1,1,3) (1,1,4) (1,1,5) (1,1,6) (1,1,7)

(1,2,1) (1,2,2) (1,3,2) (1,3,3) (1,4,3) (1,4,4)

(1,3,1) (1,4,1) (1,4,2) (1,5,2) (1,5,3)

(2,1,2) (2,1,3) (1,5,1) (1,6,1) (1,6,2)

(2,3,1) (2,1,4) (2,1,5) (1,7,1)

(3,1,2) (2,2,3) (2,2,4) (2,1,6)

(2,3,2) (2,3,3) (2,2,5)

(2,4,1) (2,4,2) (2,4,3)

(3,1,3) (2,5,1) (2,5,2)

(4,1,2) (3,1,4) (2,6,1)

(3,2,3) (3,1,5)

(3,4,1) (3,2,4)

(4,1,3) (3,4,2)

(5,1,2) (3,5,1)

(4,1,4)

(4,2,3)

(5,1,3)

(6,1,2)

(End)

(1+x)*(1+x^3)*(1+x^5)/((1-x^2)*(1-x^4)*(1-x^6)) is the Poincaré series [or Poincare series] (or Molien series) for symmetric invariants in F_2(b_1, b_2, ... b_n) ⊗ E(e_1, e_2, ... e_n) with b_i 2-dimensional, e_i one-dimensional and the permutation action of S_n, in the case n=3.

The hexagonal lattice is the familiar 2-dimensional lattice in which each point has 6 neighbors. This is sometimes called the triangular lattice.

Also the number of triangles with vertices on points of the hexagonal lattice that have area equal to n/2. - Amihay Hanany, Oct 15 2009 [Here the area is measured in the units of the lattice unit cell area; since the number of the triangles of different shapes with the same half-integral area is infinite, the triangles are probably counted up to the equivalence relation defined in the Davey, Hanany and Rak-Kyeong Seong paper. Also, this comment probably belongs to A003051, not here. - Andrey Zabolotskiy, Mar 10 2018 and Jul 04 2019]

Also number of 2n-vertex connected cubic vertex-transitive graphs which are Cayley graphs for a dihedral group [Potočnik et al.]. - N. J. A. Sloane, Apr 19 2014

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