A365859 Number of self-dual cyclic n-color compositions.

1, 1, 2, 1, 3, 2, 5, 1, 10, 3, 19, 2, 41, 5, 94, 1, 211, 10, 493, 3, 1170, 19, 2787, 2, 6713, 41, 16274, 5, 39651, 94, 97109, 1, 238838, 211, 589527, 10, 1459961, 493, 3626242, 3, 9030451, 1170, 22542397, 19, 56393862, 2787, 141358275, 2, 354975433, 6713, 892893262, 41, 2249412291, 16274, 5674891017

Offset

1,3

Comments

A cyclic composition is a sum in which the order of the parts is considered up to cyclic permutation. In other words, it is the collection of components remaining in the cycle graph C_n on n vertices when one or more edges are removed, and rotations are considered equivalent. In an n-color composition, each part of size k is assigned one of k "colors" which may be represented graphically by marking one vertex in the part. The dual of a cyclic n-color composition is obtained by switching the roles of edges and vertices in C_n, then removing each edge that came from a previously marked vertex while marking each vertex that came from a previously removed edge. A cyclic n-color composition is self-dual if it is invariant under this process.

a(n) is also the number of cyclic compositions of A000265(n) into odd parts.

This sequence is self-similar; removing all odd-indexed terms results in the same sequence.

Links

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

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

Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 33.

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

Jesus Omar Sistos Barron, Counting Conjugates of Colored Compositions, Honors College Thesis, Georgia Southern Univ. (2024), No. 985. See p. 25.

Formula

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

a(n) = (1/(b(n)))*[Sum_{k divides A000265(n)} phi(k)*lucas(b(n)/k)], where b(n) = A000265(n) and lucas(n) = A000204(n).

a(n) = 2*A365857(n) - A032198(n).

Example

Every power of 2 has only one self-dual cyclic n-color composition, which has all parts of size 1.
The self-dual cyclic n-color compositions of 5 are 1_1+1_1+1_1+1_1+1_1, 1_1+2_2+2_1, and 5_3, where the subscript indicates the color of the part, or which vertex is marked within the part.

Prog

(PARI) my(N=66, x='x+O('x^N)); Vec( sum(k=1, N, eulerphi(2*k)/(2*k) * log((1+x^k-x^(2*k))/(1-x^k-x^(2*k))) ) )  \\ Joerg Arndt, Sep 21 2023
(Python)
from sympy import totient, lucas, divisors
def A365859(n):
    m = n>>(~n&n-1).bit_length()
    return sum(totient(k)*lucas(m//k) for k in divisors(m, generator=True))//m # Chai Wah Wu, Sep 23 2023

Crossrefs

Cf. A000204 (Lucas), A000265, A032189, A032198, A365857, A365858.

Sequence in context: A030067 A181363 A105800 * A105602 A111079 A165006

Adjacent sequences: A365856 A365857 A365858 * A365860 A365861 A365862

Keyword

nonn,changed

Author

Joshua P. Bowman, Sep 20 2023

Status

approved