login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A284855 Array read by antidiagonals: T(n,k) = number of necklaces with n beads and k colors that are the same when turned over. 11
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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)

REFERENCES

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

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..1275

C. G. Bower, Transforms (2)

D. M. Y. Sommerville, On certain periodic properties of cyclic compositions of numbers, Proc. London Math. Soc. S2-7(1) (1909), 263-313.

FORMULA

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

T(2n + 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)

EXAMPLE

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

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 *)

PROG

(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(); );

CROSSREFS

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

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

Sequence in context: A057145 A134394 A322967 * A074909 A135278 A034356

Adjacent sequences:  A284852 A284853 A284854 * A284856 A284857 A284858

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Apr 04 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 18 22:03 EDT 2019. Contains 328211 sequences. (Running on oeis4.)