A032189 - OEIS

%I #44 Sep 23 2023 15:17:07

%S 1,1,2,2,3,4,5,7,10,14,19,30,41,63,94,142,211,328,493,765,1170,1810,

%T 2787,4340,6713,10461,16274,25414,39651,62074,97109,152287,238838,

%U 375166,589527,927554,1459961,2300347,3626242,5721044,9030451,14264308,22542397,35646311,56393862,89264834,141358275

%N Number of ways to partition n elements into pie slices each with an odd number of elements.

%C a(n) is also the total number of cyclic compositions of n into odd parts assuming that two compositions are equivalent if one can be obtained from the other by a cyclic shift. For example, a(5)=3 because 5 has the following three cyclic compositions into odd parts: 5, 1+3+1, 1+1+1+1+1. - _Petros Hadjicostas_, Dec 27 2016

%H C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>

%H P. Flajolet and M. Soria, <a href="http://algo.inria.fr/flajolet/Publications/publist.html">The Cycle Construction</a> In SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.

%H Petros Hadjicostas, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Hadjicostas/hadji2.html">Cyclic compositions of a positive integer with parts avoiding an arithmetic sequence</a>, Journal of Integer Sequences, 19 (2016), Article 16.8.2.

%H Silvana Ramaj, <a href="https://digitalcommons.georgiasouthern.edu/etd/2273">New Results on Cyclic Compositions and Multicompositions</a>, Master's Thesis, Georgia Southern Univ., 2021.

%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>

%F a(n) = A000358(n)-(1+(-1)^n)/2.

%F "CIK" (necklace, indistinct, unlabeled) transform of 1, 0, 1, 0...(odds)

%F G.f.: Sum_{k>=1} phi(k)/k * log( 1/(1-B(x^k)) ) where B(x) = x/(1-x^2). [_Joerg Arndt_, Aug 06 2012]

%F a(n) = (1/n)*Sum_{d divides n} phi(n/d)*A001350(d). - _Petros Hadjicostas_, Dec 27 2016

%t a1350[n_] := Sum[Binomial[k - 1, 2k - n] n/(n - k), {k, 0, n - 1}];

%t a[n_] := 1/n Sum[EulerPhi[n/d] a1350[d], {d, Divisors[n]}];

%t Array[a, 50] (* _Jean-François Alcover_, Jul 29 2018, after _Petros Hadjicostas_ *)

%o (PARI)

%o N=66;  x='x+O('x^N);

%o B(x)=x/(1-x^2);

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

%o Vec(A)

%o /* _Joerg Arndt_, Aug 06 2012 */

%o (Python)

%o from sympy import totient, lucas, divisors

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

%Y Cf. A000358, A001350, A008965.

%K nonn

%O 1,3

%A _Christian G. Bower_