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,3

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

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

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

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

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 *)

Prog

(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

Crossrefs

Cf. A000358, A001350, A008965.

Sequence in context: A136422 A173674 A018128 * A316077 A186425 A327662

Adjacent sequences: A032186 A032187 A032188 * A032190 A032191 A032192

Keyword

nonn

Author

Christian G. Bower

Status

approved