A005594 -id:A005594 - cp's OEIS frontend

A032198 "CIK" (necklace, indistinct, unlabeled) transform of 1,2,3,4,...

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

Offset: 1

Christian G. Bower

nonn

			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)

Vaclav Kotesovec, Table of n, a(n) for n = 1..1000
A. K. Agarwal, n-colour compositions, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.
C. G. Bower, Transforms (2).
Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 31.
P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
P. Flajolet and M. Soria, The Cycle Construction. [pdf file]
Meghann Moriah Gibson, Combinatorics of compositions, Master of Science, Georgia Southern University, 2017.
Meghann Moriah Gibson, Daniel Gray, and Hua Wang, Combinatorics of n-color compositions, Discrete Mathematics 341 (2018), 3209-3226.
Index entries for sequences related to necklaces

Cf. A000032, A001906, A004146, A005248, A032170, A032287, A088305, A308723, A308747.

Equals A005594(n) - 1.

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

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

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)
From Petros Hadjicostas, Jun 19 2019: (Start)
According to Gibson et al. (2018), a(n) is the number of m-color cyclic compositions of n where each part of size m has m possible colors. This is nothing else than the CIK transform of the sequence 1, 2, 3, 4, ...
Using the theory of Flajolet and Soria (1991), Gibson et al. (2018, Eq. (1.1)) proved that the g.f. of a(n) is Sum_{s >= 1} (phi(s)/s) * log((1 - x^s)^2/(1 - 3*x^s + x^(2*s))), which is exactly the same g.f. as the ones above.
Gibson et al. (2018, p. 3210) also proved that a(n) ~ (2/(3-sqrt(5)))^n/n for large n. See also Chapter 3 in Gibson (2017).
(End)

A032287 "DIK" (bracelet, indistinct, unlabeled) transform of 1,2,3,4,...

Original entry on oeis.org

1, 3, 6, 13, 24, 51, 97, 207, 428, 946, 2088, 4831, 11209, 26717, 64058, 155725, 380400, 936575, 2314105, 5744700, 14300416, 35708268, 89359536, 224121973, 563126689, 1417378191, 3572884062, 9019324297, 22797540648

Offset: 1

Christian G. Bower

nonn

From Petros Hadjicostas, Jun 21 2019: (Start)
Under Bower's transforms, the input sequence c = (c(m): m >= 1) describes how each part of size m in a composition is colored. In a composition (ordered partition) of n >= 1, a part of size m is assumed to be colored with one of c(m) colors.
Under the DIK transform, we are dealing with "dihedral compositions" of n >= 1. These are equivalence classes of ordered partitions of n such that two such ordered partitions are equivalent if one can be obtained from the other by rotation or reflection.
If the input sequence is c = (c(m): m >= 1), denote the output sequence under the DIK transform by b = (b(n): n >= 1); i.e., b(n) = (DIK c)(n) for n >= 1. If C(x) = Sum_{m >= 1} c(m)*x^m is the g.f. of the input sequence c, then the g.f. of b = DIK c is Sum_{n >= 1} b(n)*x^n = -(1/2) * Sum_{d >= 1} (phi(d)/d) * log(1 - C(x^d)) + (1 + C(x))^2/(4 * (1 - C(x^2))) - (1/4).
For the current sequence (a(n): n >= 1), the input sequence is c(m) = m for all m >= 1. That is, we are dealing with the so-called "m-color dihedral compositions". Here, a(n) is the number of dihedral compositions of n where each part of size m may be colored with one of m colors. For the linear and cyclic versions of such m-color compositions, see Agarwal (2000), Gibson (2017), and Gibson et al. (2018).
Since C(x) = x/(1 - x)^2, we have Sum_{n >= 1} a(n) * x^n = (1/2) * Sum_{d >= 1} (phi(d)/d) * log((1 - x^d)^2 / (1 - 3*x^d + x^(2*d))) + (1/2) * x * (1 + x - 2*x^2 + x^3 + x^4)/((1 - x)^2 * (1 + x - x^2) * (1 - x - x^2)), which is the g.f. given by Andrew Howroyd in the PARI program below.
Note that -Sum_{d >= 1} (phi(d)/d) * log (1 - C(x^d)) = Sum_{d >= 1} (phi(d)/d) * log((1 - x^d)^2 / (1 - 3*x^d + x^(2*d))) is the g.f. of the "m-color cyclic compositions" that appear in Gibson (2017) and Gibson et al. (2018). See sequence A032198, which is the CIK transform of sequence (c(m): m >= 1) = (m: m >= 1).
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..200
A. K. Agarwal, n-colour compositions, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.
C. G. Bower, Transforms (2).
Meghann Moriah Gibson, Combinatorics of compositions, Master of Science, Georgia Southern University, 2017.
Meghann Moriah Gibson, Daniel Gray, and Hua Wang, Combinatorics of n-color compositions, Discrete Mathematics 341 (2018), 3209-3226.
Arnold Knopfmacher and Neville Robbins, Some properties of dihedral compositions, Util. Math. 92 (2013), 207-220.
Index entries for sequences related to bracelets

Cf. A000032, A000045, A001906, A005594, A032198, A088305, A308747.

DIK := proc(L::list)
    local  x,cidx,ncyc,d,gd,g,g2,n ;
    n := nops(L) ;
    g := add(op(i,L)*x^i,i=1..n) ;
    # wrap into the cycle index of the cyclic group C_n
    cidx := 0 ;
    for ncyc from 1 to n do
        for d in numtheory[divisors](ncyc) do
            gd := subs(x=x^d,g) ;
            cidx := cidx+1/ncyc*numtheory[phi](d)*gd^(ncyc/d) ;
        end do:
    end do:
    # cycle index is half of th eone for the cyclic group plus two
    # different branches or D_n with even or odd n
    cidx := cidx/2 ;
    g2 := subs(x=x^2,g) ;
    for ncyc from 1 to n do
        if type(ncyc,'odd') then
            cidx := cidx+ g*g2^((ncyc-1)/2)/2 ;
        else
            cidx := cidx+ (g^2*g2^((ncyc-2)/2) + g2^(ncyc/2))/4 ;
        end if;
    end do:
    taylor(cidx,x=0,nops(L)) ;
    gfun[seriestolist](%) ;
end proc:
A032287_list := proc(n)
        local ele ;
        ele := [seq(i,i=1..40)] ;
        DIK(ele) ;
end proc:
A032287_list(50) ; # R. J. Mathar, Feb 14 2025

seq[n_] := x(1 + x - 2 x^2 + x^3 + x^4)/((1 - x)^2 (1 - x - x^2)(1 + x - x^2)) + Sum[EulerPhi[d]/d Log[(1 - x^d)^2/(1 - 3 x^d + x^(2d)) + O[x]^(n+1)], {d, 1, n}] // CoefficientList[#, x]& // Rest // #/2&;
seq[30] (* Jean-François Alcover, Sep 17 2019, from PARI *)

seq(n)={Vec(x*(1 + x - 2*x^2 + x^3 + x^4)/((1 - x)^2*(1 - x - x^2)*(1 + x - x^2)) + sum(d=1, n, eulerphi(d)/d*log((1 - x^d)^2/(1 - 3*x^d + x^(2*d)) + O(x*x^n))))/2} \\ Andrew Howroyd, Jun 20 2018

From Petros Hadjicostas, Jun 21 2019: (Start)
a(n) = ( F(n+4) + (-1)^n * F(n-4) - 2 * (n + 1) + (1/n) * Sum_{d|n} phi(n/d) * L(2*d) )/2 for n >= 4, where F(n) = A000045(n) and L(n) = A000032(n) are the usual n-th Fibonacci and n-th Lucas numbers, respectively.
a(n) = (A032198(n) + A308747(n))/2 for n >= 1.
G.f.: (1/2) * Sum_{d >= 1} (phi(d)/d) * log((1 - x^d)^2 / (1 - 3*x^d + x^(2*d))) + (1/2) * x * (1 + x - 2*x^2 + x^3 + x^4)/((1 - x)^2 * (1 + x - x^2) * (1 - x - x^2)).
(End)

A308747 Number of achiral m-color cyclic compositions of n (that is, number of cyclic compositions of n with reflection symmetry where each part of size m can be colored with one of m colors).

Original entry on oeis.org

1, 3, 6, 13, 23, 44, 73, 131, 210, 365, 575, 984, 1537, 2611, 4062, 6877, 10679, 18052, 28009, 47315, 73386, 123933, 192191, 324528, 503233, 849699, 1317558, 2224621, 3449495, 5824220, 9030985, 15248099, 23643522, 39920141, 61899647, 104512392, 162055489, 273617107

Offset: 1

Petros Hadjicostas, Jun 21 2019

nonn

Cyclic compositions of a positive integer n are equivalence classes of ordered partitions of n such that two such partitions are equivalent if one can be obtained from the other by rotation. These were first studied by Sommerville (1909).
Symmetric cyclic compositions or circular palindromes or achiral cyclic compositions are those cyclic compositions that have at least one axis of symmetry. They were also studied by Sommerville (1909, pp. 301-304).
Let (c(m): m >= 1) be the input sequence and let b = (b(n): n >= 1) be the output sequence under the CPAL (circular palindrome) transform of c; that is, b(n) = (CPAC c)n for n >= 1. Hence, b(n) is the number of symmetric cyclic compositions of n where a part of size m can be colored with one of c(m) colors. If C(x) = Sum{m >= 1} c(m)*x^m is the g.f. of the input sequence c, then the g.f. of b = (CPAL c) is Sum_{n >= 1} b(n)*x^n = (1 + C(x))^2/(2 * (1 - C(x^2))) - (1/2).
For the current sequence, the input sequence is c(m) = m for m >= 1, and we are dealing with the so-called "m-color" compositions. m-color linear compositions were studied by Agarwal (2000), whereas m-color cyclic compositions were studied by Gibson (2017) and Gibson et al. (2018).
Thus, for the current sequence, a(n) is the number of symmetric (achiral) cyclic compositions of n where a part of size m may be colored with one of m colors (for each m >= 1).
The function A(x) = (exp(Pi*(x + 1)*I)*phi^(-x - 4) - exp(2*I*Pi*x)*phi^(4 - x) + exp(Pi*x*I)*phi^(x - 4) + phi^(x + 4))/sqrt(5) - 2*x, where phi is the golden ratio, shows that the sequence can be easily extended to all integers. - Peter Luschny, Aug 09 2020

			We have a(1) = 1 because we only have one symmetric cyclic composition of n = 1, namely 1_1 (and a part of size 1 can be colored with only one color).
We have a(2) = 3 because we have the following colored achiral cyclic compositions of n = 2: 2_1, 2_2, 1_1 + 1_1.
We have a(3) = 6 because we have the following colored achiral cyclic compositions of n = 3: 3_1, 3_2, 3_3, 1_1 + 2_1, 1_1 + 2_2, 1_1 + 1_1 + 1_1.
We have a(4) = 13 because we have the following colored achiral cyclic compositions of n = 4: 4_1, 4_2, 4_3, 4_4, 1_1 + 3_1, 1_1 + 3_2, 1_1 + 3_3, 2_1 + 2_1, 2_1 + 2_2, 2_2 + 2_2, 1_1 + 2_1 + 1_1, 1_1 + 2_2 + 1_1, 1_1 + 1_1 + 1_1 + 1_1.
We have a(5) = 23 because we have the following colored achiral cyclic compositions of n = 5:
(i) with one part: 5_1, 5_2, 5_3, 5_4, 5_5;
(ii) with two parts: 1_1 + 4_1, 1_1 + 4_2, 1_1 + 4_3, 1_1 + 4_4, 2_1 + 3_1, 2_1 + 3_2, 2_1 + 3_3, 2_2 + 3_1, 2_2 + 3_2, 2_2 + 3_3;
(iii) with three parts: 1_1 + 3_1 + 1_1, 1_1 + 3_2 + 1_1, 1_1 + 3_3 + 1_1, 2_1 + 1_1 + 2_1, 2_2 + 1_1 + 2_2;
(iv) with four parts: 1_1 + 1_1 + 2_1 + 1_1, 1_1 + 1_1 + 2_2 + 1_1 (here, the axis of symmetry passes through one of the 1's and through 2);
(v) with five parts: 1_1 + 1_1 + 1_1 + 1_1 + 1_1.

A. K. Agarwal, n-colour compositions, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.
Christian G. Bower, Transforms (2).
Petros Hadjicostas, Generalized colored circular palindromic compositions, Moscow Journal of Combinatorics and Number Theory, 9(2) (2020), 173-186.
Meghann Moriah Gibson, Combinatorics of compositions, Master of Science, Georgia Southern University, 2017.
Meghann Moriah Gibson, Daniel Gray, and Hua Wang, Combinatorics of n-color compositions, Discrete Mathematics 341 (2018), 3209-3226.
D. M. Y. Sommerville, On certain periodic properties of cyclic compositions of numbers, Proc. London Math. Soc. S2-7(1) (1909), 263-313.

Cf. A000045, A001906, A005594, A032198, A032287, A088305.

CPAL (circular palindrome) transform of 1, 2, 3, 4, ...
a(n) = 2*a(n - 1) + 2*a(n - 2) - 6*a(n - 3) + 2*a(n - 4) + 2*a(n - 5) - a(n - 6) for n >= 7 with a(1) = 1, a(2) = 3, a(3) = 6, a(4) = 13, a(5) = 23, and a(6) = 44.
a(n) = 3*a(n - 2) - a(n - 4) + 2*(n - 2) for n >= 5 with a(1) = 1, a(2) = 3, a(3) = 6, and a(4) = 13.
a(n) = Fib(n + 4) + (-1)^n * Fib(n - 4) - 2*n for n >= 4, where Fib(n) = A000045(n).
G.f.: x * (1 + x - 2*x^2 + x^3 + x^4)/((1 - x)^2 * (1 - x - x^2) * (1 + x - x^2)).

cp's OEIS Frontend

A032198 "CIK" (necklace, indistinct, unlabeled) transform of 1,2,3,4,...

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A032287 "DIK" (bracelet, indistinct, unlabeled) transform of 1,2,3,4,...

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A308747 Number of achiral m-color cyclic compositions of n (that is, number of cyclic compositions of n with reflection symmetry where each part of size m can be colored with one of m colors).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula