

A308817


Total number of parts in all mcolor 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. 301304).
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 socalled "mcolor" compositions. mcolor linear compositions were studied by Agarwal (2000), whereas mcolor 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 mcolor 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, ncolour compositions, Indian J. Pure Appl. Math. 31 (11) (2000), 14211427.
C. G. Bower, Transforms (2).
Petros Hadjicostas, Generalized colored circular palindromic compositions, Moscow Journal of Combinatorics and Number Theory, 9(2) (2020), 173186.
Meghann Moriah Gibson, Combinatorics of compositions, Master of Science, Georgia Southern University, 2017.
Meghann Moriah Gibson, Daniel Gray, and Hua Wang, Combinatorics of ncolor compositions, Discrete Mathematics 341 (2018), 32093226.
Arnold Knopfmacher and Neville Robbins, Some properties of dihedral compositions, Util. Math. 92 (2013), 207220.
D. M. Y. Sommerville, On certain periodic properties of cyclic compositions of numbers, Proc. London Math. Soc. S27(1) (1909), 263313.


FORMULA

a(n) = (A307415(n) + A308723(n))/2 for n >= 1.
a(n) = (n/10) * (11*F(n) + 7*F(n1)) + (1)^n * (n/10) * (4*F(n) + 7*F(n1))  (1/5) * (5*F(n+1) + 3*F(n))  (1)^n * (1/5) * (3*F(n)  5*F(n1)) + (1/2) * Sum_{sn} 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 mcolor 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 mcolor 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 mcolor 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 mcolor 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



