cp's OEIS Frontend

A032190 Number of cyclic compositions of n into parts >= 2.

%I A032190 #77 Jan 05 2025 19:51:35
%S A032190 0,1,1,2,2,4,4,7,9,14,18,30,40,63,93,142,210,328,492,765,1169,1810,
%T A032190 2786,4340,6712,10461,16273,25414,39650,62074,97108,152287,238837,
%U A032190 375166,589526,927554,1459960,2300347,3626241,5721044,9030450,14264308,22542396
%N A032190 Number of cyclic compositions of n into parts >= 2.
%C A032190 Number of ways to partition n elements into pie slices each with at least 2 elements.
%C A032190 Hackl and Prodinger (2018) indirectly refer to this sequence because their Proposition 2.1 contains the g.f. of this sequence. In the paragraph before this proposition, however, they refer to sequence A000358(n) = a(n) + 1. - _Petros Hadjicostas_, Jun 04 2019
%H A032190 Alois P. Heinz, <a href="/A032190/b032190.txt">Table of n, a(n) for n = 1..1000</a>
%H A032190 Ricardo Gómez Aíza, <a href="https://arxiv.org/abs/2009.02669">Symbolic dynamical scales: modes, orbitals, and transversals</a>, arXiv:2009.02669 [math.DS], 2020.
%H A032190 C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>
%H A032190 Daryl DeFord, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/52-5/DeFord.pdf">Enumerating distinct chessboard tilings</a>, Fibonacci Quart. 52 (2014), 102-116; see formula (5.3) in Theorem 5.2, p. 111.
%H A032190 Benjamin Hackl and Helmut Prodinger, <a href="https://arxiv.org/abs/1801.09934">The Necklace Process: A Generating Function Approach</a>, arXiv:1801.09934 [math.PR], 2018.
%H A032190 Benjamin Hackl and Helmut Prodinger, <a href="https://doi.org/10.1016/j.spl.2018.06.010">The Necklace Process: A Generating Function Approach</a>, Statistics and Probability Letters 142 (2018), 57-61.
%H A032190 P. 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 A032190 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=764">Encyclopedia of Combinatorial Structures 764</a>
%H A032190 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F A032190 "CIK" (necklace, indistinct, unlabeled) transform of 0, 1, 1, 1...
%F A032190 From _Petros Hadjicostas_, Sep 10 2017: (Start)
%F A032190 For all the formulas below, assume n >= 1. Here, phi(n) = A000010(n) is Euler's totient function.
%F A032190 a(n) = (1/n) * Sum_{d|n} b(d)*phi(n/d), where b(n) = A001610(n-1).
%F A032190 a(n) = (1/n) * Sum_{d|n} phi(n/d)*(Fibonacci(d-1) + Fibonacci(d+1) - 1) (because of the equation a(n) = A000358(n) - 1 stated in the CROSSREFS section below).
%F A032190 G.f.: -x/(1-x) + Sum_{k>=1} phi(k)/k * log(1/(1-B(x^k))) where B(x) = x*(1+x). (This is a modification of a formula due to _Joerg Arndt_.)
%F A032190 G.f.: Sum_{k>=1} phi(k)/k * log((1-x^k)/(1-B(x^k))), which agrees with the one in the Encyclopedia of Combinatorial Structures, #764, above. (We have Sum_{n>=1} (phi(n)/n)*log(1-x^n) = -x/(1-x), which follows from the Lambert series Sum_{n>=1} phi(n)*x^n/(1-x^n) = x/(1-x)^2.)
%F A032190 Sum_{d|n} a(d)*d = n*Sum_{d|n} b(d)/d, where b(n) = A001610(n-1).
%F A032190 (End)
%F A032190 a(n) = Sum_{1 <= i <= ceiling((n-1)/2)} [ (1/(n - i)) * Sum_{d|gcd(i, n-i)} phi(d) * binomial((n - i)/d, i/d) ]. (This is a slight variation of DeFord's formula for the number of distinct Lucas tilings of a 1 X n bracelet up to symmetry, where we exclude the case with i = 0 dominoes.) - _Petros Hadjicostas_, Jun 07 2019
%p A032190 # formula (5.3) of Daryl Deford for "Number of distinct Lucas tilings of a 1 X n
%p A032190 # bracelet up to symmetry" in "Enumerating distinct chessboard tilings"
%p A032190 A032190 := proc(n)
%p A032190     local a,i,d ;
%p A032190     a := 0 ;
%p A032190     for i from 0 to ceil((n-1)/2) do
%p A032190         for d in numtheory[divisors](i) do
%p A032190             if modp(igcd(i,n-i),d) = 0 then
%p A032190                 a := a+(numtheory[phi](d)*binomial((n-i)/d,i/d))/(n-i) ;
%p A032190             end if;
%p A032190         end do:
%p A032190     end do:
%p A032190     a ;
%p A032190 end proc:
%p A032190 seq(A032190(n),n=1..60) ; # _R. J. Mathar_, Nov 27 2014
%t A032190 nn=40;Apply[Plus,Table[CoefficientList[Series[CycleIndex[CyclicGroup[n],s]/.Table[s[i]->x^(2i)/(1-x^i),{i,1,n}],{x,0,nn}],x],{n,1,nn/2}]] (* _Geoffrey Critzer_, Aug 10 2013 *)
%t A032190 A032190[n_] := Module[{a=0, i, d, j, dd}, For[i=1, i <= Ceiling[(n-1)/2], i++, For[dd = Divisors[i]; j=1, j <= Length[dd], j++, d=dd[[j]]; If[Mod[GCD[i, n-i], d] == 0, a = a + (EulerPhi[d]*Binomial[(n-i)/d, i/d])/(n-i)]]]; a]; Table[A032190[n], {n, 1, 60}] (* _Jean-François Alcover_, Nov 27 2014, after _R. J. Mathar_ *)
%Y A032190 a(n) = A000358(n) - 1. Cf. A008965.
%K A032190 nonn
%O A032190 1,4
%A A032190 _Christian G. Bower_
%E A032190 Better name from _Geoffrey Critzer_, Aug 10 2013