A284855 Array read by antidiagonals: T(n,k) = number of necklaces with n beads and k colors that are the same when turned over.

1, 2, 1, 3, 3, 1, 4, 6, 4, 1, 5, 10, 9, 6, 1, 6, 15, 16, 18, 8, 1, 7, 21, 25, 40, 27, 12, 1, 8, 28, 36, 75, 64, 54, 16, 1, 9, 36, 49, 126, 125, 160, 81, 24, 1, 10, 45, 64, 196, 216, 375, 256, 162, 32, 1, 11, 55, 81, 288, 343, 756, 625, 640, 243, 48, 1

Offset: 1

Author

Andrew Howroyd, Apr 04 2017

Keywords

• nonn
• tabl

Comments

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)

Examples

			Table starts:
1  2   3    4    5     6     7      8      9     10 ...
1  3   6   10   15    21    28     36     45     55 ...
1  4   9   16   25    36    49     64     81    100 ...
1  6  18   40   75   126   196    288    405    550 ...
1  8  27   64  125   216   343    512    729   1000 ...
1 12  54  160  375   756  1372   2304   3645   5500 ...
1 16  81  256  625  1296  2401   4096   6561  10000 ...
1 24 162  640 1875  4536  9604  18432  32805  55000 ...
1 32 243 1024 3125  7776 16807  32768  59049 100000 ...
1 48 486 2560 9375 27216 67228 147456 295245 550000 ...
...
For n = 4 and k = 2, the palindromic necklaces are 0000, 0001, 0011, 0111, 0101, 1111 so T(4,2) = 6. Necklaces are only counted up to cyclic equivalence.
For n = 4 and k = 2, using MacMahon's bijection, with B = 0 and W = 1, the corresponding Sommerville symmetrical cyclic compositions of n = 4 are as follows: 1+1+1+1, 1+1+2, 1+3, 4, 2+2 (with none for 1111). If we let B = 1 and W = 0, we get the corresponding symmetrical cyclic compositions of n=4: (none for 0000) 4, 1+3, 1+1+2, 2+2, 1+1+1+1. (All these cyclic compositions must viewed on a circle.) - _Petros Hadjicostas_, Sep 02 2018
		

References

• M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for the pdf file of Chap. 2]

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1275
• Christian G. Bower, Transforms (2).
• Petros Hadjicostas, Generalized colored circular palindromic compositions, Moscow Journal of Combinatorics and Number Theory, 9(2) (2020), 173-186.
• D. M. Y. Sommerville, On certain periodic properties of cyclic compositions of numbers, Proc. London Math. Soc. S2-7(1) (1909), 263-313.

Crossrefs

Columns 2-6 are A164090, A182751(n-1), A056486, A056487(n-1), A056488.

Cf. A037306, A081720, A075195, A119963, A284856, A277504.

Programs

Mathematica

a[n_, k_] := If[EvenQ[n], (k^(n/2) + k^(n/2 + 1))/2, k^((n+1)/2)];
Table[a[n-k+1, k], {n, 1, 11}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jun 05 2017, translated from PARI *)

PARI

a(n,k) = if(n % 2 == 0, (k^(n/2) + k^(n/2+1))/2, k^((n+1)/2));
for(n=1, 10, for(k=1, 10, print1( a(n,k),", ");); print(););

Formula

T(2*n, k) = (k^(n+1) + k^n) / 2.

T(2*n + 1, k) = k^(n+1).

T(n, k) = 2 * A081720(n, k) - A075195(n, k).

From Petros Hadjicostas, Sep 02 2018: (Start)

For fixed k >= 1, the k-th column (T(n, k): n >= 1) is the CPAL ("circular palindrome") transform of the sequence k, 0, 0, ...

G.f. of column k: Sum_{n>=1} T(n,k)*x^n = (1 + k*x)^2/(2*(1 - k*x^2)) - 1/2. (End)