cp's OEIS Frontend

Number of periodic palindromes of length n using a maximum of k different symbols.

From Petros Hadjicostas, Sep 02 2018: (Start)

According to Christian Bower's theory of transforms, we have boxes of different sizes and different colors. The size of a box is determined by the number of balls it can hold. In this case, we assume all balls are the same and are unlabeled. Assume also that the number of possible colors a box with m balls can have is given by c(m). We place the boxes on a circle at equal distances from each other. Two configurations of boxes on the circle are considered equivalent if one can be obtained from the other by rotation. We are interested about circular configurations of boxes that are circular palindromes (i.e., necklaces with boxes that are the same when turned over). Let b(n) be the number of circularly palindromic configurations of boxes on a circle when the total number of balls in the boxes is n (and each box contains at least one ball).

Bower calls the sequence (b(n): n >= 1), the CPAL ("circular palindrome") transform of the input sequence (c(m): m >= 1). If the g.f. of the input sequence (c(m): m >= 1) is C(x) = Sum_{m>=1} c(m)*x^m, then the g.f. of the output sequence (b(n): n >= 1) is B(x) = Sum_{n >= 1} b(n)*x^n = (1 + C(x))^2/(2*(1 - C(x^2))) - 1/2.

In the current sequence, each box holds only one ball but can have one of k colors. Hence, c(1) = k but c(m) = 0 for m >= 2. Thus, C(x) = k*x. Then, for fixed k, the output sequence is (b(n): n >= 1) = (T(n, k): n >= 1), where T(n, k) = number of necklaces with n beads and k colors that are the same when turned over. If we let B_k(x) = Sum_{n>=1} T(n, k)*x^n, then B_k(x) = (1 + k*x)^2/(2*(1 - k*x^2)) - 1/2. From this, we can easily prove the formulae below.

Note that T(n, k=2) - 1 is the total number of Sommerville symmetric cyclic compositions of n. See pp. 301-304 in his paper in the links below. To see why this is the case, we use MacMahon's method of representing a cyclic composition of n with a necklace of 2 colors (see p. 273 in Sommerville's paper where the two "colors" are an x and a dot . rather than B and W). Given a Sommerville symmetrical composition b_1 + ... + b_r of n (with b_i >= 1 for all i and 1 <= r <= n), create the following circularly palindromic necklace with n beads of 2 colors: Start with a B bead somewhere on the circle and place b_1 - 1 W beads to the right of it; place a B bead to the right of the W beads (if any) followed by b_2 - 1 W beads; and so on. At the end, place a B bead followed with b_r - 1 W beads. (If b_i = 1 for some i, then a B bead follows a B bead since there are 0 W beads between them.) We thus get a circularly palindromic necklace with n beads of two colors. (The only necklace we cannot get with this method is the one than has all n beads colored W.)

It is interesting that the representation of a necklace of length n, say s_1, s_2, ..., s_n, as a periodic sequence (..., s_{-2}, s_{-1}, s_0, s_1, s_2, ...) with the property s_i = s_{i+n} for all i, as was done by Marks R. Nester in Chapter 2 of his 1999 PhD thesis, was considered by Sommerville in his 1909 paper (in the very first paragraph of his paper). (End)

An orientable necklace when turned over does not leave it unchanged. Only one necklace in each pair is included in the count.

The number of chiral bracelets. An achiral bracelet is the same as its reverse, while a chiral bracelet is equivalent to its reverse. - Robert A. Russell, Sep 28 2018

T(n, k) is the number of n-ary necklaces of length k (see Ruskey, Savage and Wang). - Peter Luschny, Aug 12 2012, comment corrected at the suggestion of Petros Hadjicostas, Peter Luschny, Sep 10 2018

From Petros Hadjicostas, Sep 12 2018: (Start)

The programs by Peter Luschny below can generate all n-ary necklaces of length k (and all k-ary necklaces of length n) for any positive integer values of n and k, not just for 1 <= k <= n.

From the examples below, we see that the number of 4-ary necklaces of length 3 equals the number of 3-ary necklaces of length 4. The question is whether there are other pairs (n, k) of distinct positive integers such that the number of n-ary necklaces of length k equals the number of k-ary necklaces of length n.

(End)

T(n,k) is the number of n-bead necklaces with up to k different colored beads. - Yves-Loic Martin, Sep 29 2020

Unlike A075195 and A284855, antidiagonals go from bottom-left to top-right.

For the base case of m=2 the sequence counts circulant digraphs up to Cayley isomorphism. Two circulant graphs are Cayley isomorphic if there is a d, which is necessarily prime to n, that transforms through multiplication modulo n the step values of one graph into those of the other. For squarefree n this is the only way that two circulant graphs can be isomorphic. (See Liskovets reference for a proof.)

Alternatively, the number of mappings with domain {1..n-1} and codomain {1..m} up to equivalence. Mappings A and B are equivalent if there is a d, prime to n, such that A(i) = B(i*d mod n) for i in {1..n-1}. This sequence differs from A132191 only in that sequence also includes 0 in the domain which introduces an extra factor of m into the results since zero multiplied by anything is zero.

All column sequences are polynomials of order n-1 and these are the cycle index polynomials.

This sequence is also related to A075195(n, m) which counts necklaces and A285548(m, n) which is the sequence described in the Titsworth reference. In particular, A075195 is the analogous array with equivalence determined through the additive group instead of by multiplication whereas A285548 allows for both addition and multiplication.