login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A032198 "CIK" (necklace, indistinct, unlabeled) transform of 1,2,3,4,... 2
1, 3, 6, 13, 25, 58, 121, 283, 646, 1527, 3601, 8678, 20881, 50823, 124054, 304573, 750121, 1855098, 4600201, 11442085, 28527446, 71292603, 178526881, 447919418, 1125750145, 2833906683, 7144450566, 18036423973 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

LINKS

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

C. G. Bower, Transforms (2)

P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.

Index entries for sequences related to necklaces

FORMULA

a(n) = 1/n*Sum_{d divides n} phi(n/d)*A004146(d). - Vladeta Jovovic, Feb 15 2003

From Petros Hadjicostas, Jan 07 2018: (Start)

a(n) = -2 + (1/n)*Sum_{d|n} phi(n/d)*A005248(d) = -2 + (1/n)*Sum_{d|n} phi(n/d)*L(2*d), where L(n) = A000032(n) is the usual Lucas sequence.

G.f.: -Sum_{n>=1} (phi(n)/n)*log(1-B(x^n)), where B(x) = x + 2*x^2 + 3*x^3 + 4*x^4 + ... = x/(1-x)^2.

G.f.: -2*x/(1-x) - Sum_{n>=1} (phi(n)/n)*log(1-3*x^n+x^(2*n)).

(End)

EXAMPLE

From Petros Hadjicostas, Jan 07 2018: (Start)

We give some examples to illustrate the theory of C. G. Bower about transforms given in the weblink above. We assume we have boxes of different sizes and colors that we place on a circle to form a necklace. Two boxes of the same size and same color are considered identical (indistinct and unlabeled). We do, however, change the roles of the sequences (a(n): n>=1) and (b(n): n>=1) that appear in the weblink  above. We assume (a(n): n>=1) = CIK((b(n): n>=1)).

Since b(1) = 1, b(2) = 2, b(3) = 3, etc., a box that can hold 1 ball only can be of 1 color only, a box that can hold 2 balls only can be one of 2 colors only, a box that can hold 3 balls can be one of 3 colors, and so on.

To prove that a(3) = 6, we consider three cases. In the first case, we have a single box that can hold 3 balls, and thus we have 3 possibilities for the 3 colors the box can be. In the second case, we have a box that can hold 2 balls and a box that can hold 1 ball. Here, we have 2 x 1 = 2 possibilities. In the third case, we have 3 identical boxes, each of which can hold 1 ball. This gives rise to 1 possibility. Hence, a(3) = 3 + 2 + 1 = 6.

To prove that a(4) = 13, we consider 5 cases: a box with 4 balls (4 possibilities), one box with 3 balls and one box with 1 ball (3 possibilities), two identical boxes each with 2 balls (3 possibilities), one box with 2 balls and two identical boxes each with 1 ball (2 possibilities), and four identical boxes each with 1 ball (1 possibility). Thus, a(4) = 4 + 3 + 3 + 2 + 1 = 13.

(End)

MATHEMATICA

nmax = 30;

f[x_] = Sum[n*x^n, {n, 1, nmax}];

gf = Sum[(EulerPhi[n]/n)*Log[1/(1 - f[x^n])] + O[x]^nmax, {n, 1, nmax}]/x;

CoefficientList[gf, x] (* Jean-Fran├žois Alcover, Jul 29 2018, after Joerg Arndt *)

PROG

(PARI)

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

f(x)=sum(n=1, N, n*x^n );

gf = sum(n=1, N, eulerphi(n)/n*log(1/(1-f(x^n)))  );

v = Vec(gf)

/* Joerg Arndt, Jan 21 2013 */

CROSSREFS

Cf. A000032, A004146, A005248, A032170.

Equals A005594(n)-1.

Sequence in context: A215984 A074890 A244704 * A079941 A255125 A267367

Adjacent sequences:  A032195 A032196 A032197 * A032199 A032200 A032201

KEYWORD

nonn

AUTHOR

Christian G. Bower

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 17 14:25 EDT 2018. Contains 316281 sequences. (Running on oeis4.)