cp's OEIS Frontend

From John P. McSorley, Aug 24 2010: (Start)

A combinatorial interpretation of this triangle is as follows:

Ignore the first column of 1's of the above triangle and the call the (n,k) entry of the new triangle formed RE(n,k).

Hence row 8 of the 'RE(n,k)' triangle is 1 4 3 6 3 4 1 1.

Now see sequence A180171 for the definition of a k-reverse of n.

Briefly, a k-reverse of n is a k-composition of n which is cyclically equivalent to its reverse.

Sequence A180171 is the 'R(n,k)' triangle read by rows where R(n,k) is the total number of k-reverses of n.

Then RE(n,k) is the number of k-reverses of n up to cyclic equivalence.

In sequence A180171 we have R(8,3)=9 because there are 9 3-reverses of 8.

In cyclically equivalent classes: {116,611,161} {224,422,242}, and {233,323,332}; since there are 3 such classes we have RE(8,3)=3.

Similarly, in A180171, we have R(8,6)=21 because all 21 6-compositions of 8 are 6-reverses of 8, but they come in 4 cyclically equivalent classes (with representatives 111113, 111122, 111212, and 112112) hence RE(8,6)=4.

There is another (equivalent) interpretation for RE(n,k) involving k-subsets of Z_n, the integers modulo n, and the multiplier -1. See the McSorley/Schoen paper below for more details.

In this case it is convenient to count k-subsets up to dihedral equivalence, rather than cyclic equivalence.

The counts are the same. The row sums of the 'RE(n,k)' triangle give sequence A052955.

(End)

From Petros Hadjicostas, Oct 12 2017: (Start)

When 1 <= k <= n, each cyclically equivalence class of k-reverses of n is a "Sommerville symmetrical cyclic composition," which was introduced by Sommerville (1909). On pp. 301-304 of his paper, he proves that the number of such (equivalence classes of) compositions of n with length k is exactly T(n,k) = RE(n,k).

The equivalence class of a Sommerville symmetrical cyclic composition contains at least one palindromic composition (type I) or a composition that becomes a palindromic composition if we remove the first part (type II). A composition with only one part is a palindromic composition of both types. Hadjicostas and Zhang (2017) have proved that each equivalence class of k-reverses of n contains exactly two compositions that are either of type I or type II (except in the case when k | n and all the parts are the same).

For example, consider the case with n=8 and k=3, where RE(8,3)=3. As pointed above by J. P. McSorley, in cyclically equivalent classes we have {116,611,161} {224,422,242}, and {233,323,332}. The first class contains one composition of type I (161) and one of type II (611); the second class contains one composition of type I (242) and one of type II (422); and the last class contains one composition of type I (323) and one of type II (233).

When n = 6 and k = 4, the class of 4-reverses {1221, 2211, 2112, 1122} contains two compositions of type I (1221 and 2112).

If A is a set of positive integers and 1 <= k <= n, let RE_A(n,k) be the total number of Sommerville symmetrical cyclic compositions of n with length k and parts only in A (= number of cyclically equivalence classes of k-reverses of n with parts only in A). Then the g.f. of RE_A(n,k) is Sum_{n,k >= 1} RE_A(n,k) * x^n * y^k = (-1/2) + (1 + y * f_A(x))^2/(2 * (1 - y^2 * f_A(x^2)), where f_A(x) = Sum_{m in A} x^m. (For this sequence, A = all positive integers.)

Sequence A292200 contains the total number of Sommerville symmetrical cyclic compositions of n that are Carlitz (compositions that have length one, or have length >= 1 and adjacent parts of the composition on a circle are distinct).

(End)

This is a corrected version of the entries in sequence A210769, which is copied from the third row of Table 2 (p. 381) in Williamson (1972). Apparently, in that row, there are probable typographical errors for the values of a(4) and a(7). The formula for a(n) can be obtained by letting z_1=z_2=...=z_8=n in equation (24) on p. 377 in Williamson (1972). In any case, to be certain, we provide a sketch of an independent derivation of the formula.

Bilaterally symmetric bracelets are also known as circular palindromes. This kind of necklaces was first studied by Sommerville (1909) in the context of circular compositions.

Consider sequence A081720, which contains the numbers T(n,k) that are the number of bracelets (turn over necklaces) with n beads each of which is colored with one of k colors. The g.f. for column k of that triangle is (1/2)*((k*x+k*(k+1)*x^2/2)/(1-k*x^2) - Sum_{n>=1} (phi(n)/n)*log(1-k*x^n)). The part of the g.f. that is the number of bilaterally symmetric bracelets with n beads of k colors is (k*x+k*(k+1)*x^2/2)/(1-k*x^2). Thus, for fixed k (= number of colors for sequence A081720), the g.f. of the number of bilaterally asymmetric bracelets with n beads of k colors is the difference between the two g.f.'s, that is, (1/2)*(-(k*x+k*(k+1)*x^2/2)/(1-k*x^2) - Sum_{n>=1} (phi(n)/n)*log(1-k*x^n)). The coefficient of x^8 in the Taylor expansion w.r.t. x (around x=0) for the latter g.f. gives the number of bilaterally asymmetric 8-hoops obtained using (up to) k symbols. Taking the 8th derivative w.r.t. x of the last g.f., evaluating at x=0, dividing by 8!, and replacing k with n, we get the formulae given below.

A cyclic Carlitz composition is a composition of length greater than one where adjacent parts, including the first and the last ones, are distinct. A composition of length one is also considered cyclic and Carlitz. Assume two cyclic Carlitz compositions are considered equivalent iff one can be obtained from the other by a rotation or reversal of order. Each equivalence class obtained is called a dihedral Carlitz composition of n.

Bracelets that have no reflection symmetry are also known as chiral bracelets.

Here, for n >= 6, a(n) is also the number of dihedral compositions of n with 6 parts that have no reflection symmetry. Taking the MacMahon conjugates of these dihedral compositions, we see that a(n) is also the number of dihedral compositions of n into n-6 parts that have no reflection symmetry.

A cyclic composition b_1 + b_2 + ... + b_k of n into k parts is an equivalent class of (linear) compositions of n into k parts (placed on a circle) such that two such (linear) compositions are equivalent iff one can be obtained from the other by a rotation. Such compositions were first studied extensively by Sommerville (1909).

A dihedral composition b_1 + b_2 + ... + b_k of n into k parts is an equivalent class of (linear) compositions of n into k parts (placed on a circle) such that two such (linear) compositions are equivalent iff one can be obtained from the other by a rotation or a reversal of order. Such compositions were studied, for example, by Knopfmacher and Robbins (2013).

Given a bracelet of length n with k white beads and n-k black beads, we may get the corresponding dihedral composition using MacMahon's correspondence: start with a white bead and count that bead and the black beads that follow (in one direction), and call that b_1; then start with the next white bead and count that one and the black beads that follow, and call that b_2; repeat this process until you reach the k-th white bead and count that one and the black beads that follow, and call that b_k. The corresponding dihedral composition is b_1 + b_2 + ... + b_k.

If in the previous paragraph (given a bracelet of length n with k white beads and n-k black beads), we replace the white beads with black beads and the black beads with white beads, we get a dihedral composition of n into n-k parts: c_1 + c_2 + ... + c_{n-k}. These two dihedral compositions (which correspond to the same bracelet) are called "conjugate" compositions. See p. 273 in Sommerville (1909) for an explanation of "conjugate" compositions in the context of cyclic compositions.

Symmetric cyclic compositions of a positive integer n were first studied by Sommerville (1909, pp. 301-304). It can be proved that the study of necklaces with reflection symmetry using beads of two colors is equivalent to the study of symmetric cyclic compositions of a positive integer. Clearly all the necklaces with reflection symmetry are all the bracelets (turnover necklaces) with reflection symmetry. See also the comments for sequences A119963, A292200, and A295925.