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

1, 1, 2, 2, 3, 4, 5, 7, 10, 14, 19, 30, 41, 63, 94, 142, 211, 328, 493, 765, 1170, 1810, 2787, 4340, 6713, 10461, 16274, 25414, 39651, 62074, 97109, 152287, 238838, 375166, 589527, 927554, 1459961, 2300347, 3626242, 5721044, 9030451, 14264308, 22542397, 35646311, 56393862, 89264834, 141358275

Offset: 1

Author

Christian G. Bower

Keywords

• nonn

Comments

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

Links

• C. G. Bower, Transforms (2)
• P. Flajolet and M. Soria, The Cycle Construction In SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
• Petros Hadjicostas, Cyclic compositions of a positive integer with parts avoiding an arithmetic sequence, Journal of Integer Sequences, 19 (2016), Article 16.8.2.
• Silvana Ramaj, New Results on Cyclic Compositions and Multicompositions, Master's Thesis, Georgia Southern Univ., 2021.
• Index entries for sequences related to necklaces

Crossrefs

Cf. A000358, A001350, A008965.

Programs

Mathematica

a1350[n_] := Sum[Binomial[k - 1, 2k - n] n/(n - k), {k, 0, n - 1}];
a[n_] := 1/n Sum[EulerPhi[n/d] a1350[d], {d, Divisors[n]}];
Array[a, 50] (* Jean-François Alcover, Jul 29 2018, after Petros Hadjicostas *)

PARI

N=66;  x='x+O('x^N);
B(x)=x/(1-x^2);
A=sum(k=1,N,eulerphi(k)/k*log(1/(1-B(x^k))));
Vec(A)
/* Joerg Arndt, Aug 06 2012 */

Python

from sympy import totient, lucas, divisors
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

Formula

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

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

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]

a(n) = (1/n)*Sum_{d divides n} phi(n/d)*A001350(d). - Petros Hadjicostas, Dec 27 2016