login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A308817 Total number of parts in all m-color dihedral compositions of n (that is, the total number of parts in all dihedral compositions of n where a part of size m may be colored with one of m colors). 0
1, 4, 10, 26, 56, 138, 299, 726, 1686, 4158, 10130, 25678, 64725, 166538, 428456, 1112226, 2888604, 7533750, 19653903, 51367462, 134277878, 351284164, 919080550, 2405427698, 6295780309, 16480373968, 43141303978, 112939105716, 295664584064, 774042041090, 2026429360115, 5305210333758 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Cyclic compositions of a positive integer n are equivalence classes of ordered partitions of n such that two such partitions are equivalent iff one can be obtained from the other by rotation. These were first studied by Sommerville (1909).

Symmetric cyclic compositions or circular palindromes or achiral cyclic compositions are those cyclic compositions that have at least one axis of symmetry. They were also studied by Sommerville (1909, pp. 301-304).

Dihedral compositions of a positive integer n are equivalence classes of ordered partitions of n such that two such partitions are equivalent iff one can be obtained from the other by rotation or reflection. See, for example, Knopfmacher and Robbins (2013).

The number of dihedral compositions of n (of any kind) is the average of the corresponding numbers of cyclic and symmetric cyclic compositions of n.

Let c = (c(m): m >= 1) be the input sequence and let b_k = (b_k(n): n >= 1) be the output sequence under Bower's DIK[k] ("bracelet, indistinct, unlabeled" with k boxes) transform of c; that is, b_k(n) = (DIK[k] c)_n for n >= 1. Hence, b_k(n) is the number of dihedral compositions of n with k parts, where a part of size m can be colored with one of c(m) colors. If C(x) = Sum_{m >= 1} c(m)*x^m is the g.f. of the input sequence c, then the bivariate g.f. of the list of sequences (b_k: k >= 1) = ((DIK[k] c): k >= 1) = ((b_k(n): n >= 1): k >= 1) is Sum_{n,k >= 1} b_k(n)*x^n*y^k = (1 + y * C(x))^2/(4 * (1 - y^2 * C(x^2))) - (1/4) - (1/2) * Sum_{d >= 1} (phi(d)/d) * log(1 - y^d * C(x^d)).

Here, Sum_{k=1..n} k*b_k(n) is the total number of parts in all colored dihedral compositions of n (where the coloring of parts is done according to the input sequence c). To find the g.f. of the sequence (Sum_{k=1..n} k*b_k(n): n >= 1), we differentiate the above bivariate g.f. (i.e., Sum_{n,k >= 1} b_k(n)*x^n*y^k) w.r.t. y and set y = 1. We get (1 + C(x)) * (C(x) + C(x^2))/(2 * (1 - C(x^2))^2) + (1/2) * Sum_{d >= 1} phi(d) * C(x^d)/(1 - C(x^d)).

For the current sequence, the input sequence is c(m) = m for m >= 1, and we are dealing with the so-called "m-color" compositions. m-color linear compositions were studied by Agarwal (2000), whereas m-color cyclic compositions were studied by Gibson (2017) and Gibson et al. (2018).

Thus, for the current sequence, a(n) is the total number of parts in all m-color dihedral compositions of n (where a part of size m may be colored with one of m colors). Since C(x) = x/(1 - x)^2, we get that (1 + C(x)) * (C(x) + C(x^2))/(2 * (1 - C(x^2))^2) + (1/2) * Sum_{d >= 1} phi(d) * C(x^d)/(1 - C(x^d))  = (1/2) * (x^2 - x + 1) * x * (x^2 + 3*x + 1) * (x + 1)^2/((x^2 + x - 1)^2 * (x^2 - x - 1)^2) + (1/2) * Sum_{s >= 1} phi(s) * x^s/(1 - 3*x^s + x^(2*s)).

LINKS

Table of n, a(n) for n=1..32.

A. K. Agarwal, n-colour compositions, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.

C. G. Bower, Transforms (2).

Petros Hadjicostas, Generalized colored circular palindromic compositions, Moscow Journal of Combinatorics and Number Theory, 9(2) (2020), 173-186.

Meghann Moriah Gibson, Combinatorics of compositions, Master of Science, Georgia Southern University, 2017.

Meghann Moriah Gibson, Daniel Gray, and Hua Wang, Combinatorics of n-color compositions, Discrete Mathematics 341 (2018), 3209-3226.

Arnold Knopfmacher and Neville Robbins, Some properties of dihedral compositions, Util. Math. 92 (2013), 207-220.

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

FORMULA

a(n) = (A307415(n) + A308723(n))/2 for n >= 1.

a(n) = (n/10) * (11*F(n) + 7*F(n-1)) + (-1)^n * (n/10) * (-4*F(n) + 7*F(n-1)) - (1/5) * (5*F(n+1) + 3*F(n)) - (-1)^n * (1/5) * (3*F(n) - 5*F(n-1)) + (1/2) * Sum_{s|n} phi(n/s) * F(2*s) for n >= 1, where F(n) = A000045(n) (Fibonacci numbers).

G.f.: (1/2) * (x^2 - x + 1) * x * (x^2 + 3*x + 1) * (x + 1)^2/((x^2 + x - 1)^2 * (x^2 - x - 1)^2) + (1/2) * Sum_{s >= 1} phi(s) * x^s/(1 - 3*x^s + x^(2*s)).

EXAMPLE

We have a(1) = 1 because 1_1 is the only m-color dihedral composition of n = 1 and the total number of parts is 1.

We have a(2) = 4 because 2_1, 2_2, 1_1 + 1_1 are all the m-color dihedral compositions of 2 and the total number of parts is 1 + 1 + 2 = 4.

We have a(3) = 10 because 3_1, 3_2, 3_3, 1_1 + 2_1, 1_1 + 2_2, 1_1 + 1_1 + 1_1 are all the m-color dihedral compositions of n = 3 and the total number of parts is 1 + 1 + 1 + 2 + 2 + 3 = 10.

We have a(4) = 26 because 4_1, 4_2, 4_3, 4_4, 1_1 + 3_1, 1_1 + 3_2, 1_1 + 3_3, 2_1 + 2_1, 2_1 + 2_2, 2_2 + 2_2, 1_1 + 2_1 + 1_1, 1_1 + 2_2 + 1_1, 1_1 + 1_1 + 1_1 + 1_1 are all the m-color dihedral compositions of n = 4 and the total number of parts is 1 + 1 + 1 + 1 + 2 + 2 + 2 + 2 + 2 + 2 + 3 + 3 + 4 = 26.

Note that a(n) = A307415(n) = A308723(n) for n = 1, 2, 3, 4 because all cyclic compositions of n when 1 <= n <= 4 are symmetric as well (and thus are dihedral).

For n = 5, we have A307415(5) = 53 <> 59 = A308723(5), in which case, a(n) = (53 + 59)/2 = 56. For example, 1_1 + 2_1 + 3_1 is a dihedral composition of n = 5, but it is not symmetric, so it corresponds to two (inequivalent) cyclic compositions: 1_1 + 2_1 + 3_1 and 3_1 + 2_1 + 1_1. Similarly, 1_1 + 2_1 + 2_2 is a dihedral composition of n = 5, but it not symmetric, so it corresponds to two (inequivalent) cyclic compositions: 1_1 + 2_1 + 2_2 and 2_2 + 2_1 + 1_1.

CROSSREFS

Cf. A000045, A030267, A032198, A032287, A088305, A307415, A308723.

Sequence in context: A022812 A192306 A276432 * A000293 A000294 A308723

Adjacent sequences:  A308814 A308815 A308816 * A308818 A308819 A308820

KEYWORD

nonn

AUTHOR

Petros Hadjicostas, Jun 26 2019

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 April 15 20:40 EDT 2021. Contains 342977 sequences. (Running on oeis4.)