cp's OEIS Frontend

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

%I A365859 #40 Mar 31 2025 15:20:53
%S A365859 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,
%T A365859 41,16274,5,39651,94,97109,1,238838,211,589527,10,1459961,493,3626242,
%U A365859 3,9030451,1170,22542397,19,56393862,2787,141358275,2,354975433,6713,892893262,41,2249412291,16274,5674891017
%N A365859 Number of self-dual cyclic n-color compositions.
%C A365859 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.
%C A365859 a(n) is also the number of cyclic compositions of A000265(n) into odd parts.
%C A365859 This sequence is self-similar; removing all odd-indexed terms results in the same sequence.
%H A365859 A. K. Agarwal, <a href="https://www.insa.nic.in/writereaddata/UpLoadedFiles/IJPAM/20005b15_1421.pdf">n-colour compositions</a>, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.
%H A365859 Joshua P. Bowman, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL27/Bowman/bowman4.html">Compositions with an Odd Number of Parts, and Other Congruences</a>, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 33.
%H A365859 Meghann Moriah Gibson, Daniel Gray, and Hua Wang, <a href="https://doi.org/10.1016/j.disc.2018.08.001">Combinatorics of n-color cyclic compositions</a>, Discrete Mathematics 341 (2018), 3209-3226.
%H A365859 Brian Hopkins, Jesús Sistos Barrón, and Hua Wang, <a href="https://doi.org/10.61091/um122-04">Conjugating cyclic n-color compositions</a>, Utilitas Mathematica (2025) Vol. 122, 53-64. See p. 61.
%H A365859 Jesus Omar Sistos Barron, <a href="https://digitalcommons.georgiasouthern.edu/honors-theses/985">Counting Conjugates of Colored Compositions</a>, Honors College Thesis, Georgia Southern Univ. (2024), No. 985. See p. 25.
%F A365859 G.f.: Sum_{k>=1} phi(2*k)/(2*k) * log((1+x^k-x^(2*k))/(1-x^k-x^(2*k))).
%F A365859 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).
%F A365859 a(n) = 2*A365857(n) - A032198(n).
%e A365859 Every power of 2 has only one self-dual cyclic n-color composition, which has all parts of size 1.
%e A365859 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.
%o A365859 (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
%o A365859 (Python)
%o A365859 from sympy import totient, lucas, divisors
%o A365859 def A365859(n):
%o A365859     m = n>>(~n&n-1).bit_length()
%o A365859     return sum(totient(k)*lucas(m//k) for k in divisors(m,generator=True))//m # _Chai Wah Wu_, Sep 23 2023
%Y A365859 Cf. A000204 (Lucas), A000265, A032189, A032198, A365857, A365858.
%K A365859 nonn
%O A365859 1,3
%A A365859 _Joshua P. Bowman_, Sep 20 2023