login
Number of cyclic compositions of 2*n-1 into odd parts.
3

%I #29 Apr 25 2024 10:47:31

%S 1,2,3,5,10,19,41,94,211,493,1170,2787,6713,16274,39651,97109,238838,

%T 589527,1459961,3626242,9030451,22542397,56393862,141358275,354975433,

%U 892893262,2249412291,5674891017,14335757586,36259245523,91815545801,232745229290,590586152235,1500020153485,3813274653414

%N Number of cyclic compositions of 2*n-1 into odd parts.

%C Odd bisection of A032189.

%C Also the number of cyclic compositions into an odd number of odd parts; because such a sum must be odd, alternating terms are zero and have been removed.

%H 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. 25.

%H 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. 30.

%F G.f.: (1/2) * Sum_{k odd} (phi(k)/k)*log((1+x^k-x^(2k))/(1-x^k-x^(2*k))), where phi(n) = A000010(n).

%F a(n) = (1/(2*n-1)) * Sum_{k divides 2n-1} phi(k)*A000204((2*n-1)/k).

%F a(n) ~ ((1+sqrt(5))/2)^(2*n-1) / (2*n). - _Vaclav Kotesovec_, Sep 22 2023

%t Table[1/(2*n - 1) * Sum[EulerPhi[k]*LucasL[(2*n - 1)/k], {k, Divisors[2*n - 1]}], {n, 1, 40}] (* _Vaclav Kotesovec_, Sep 22 2023 *)

%o (PARI)

%o N=99; x='x+O('x^N); B(x)=x/(1-x^2);

%o A=Vec(sum(k=1, N, eulerphi(k)/k*log(1/(1-B(x^k)))));

%o vector(#A\2,n,A[2*n-1]) \\ _Joerg Arndt_, Sep 22 2023

%o (Python)

%o from sympy import totient, lucas, divisors

%o def A365858(n): return sum(totient(((n<<1)-1)//k)*(lucas(k)-((k&1^1)<<1)) for k in divisors((n<<1)-1,generator=True))//((n<<1)-1) # _Chai Wah Wu_, Sep 23 2023

%Y Cf. A000010, A000204 (Lucas), A032189, A365857, A365859.

%K nonn

%O 1,2

%A _Joshua P. Bowman_, Sep 20 2023