cp's OEIS Frontend

T(h,k) is the number of classes of aperiodic binary words of k ones and h-k zeros; words u,v are in the same class if v is a cyclic permutation of u (e.g., u=111000, v=110001) and a word is aperiodic if not a juxtaposition of 2 or more identical subwords.

T(2n, n), T(2n+1, n), T(n, 3) match A022553, A000108, A001840, respectively. Row sums match A001037.

From R. J. Mathar, Jul 31 2008: (Start)

This triangle may also be regarded as the square array A(r,n), the n-th term of the r-th Witt transform of the all-1 sequence, r >= 1, n >= 0, read by antidiagonals:

This array begins as follows:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9

0 1 2 3 5 7 9 12 15 18 22 26 30 35 40 45 51 57 63

0 1 2 5 8 14 20 30 40 55 70 91 112 140 168 204 240 285 330

0 1 3 7 14 25 42 66 99 143 200 273 364 476 612 775 969 1197 1463

0 1 3 9 20 42 75 132 212 333 497 728 1026 1428 1932 2583 3384 4389 5598

0 1 4 12 30 66 132 245 429 715 1144 1768 2652 3876 5537 7752 10659 14421 19228

0 1 4 15 40 99 212 429 800 1430 2424 3978 6288 9690 14520 21318 30624 43263 60060

0 1 5 18 55 143 333 715 1430 2700 4862 8398 13995 22610 35530 54477 81719 120175

0 1 5 22 70 200 497 1144 2424 4862 9225 16796 29372 49742 81686 130750 204248

0 1 6 26 91 273 728 1768 3978 8398 16796 32065 58786 104006 178296 297160 482885

0 1 6 30 112 364 1026 2652 6288 13995 29372 58786 112632 208012 371384 643842

0 1 7 35 140 476 1428 3876 9690 22610 49742 104006 208012 400023 742900 1337220

0 1 7 40 168 612 1932 5537 14520 35530 81686 178296 371384 742900 1432613 2674440

...

It is essentially symmetric: A(r,r+i) = A(r,r-i+1).

Some of the diagonals are:

A(r,r+1): A000108

A(r,r): A022553

A(r,r-1): A000108

A(r,r+2): A000150

A(r,r+3): A050181

A(r,r+4): A050182

A(r,r+5): A050183

A(r,r-2): A000150 (End)

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)} A054533(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) = T(n + k, k). - Petros Hadjicostas, Jul 09 2019

"Necklaces with turning over allowed" are usually called bracelets. - Joerg Arndt, Jun 10 2016

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

Also number of n X 2 binary matrices under row and column permutations and column complementations (if offset is 0).

Also Molien series for certain 4-D representation of dihedral group of order 8.

With offset 4, number of bracelets (turnover necklaces) of n-bead of 2 colors with 4 red beads. - Washington Bomfim, Aug 27 2008

From Vladimir Shevelev, Apr 23 2011: (Start)

Also number of non-equivalent necklaces of 4 beads each of them painted by one of n colors.

The sequence solves the so-called Reis problem about convex k-gons in case k=4 (see our comment to A032279). (End)

Number of 2 X 2 matrices with nonnegative integer values totaling n under row and column permutations. - Gabriel Burns, Nov 08 2016

From Petros Hadjicostas, Jan 12 2019: (Start)

By "necklace", Vladimir Shevelev (above) means "turnover necklace", i.e., a bracelet. Zagaglia Salvi (1999) also uses this terminology: she calls a bracelet "necklace" and a necklace "cycle".

According to Cyvin et al. (1997), the sequence (a(n): n >= 0) consists of "the total numbers of isomers of polycyclic conjugated hydrocarbons with q + 1 rings and q internal carbons in one ring (class Q_q)", where q = 4 and n is the hydrogen content (i.e., we count certain isomers of C_{n+2*q} H_n with q = 4 and n >= 0). (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

From Vladimir Shevelev, Apr 23 2011: (Start)

Also number of non-equivalent (turnover) necklaces of 6 beads each of them painted by one of n colors.

The sequence solves the so-called Reis problem about convex k-gons in case k=6 (see our comment to A032279).

(End)

Also number of reverse invariant anonymous and neutral equivalence classes of preference profiles with 3 alternatives and (n-6) agents (IANC model). - Alexander Karpov, Apr 12 2018

Also the number of weighted cubic graphs with weight n derived from one of the 2 cubic graphs on 6 vertices (contributing to A321306). - R. J. Mathar, Nov 05 2018

Also number of rooted planar general trees (of n vertices or n-1 edges) up to reflection. - Antti Karttunen, Aug 09 2002 (For the correspondence with bracelets, start by considering Raney's lemma as explained by Graham, Knuth & Patashnik.)

Number of connected lattice path matroids on n elements up to isomorphism.

a(n) = number of noncrossing set partitions of [n] up to reflection (i<->n+1-i). Example: a(4) counts 123, 1-23, 13-2, 1-2-3 but not 12-3 because it is the reflection of 1-23. - David Callan, Oct 08 2005

From Vladimir Shevelev, Apr 23 2011: (Start)

Also number of non-equivalent necklaces of n beads, each of which is painted by one of 2*n-1 colors.

The sequence solves the so-called Reis problem about convex k-gons in case N=2*n-1, k=n. H. Gupta (1979) gave a full solution; I gave a short proof of Gupta's result and showed an equivalence of this problem and each of the following problems: the problem of enumerating the bracelets of n beads of 2 colors, k of them black, and the problem of enumerating the necklaces of k beads, each painted by one of n colors.

a(n) is an essentially unimprovable upper estimate for the number of distinct values of the permanent in (0,1)-circulants of order 2*n-1 with n 1's in every row. (End)

The number of Dyck paths of semilength n-1 up to reversal; that is, the number of Dyck paths of semilength n-1, treating as identical a path and that path when traveled in reverse order. - Noah A Rosenberg, Jan 28 2019

From Vladimir Shevelev, Apr 23 2011: (Start)

Also number of non-equivalent necklaces of 5 beads each of them painted by one of n colors.

The sequence solves the so-called Reis problem about convex k-gons in case k=5. The full solution was given by H. Gupta (1979); I gave a short proof of Gupta's result and showed an equivalence of this problem and every one of the following problems: enumerating the bracelets of n beads of 2 colors, k of them black, and enumerating the necklaces of k beads each of them painted by one of n colors.

a(n) is an essentially unimprovable upper estimate for the number of distinct values of the permanent in (0,1)-circulants of order n with five 1's in every row. (End)

a(n+5) is the number of symmetry-allowed, linearly-independent terms at n-th order in the series expansion of the T_1 X h vibronic perturbation matrix, H(Q) (cf. Dunn & Bates). - Bradley Klee, Jul 20 2015

From Petros Hadjicostas, Jul 17 2018: (Start)

Let (c(n): n >= 1) be a sequence of nonnegative integers and let C(x) = Sum_{n>=1} c(n)*x^n be its g.f. Let k be a positive integer. Let a_k = (a_k(n): n >= 1) be the output sequence of the DIK[k] transform of sequence (c(n): n >= 1), and let A_k(x) = Sum_{n>=1} a_k(n)*x^n be its g.f. See Christian G. Bower's web link below. It can be proved that, when k is odd, A_k(x) = ((1/k)*Sum_{d|k} phi(d)*C(x^d)^(k/d) + C(x^2)^((k-1)/2)*C(x))/2.

For this sequence, k = 5, c(n) = 1 for all n >= 1, and C(x) = x/(1-x). Thus, a(n) = a_5(n) for all n >= 1. Since a_k(n) = 0 for 1 <= n <= k-1, the offset of this sequence is n = k = 5. Applying the formula for the g.f. of DIK[5] of (c(n): n >= 1) with C(x) = x/(1-x) and k = 5, we get A(x) = A_5(x) = x^5*((1/5)*Sum_{d|5} phi(d)*(1-x^d)^(-5/d) + (1+x)/(1-x^2)^3)/2, which obviously equals the g.f. in the formula section below.

The g.f. is also a special case of Herbert Kociemba's formula that is valid for both even and odd k: A_k(x) = x^k*((1/k)*Sum_{d|k} phi(d)*(1-x^d)^(-k/d) + (1+x)/(1-x^2)^Floor[(k+2)/2])/2.

Here, a(n) is defined to be the number of n-bead bracelets of two colors with 5 black beads and n-5 white beads. But it is also the number of dihedral compositions of n with 5 positive parts. (This statement is equivalent to Vladimir Shevelev's statement above that a(n) is the "number of non-equivalent necklaces of 5 beads each of them painted by one of n colors." By "necklaces" he means "turnover necklaces". See paragraph (2) of Section 2 in his 2004 paper in the Indian Journal of Pure and Applied Mathematics.)

Two cyclic compositions of n (with k = 5 parts) belong to the same equivalence class corresponding to a dihedral composition of n if and only if one can be obtained from the other by a rotation or reversal of order. (End)