|
| |
|
|
A032190
|
|
Number of cyclic compositions of n into parts >= 2.
|
|
4
|
|
|
|
0, 1, 1, 2, 2, 4, 4, 7, 9, 14, 18, 30, 40, 63, 93, 142, 210, 328, 492, 765, 1169, 1810, 2786, 4340, 6712, 10461, 16273, 25414, 39650, 62074, 97108, 152287, 238837, 375166, 589526, 927554, 1459960, 2300347, 3626241, 5721044, 9030450, 14264308, 22542396
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
Number of ways to partition n elements into pie slices each with at least 2 elements.
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
|
|
|
LINKS
|
|
|
|
FORMULA
|
"CIK" (necklace, indistinct, unlabeled) transform of 0, 1, 1, 1...
For all the formulas below, assume n >= 1. Here, phi(n) = A000010(n) is Euler's totient function.
a(n) = (1/n) * Sum_{d|n} b(d)*phi(n/d), where b(n) = A001610(n-1).
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).
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.)
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.)
Sum_{d|n} a(d)*d = n*Sum_{d|n} b(d)/d, where b(n) = A001610(n-1).
(End)
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
|
|
|
MAPLE
|
# formula (5.3) of Daryl Deford for "Number of distinct Lucas tilings of a 1 X n
# bracelet up to symmetry" in "Enumerating distinct chessboard tilings"
local a, i, d ;
a := 0 ;
for i from 0 to ceil((n-1)/2) do
for d in numtheory[divisors](i) do
if modp(igcd(i, n-i), d) = 0 then
a := a+(numtheory[phi](d)*binomial((n-i)/d, i/d))/(n-i) ;
end if;
end do:
end do:
a ;
end proc:
|
|
|
MATHEMATICA
|
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 *)
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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
