A032199 - OEIS

%I #38 Jan 07 2018 10:13:18

%S 3,11,33,114,397,1524,5873,23492,95033,390262,1617513,6764338,

%T 28478813,120631428,513569941,2196269672,9429031893,40621573968,

%U 175544747673,760719000950,3304818106413,14389871196680

%N "CIK" (necklace, indistinct, unlabeled) transform of 3,5,7...

%C The auxiliary sequence (c(n): n>=1) that appears in the formula section below can be determined via its g.f. C(x) = Sum_{n>=1} c(n)*x^n. We have C(x) = x*(dB(x)/dx)/(1-B(x)), where B(x) = 3*x + 5*x^2 + 7*x^3 + 9*x^4 + ... = (3*x - x^2)/(1-x)^2. We get C(x) = (3*x + x^2)/((1-x)*(2*x^2 - 5*x + 1)) = -2*x/(1-x) + (5*x - 4*x^2)/(2*x^2 - 5*x +1). The second term of the last equation is the g.f. of the sequence (A159289(n-1): n>=1). - _Petros Hadjicostas_, Jan 06 2018

%H C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>

%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>

%F From _Petros Hadjicostas_, Jan 06 2018: (Start)

%F a(n) = (1/n)*Sum_{d|n) phi(d)*c(n/d), where c(n) = -2 + A159289(n-1) = -2 + r1^n + r2^n with r1 = (5 - sqrt(17))/2 and r2 = (5 + sqrt(17))/2 (for n >= 1). (Notice the different offsets between this sequence and sequence A159289.)

%F a(n) = -2 + (1/n)*Sum_{d|n} phi(n/d)*A159289(d-1).

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

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

%F (End)

%e From _Petros Hadjicostas_, Jan 06 2018: (Start)

%e We give examples to illustrate the meaning of the CIK transform, whose theory is outlined by C. G. Bower in the weblink above. We are forced, however, to switch the roles of sequences (a(n): n>=1) and (b(n): n>=1) in the weblink above about transforms.

%e We assume we have boxes of different sizes and colors. Here, b(n) = number of colors a box holding n balls can be, while a(n) = number of ways we can have a collection of boxes so that the total number of balls is n. We have (a(n): n>=1) = CIK((b(n): n>=1)).

%e Since b(1) = 3, b(2) = 5, b(3) = 7, etc., a box holding 1 ball can be one of 3 colors, a box holding 2 balls can be one of 5 colors, a box holding 3 balls can be one of 7 colors, and so on.

%e The meaning of the CIK transform entails that boxes of the same size and color are indistict and unlabeled, while they form a necklace (on a circle). (The boxes differ only in their size—how many balls they can hold—and in their color.)

%e We have a(1) = 3 because we have 1 ball in one box (that can hold 1 ball) and the box can be of one of 3 colors.

%e To prove that a(2) = 11, we consider two cases. In the first case, we have a single box that can hold 2 balls. This box can be one of 5 colors. In the second case, we have 2 identical boxes each holding 1 ball. Each such box can be one of 3 colors, say a, b, and c. We have 6 possibilities on a circle: aa, ab, ac, bb, bc, cc. Hence, a(2) = 5 + 6 = 11.

%e To prove that a(3) = 33, we consider three cases giving a total of 7 + 15 + 11 = 33 possibilities. In the first case, we have 1 box holding 3 balls. This case gives rise to 7 possibilities. In the second case, we have 2 boxes, one that can hold 2 balls and one that can hold 1 ball. In this case, we have 5 x 3 = 15 possibilities (even on a circle). In the third case, we have three identical boxes on a circle, each holding 1 ball. If the colors are a, b, and c, we have 11 possibilities on a circle: aaa, aab, aac, abb, abc, acb, acc, bbb, bbc, bcc, and ccc.

%e (End)

%Y Cf. A159289.

%K nonn

%O 1,1

%A _Christian G. Bower_

%E Name edited by _Petros Hadjicostas_, Jan 06 2018