|
%I #57 Aug 09 2020 17:08:10
%S 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,
%T 28,36,75,64,54,16,1,9,36,49,126,125,160,81,24,1,10,45,64,196,216,375,
%U 256,162,32,1,11,55,81,288,343,756,625,640,243,48,1
%N Array read by antidiagonals: T(n,k) = number of necklaces with n beads and k colors that are the same when turned over.
%C Number of periodic palindromes of length n using a maximum of k different symbols.
%C From _Petros Hadjicostas_, Sep 02 2018: (Start)
%C 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).
%C 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.
%C 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.
%C 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.)
%C 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)
%D 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]
%H Andrew Howroyd, <a href="/A284855/b284855.txt">Table of n, a(n) for n = 1..1275</a>
%H Christian G. Bower, <a href="/transforms2.html">Transforms (2)</a>.
%H Petros Hadjicostas, <a href="https://doi.org/10.2140/moscow.2020.9.173">Generalized colored circular palindromic compositions</a>, Moscow Journal of Combinatorics and Number Theory, 9(2) (2020), 173-186.
%H D. M. Y. Sommerville, <a href="https://doi.org/10.1112/plms/s2-7.1.263">On certain periodic properties of cyclic compositions of numbers</a>, Proc. London Math. Soc. S2-7(1) (1909), 263-313.
%F T(2*n, k) = (k^(n+1) + k^n) / 2.
%F T(2*n + 1, k) = k^(n+1).
%F T(n, k) = 2 * A081720(n, k) - A075195(n, k).
%F From _Petros Hadjicostas_, Sep 02 2018: (Start)
%F 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, ...
%F 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)
%e Table starts:
%e 1 2 3 4 5 6 7 8 9 10 ...
%e 1 3 6 10 15 21 28 36 45 55 ...
%e 1 4 9 16 25 36 49 64 81 100 ...
%e 1 6 18 40 75 126 196 288 405 550 ...
%e 1 8 27 64 125 216 343 512 729 1000 ...
%e 1 12 54 160 375 756 1372 2304 3645 5500 ...
%e 1 16 81 256 625 1296 2401 4096 6561 10000 ...
%e 1 24 162 640 1875 4536 9604 18432 32805 55000 ...
%e 1 32 243 1024 3125 7776 16807 32768 59049 100000 ...
%e 1 48 486 2560 9375 27216 67228 147456 295245 550000 ...
%e ...
%e 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.
%e 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
%t a[n_, k_] := If[EvenQ[n], (k^(n/2) + k^(n/2 + 1))/2, k^((n+1)/2)];
%t Table[a[n-k+1, k], {n, 1, 11}, {k, n, 1, -1}] // Flatten (* _Jean-François Alcover_, Jun 05 2017, translated from PARI *)
%o (PARI)
%o a(n,k) = if(n % 2 == 0, (k^(n/2) + k^(n/2+1))/2, k^((n+1)/2));
%o for(n=1, 10, for(k=1, 10, print1( a(n,k),", ");); print(););
%Y Columns 2-6 are A164090, A182751(n-1), A056486, A056487(n-1), A056488.
%Y Cf. A037306, A081720, A075195, A119963, A284856, A277504.
%K nonn,tabl
%O 1,2
%A _Andrew Howroyd_, Apr 04 2017
|
