A032198 -id:A032198 - cp's OEIS frontend

A032170 "CHK" (necklace, identity, unlabeled) transform of 1, 2, 3, 4, ...

1, 2, 5, 10, 24, 50, 120, 270, 640, 1500, 3600, 8610, 20880, 50700, 124024, 304290, 750120, 1854400, 4600200, 11440548, 28527320, 71289000, 178526880, 447910470, 1125750120, 2833885800, 7144449920, 18036373140, 45591631800, 115381697740, 292329067800

Offset: 1

Christian G. Bower

nonn

Apparently, for n > 2, the same as A072337. - Ralf Stephan, Feb 01 2004
a(n) is the number of prime period-n periodic orbits of Arnold's cat map. - Bruce Boghosian, Apr 26 2009
From Petros Hadjicostas, Nov 17 2017: (Start)
A first proof of the g.f., given below, can be obtained using the first of Vladeta Jovovic's formulae. If b(n) = A004146(n), then B(x) = Sum_{n >= 1} b(n)*x^n = x*(1 + x)/((1 - x)*(1 - 3*x + x^2)) (see the documentation for sequence A004146). From Jovovich's first formula, A(x) = Sum_{n >= 1} a(n)*x^n = Sum_{n >= 1} (1/n)*Sum_{d | n} mu(d)*b(n/d)*x^n. Letting m = n/d, we get A(x) = Sum_{d >= 1} (mu(d)/d)*Sum_{m >= 1} b(m)*(x^d)^m/m = Sum_{d >= 1} (mu(d)/d)*f(x^d), where f(y) = Sum_{m >= 1} b(m)*y^m/m = int(B(w)/w, w = 0..y) = int((1 + w)/((1 - w)*(1 - 3*w + w^2)), w = 0..y) = log((1 - y)^2/(1 - 3*y + y^2)) for |y| < (3 - sqrt(5))/2.
A second proof of the g.f. can be obtained using C. G. Bower's definition of the CHK transform of a sequence (e(n): n>=1) with g.f. E(x) (see the links below). If (c_k(n): n >= 1) = CHK_k(e(n): n >= 1), then (c_k(n): n >= 1) = (1/k)*(MOEBIUS*AIK)k (e_n: n >= 1) = (1/k)*Sum{d | gcd(n,k)} mu(d)*AIK_{k/d}(e(n/d): n multiple of d), where the * between MOEBIUS and AIK denotes Dirichlet convolution and (d_k(n): n >= 1) = AIK_k(e(n): n >= 1) has g.f. E(x)^k. (There is a typo in the given definition of CHK in the link.)
If C(x) is the g.f. of CHK(e(n): n >= 1) = Sum_{k = 1..n} CHK_k(e(n): n >= 1), then C(x) = Sum_{n>=1} Sum_{k = 1..n} c_k(n)*x^n = Sum_{k >= 1} (1/k) Sum_{n >= k} Sum_{d | gcd(n,k)} mu(d)*d_{k/d}(n/d)*x^n. Letting m = n/d and s = k/d and using the fact that E(0) = 0, we get C(x) = Sum_{d >= 1} (mu(d)/d)*Sum_{s >= 1} (1/s)*Sum_{m >= s} d_s(m)*(x^d)^m = Sum_{d >= 1} (mu(d)/d)*Sum_{s >= 1} E(x^d)^s. Thus, C(x) = -Sum_{d >= 1} (mu(d)/d)*log(1 - E(x^d)).
For the sequence (e(n): n >= 1) = (n: n >= 1), we have E(x) = Sum_{n>=1} n*x^n = x/(1 - x)^2, and thus A(x) = C(x) = -Sum_{d >= 1} (mu(d)/d)*log(1 - x/(1-x)^2), from which we can easily get the g.f. given in the formula section.
Apparently, for this sequence and for sequences A032165, A032166, A032167, the author assumes that C(0) = 0 (i.e., he assumes the CHK transform has no constant term), while for sequences A032164, A108529, and possibly others, he assumes that the CHK transform starts with the constant term 1 (i.e., he assumes C(x) = 1 - Sum_{d >= 1} (mu(d)/d)*log(1 - E(x^d))). (End)
From Petros Hadjicostas, Jul 13 2020: (Start)
We elaborate further on Michel Marcus's claim below. Consider his sequence (b(n): n >= 1) with b(1) = 3 and b(n) = a(n) for n >= 2.
Using the identity -Sum_{k >= 1} (mu(k)/k)*log(1 - x^k) = x for |x| < 1 and the g.f. of (a(n): n >= 1) below, we see that Sum_{n >= 1} b(n)*x^n = 3*x - a(1)*x + Sum_{n >= 1} a(n)*x^n = 2*x + Sum_{k >= 1} (mu(k)/k)*(2*log(1 - x^k) - log(1 - 3*x^k + x^(2*k))) = -Sum_{k >= 1} (mu(k)/k)*log(1 - 3*x^k + x^(2*k)).
Following Kam Cheong Au (2020), let d(w,N) be the dimension of the Q-span of weight w and level N of colored multiple zeta values (CMZV). Here Q are the rational numbers.
Deligne's bound says that d(w,N) <= D(w,N), where 1 + Sum_{w >= 1} D(w,N)*t^w = (1 - a*t + b*t^2)^(-1) when N >= 3, where a = phi(N)/2 + omega(N) and b = omega(N) - 1 (with omega(N) being the number of distinct primes of N).
For N = 6, a = phi(6)/2 + omega(6) = 2/2 + 2 = 3 and b = omega(6) - 1 = 1. It follows that D(w, N=6) = A001906(w+1) = Fibonacci(2*(w+1)).
For some reason, Kam Cheong Au (2020) assumes Deligne's bound is tight, i.e., d(w,N) = D(w,N). He sets Sum_{w >= 1} c(w,N)*t^w = log(1 + Sum_{w >= 1} d(w,N)*t^w) = log(1 + Sum_{w >= 1} D(w,N)*t^w) = -log(1 - a*t + b*t^2) for N >= 3.
For N = 6, we get that c(w, N=6) = A005248(w)/w.
He defines d*(w,N) = Sum_{k | w} (mu(k)/k)*c(w/k,N) to be the "number of primitive constants of weight w and level N". (Using the terminology of A113788, we may perhaps call d*(w,N) the number of irreducible colored multiple zeta values at weight w and level N.)
Using standard techniques of the theory of g.f.'s, we can prove that Sum_{w >= 1} d*(w,N)*t^w = Sum_{s >= 1} (mu(s)/s) Sum_{k >= 1} c(k,N)*(t^s)^k = -Sum_{s >= 1} (mu(s)/s)*log(1 - a*t^s + b*t^(2*s)).
For N = 6, we saw that a = 3 and b = 1, and hence d*(w, N=6) = b(w) for w >= 1 (as claimed by Michel Marcus below). See Table 1 on p. 6 in Kam Cheong Au (2020). (End)

Michael De Vlieger, Table of n, a(n) for n = 1..2400
Kam Cheong Au, Evaluation of one-dimensional polylogarithmic integral, with applications to infinite series, arXiv:2007.03957 [math.NT], 2020. See line N = 6 in Table 1 (p. 6).
C. G. Bower, Transforms (2).
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
Eric Weisstein's World of Mathematics, Arnold's cat map.
Wikipedia, Arnold's cat map.
Index entries for sequences related to Lyndon words

Cf. A000010, A001221, A001906, A004146, A032164, A032165, A032166, A032167, A032198, A005248, A108529, A113788.

Table[DivisorSum[n, MoebiusMu[n/#] (LucasL[2 #] - 2) &]/n, {n, 31}] (* Michael De Vlieger, Nov 18 2017 *)

a(n) = (1/n)*Sum_{d | n} mu(n/d)*A004146(d). - Vladeta Jovovic, Feb 15 2003
Inverse EULER transform of Fibonacci(2*n). - Vladeta Jovovic, May 04 2006
G.f.: Sum_{n >= 1} (mu(n)/n)*f(x^n), where f(y) = log((1 - y)^2/(1 - 3*y + y^2)). - Petros Hadjicostas, Nov 17 2017
It appears that the sequence b(1) = 3, b(n) = a(n) for n >= 2 is related to the rational sequence (c(w, N=6): w >= 1) = (A005248(w)/w: w >= 1) whose g.f. is log(1/(1 - a*t + b*t^2)), where a = phi(N)/2 + omega(N) and b = omega(N) - 1 when N = 6, where phi is A000010 and omega is A001221. See Kam Cheong Au (2020). - Michel Marcus, Jul 13 2020 [Edited by Petros Hadjicostas, Jul 13 2020]

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)

A322059 Expansion of generating function related to a certain class of combinatorial objects.

Original entry on oeis.org

1, 3, 8, 21, 50, 128

Offset: 1

N. J. A. Sloane, Dec 25 2018

For precise definition see Example 15.3.6 of Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 1001-1002.

Apparently this has been computed by series inversion (INVERT transform) of the generating function x+2*x^2+3*x^3+4*x^4, which is not related to a Cyc. transformation (as claimed by Bona) (??) To obtain an interpretation from the Polya cycle index for the group of cyclic permutations, one would have to plug in the g.f. x+2*x^2+5*x^3+10*x^4+18*x^5+26*x^6+.. and it's difficult to associate this with any sort of marked linear chains of length up to 4 (because terms of x^5 and higher are needed). - R. J. Mathar, Feb 06 2025

N.Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 1001-1002.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, errata.
N. J. A. Sloane, Annotated scan of page 1001 of Bona (2015).
N. J. A. Sloane, Annotated scan of page 1002 of Bona (2015).

Cf. A322060, A380886 (column 4), A380890 (cycles of rooted chains), A032198 (cycles of directed linear chains), A002861 (cycles of rooted trees).

A329156 Expansion of Product_{k>=1} 1 / (1 - Sum_{j>=1} j * x^(k*j)).

Original entry on oeis.org

1, 1, 4, 10, 29, 72, 200, 510, 1364, 3546, 9348, 24400, 64090, 167562, 439200, 1149360, 3010349, 7879832, 20633304, 54014950, 141422328, 370239300, 969323000, 2537696160, 6643839400, 17393731933, 45537549048, 119218684970, 312119004990, 817137724392, 2139295489200, 5600747143950

Offset: 0

Ilya Gutkovskiy, Nov 06 2019

nonn

Euler transform of A032198.

Alois P. Heinz, Table of n, a(n) for n = 0..2392
Christian Kassel and Christophe Reutenauer, Pairs of intertwined integer sequences, arXiv:2507.15780 [math.NT], 2025. See p. 13.

Cf. A006951, A032198, A088305, A162891, A258210, A329157, A329163, A386706, A387017.

Convolution inverse of A329157.

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i>1, b(n, i-1), 0)-
      add(b(n-i*j, min(n-i*j, i-1))*j, j=`if`(i=1, n, 1..n/i)))
    end:
a:= proc(n) option remember; `if`(n=0, 1,
      -add(a(j)*b(n-j$2), j=0..n-1))
    end:
seq(a(n), n=0..31);  # Alois P. Heinz, Jul 25 2025

nmax = 31; CoefficientList[Series[Product[1/(1 - Sum[j x^(k j), {j, 1, nmax}]), {k, 1, nmax}], {x, 0, nmax}], x]
nmax = 31; CoefficientList[Series[Product[1/(1 - x^k/(1 - x^k)^2), {k, 1, nmax}], {x, 0, nmax}], x]

G.f.: Product_{k>=1} 1 / (1 - x^k / (1 - x^k)^2).
G.f.: exp(Sum_{k>=1} ( Sum_{d|k} 1 / (d * (1 - x^(k/d))^(2*d)) ) * x^k).
G.f.: Product_{k>=1} 1 / (1 - x^k)^A032198(k).
G.f.: A(x) = Product_{k>=1} B(x^k), where B(x) = g.f. of A088305.
a(n) ~ phi^(2*n-1), where phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Nov 07 2019
a(2^k) = A002878(2^k-1) for all nonnegative integers k. Follows from Cor. 4.5 on page 11 of Kassel-Reutenauer paper. - Michael De Vlieger, Jul 28 2025

A005594 States of a dynamic storage system.

Original entry on oeis.org

1, 2, 4, 7, 14, 26, 59, 122, 284, 647, 1528, 3602, 8679, 20882, 50824, 124055, 304574, 750122, 1855099, 4600202, 11442086, 28527447, 71292604, 178526882, 447919419, 1125750146, 2833906684, 7144450567, 18036423974

Offset: 0

N. J. A. Sloane

nonn

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000
C. G. Bower, Transforms
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 107
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 111
M. D. McIlroy, The number of states of a dynamic storage system, Computer J., 25 (No. 3, 1982), 388-392.
M. D. McIlroy, The number of states of a dynamic storage system, Computer J., 25 (No. 3, 1982), 388-392. (Annotated scanned copy)
Index entries for sequences related to necklaces

Equals A032198(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}];
CoefficientList[gf, x] + 1 (* Jean-François Alcover, Jul 29 2018, after Joerg Arndt *)

Also "CIK" (necklace, indistinct, unlabeled) transform of 2, 1, 1, 1, ...

Sequence extended by Christian G. Bower

A308723 Total number of parts in all m-cyclic compositions of n (where each part of size m can be colored with one of m colors).

Original entry on oeis.org

1, 4, 10, 26, 59, 160, 383, 1018, 2606, 6836, 17721, 46580, 121405, 318212, 832190, 2179358, 5702903, 14933264, 39088187, 102341134, 267915110, 701426484, 1836311925, 4807575700, 12586269265, 32951401540, 86267576506, 225851752438, 591286729907, 1548009602240, 4052739537911

Offset: 1

Petros Hadjicostas, Jun 19 2019

nonn

Unmarked cyclic compositions (originally studied by Sommerville (1909)) are equivalence classes of ordered partitions of n such that two such partitions are equivalent iff one can be obtained from the other by rotation.
The so-called "m-cyclic compositions" of n are cyclic compositions of n such that each part of size m can be colored with any one of m colors. (Colored ordered partitions were originally introduced by Agarwal (2000). The theory of Bower about transforms in the web link below is a generalization of this idea.)
If b(n) is the number of m-colored compositions of n, then (b(n): n >= 1) is the CIK transform of the sequence 1, 2, 3, ... and it has the g.f. -Sum_{n >= 1} (phi(s)/s) * log(1 - C(x^s)), where C(x) = x + 2*x^2 + 3*x^3 + 4*x^4 + ... = x/(1-x)^2. (See Bower's link about transforms for information about the CIK transform.) Thus, b(n) = A032198(n) for n >= 1, and its g.f. and formula were also derived in Gibson (2017) and Gibson et al. (2018).
In general, if c = (c(m): m >= 1) is the input sequence and (b_k(n): n >= 1) is the output sequence under the CIK[k] transform of c, then b_n = (CIK c)n = Sum{k = 1..n} (CIK[k] c)n = Sum{k = 1..n} b_k(n) for all n >= 1 (see Bower's web link on transforms).
The g.f. of (b_k(n): n >= 1) is Sum_{n >= 1} b_k(n)*x^k = (1/k)*Sum_{d|k} phi(d) * A(x^d)^(k/d). It follows that Sum_{n >= 1, k >= 1} b_k(n)*x^n*y^k = -Sum_{d >= 1} (phi(d)/d) * log(1 - y^d *A(x^d)) (with the understanding that b_k(n) = 0 for k > n).
For n >= 1, let d(n) = Sum_{k >= 1} k*b_k(n) = total number of parts of in all compositions of n under the CIK transform of c = (c(m): m >= 1). Thus, d(n) is the total number of parts in all cyclic compositions of n where each part of size m can be colored with c(m) colors.
To obtain the g.f. of (d(n): n >= 1) = (Sum_{k = 1..n} k*b_k(n): n >= 1), we differentiate the bivariate g.f. Sum_{n >= 1, k >= 1} b_k(n)*x^n*y^k w.r.t. y and set y = 1. We get Sum_{n >= 1} d(n)*x^n = Sum_{d >= 1} phi(d) * A(x^d)/(1 - A(x^d)).
In our case, A(x) = x/(1 - x)^2, so Sum_{n >= 1} d(n)*x^n = -Sum_{d >=1} phi(d) * x^d/(1 - 3*x^d + x^(2*d)), which is exactly the g.f. of the current sequence that was proved in Gibson (2017) and Gibson et al. (2018).

			We have a(1) = 1 because 1_1 is the only m-color cyclic composition of n = 1 and the total number of parts is 1.
We have a(2) = 4 because 2_1, 2_2, 1_1 + 1_1 are all the m-color cyclic compositions of 2 and the total number of parts is 1 + 1 + 2 = 4.
We have a(3) = 10 because 3_1, 3_2, 3_3, 1_1 + 2_1, 1_1 + 2_2, 1_1 + 1_1 + 1_1 are all the m-color cyclic compositions of n = 3 and the total number of parts is 1 + 1 + 1 + 2 + 2 + 3 = 10.
We have a(4) = 26 because 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 are all the m-color cyclic compositions of n = 4 and the total number of parts is 1 + 1 + 1 + 1 + 2 + 2 + 2 + 2 + 2 + 2 + 3 + 3 + 4 = 26.

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.
D. M. Y. Sommerville, On certain periodic properties of cyclic compositions of numbers, Proc. London Math. Soc., S2-7(1) (1909), 263-313.

Cf. A001906, A032198, A088305.

a(n) = Sum_{s|n} phi(s)*A088305(n/s) = Sum_{s|n} phi(n/s)*Fibonacci(2*s) for n >= 1. (See Theorem 3.1 in Gibson et al. (2018).)
a(n) ~ (2/(3 - sqrt(5)))^n/sqrt(5) for large n. (See p. 3210 in Gibson et al. (2018).)
G.f.: Sum_{s >= 1} phi(s) * x^s/(1 - 3*x^s + x^(2*s)). (See Eq. (1.2) in Gibson et al. (2018).)

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

A329157 Expansion of Product_{k>=1} (1 - Sum_{j>=1} j * x^(k*j)).

Original entry on oeis.org

1, -1, -3, -3, -4, 3, 2, 19, 21, 32, 40, 45, 16, 8, -18, -125, -164, -291, -358, -530, -588, -724, -592, -675, -358, -207, 570, 1201, 2208, 3333, 4944, 6490, 8277, 10492, 11800, 13260, 14328, 14722, 12942, 12075, 5640, 603, -10444, -21120, -39360, -55876, -83488

Offset: 0

Ilya Gutkovskiy, Nov 06 2019

sign

Convolution inverse of A329156.

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Cf. A003056, A032198, A077285, A088305, A104575, A319668, A329156, A385001.

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i>1, b(n, i-1), 0)-
      add(b(n-i*j, min(n-i*j, i-1))*j, j=`if`(i=1, n, 1..n/i)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..46);  # Alois P. Heinz, Jul 18 2025

nmax = 46; CoefficientList[Series[Product[(1 - Sum[j x^(k j), {j, 1, nmax}]), {k, 1, nmax}], {x, 0, nmax}], x]
nmax = 46; CoefficientList[Series[Product[(1 - x^k/(1 - x^k)^2), {k, 1, nmax}], {x, 0, nmax}], x]

G.f.: Product_{k>=1} (1 - x^k / (1 - x^k)^2).
G.f.: exp(-Sum_{k>=1} ( Sum_{d|k} 1 / (d * (1 - x^(k/d))^(2*d)) ) * x^k).
G.f.: Product_{k>=1} (1 - x^k)^A032198(k).
G.f.: A(x) = Product_{k>=1} 1 / B(x^k), where B(x) = g.f. of A088305.
a(n) = Sum_{k=0..A003056(n)} (-1)^k * A385001(n,k). - Alois P. Heinz, Jul 18 2025

A365857 Number of cyclic compositions of 2*n into odd parts.

Original entry on oeis.org

1, 2, 4, 7, 14, 30, 63, 142, 328, 765, 1810, 4340, 10461, 25414, 62074, 152287, 375166, 927554, 2300347, 5721044, 14264308, 35646311, 89264834, 223959710, 562878429, 1416953362, 3572233420, 9018211989, 22795835726, 57690911720, 146164582455, 370705552702, 941109975022, 2391391374017, 6081865318124

Offset: 1

Joshua P. Bowman, Sep 20 2023

nonn

Even bisection of A032189.
Also the number of cyclic compositions into an even number of odd parts; because such a sum must be even, alternating terms are zero and have been removed.
Also the number of dual classes of cyclic n-color compositions of n. A cyclic composition is a sum of positive integers in which the order of the parts is considered up to cyclic permutation. In other words, it is the collection of components remaining in the cycle graph C_n on n vertices when one or more edges are removed, and rotations are considered equivalent. In an n-color composition, each part of size k is assigned one of k "colors" which may be represented graphically by marking one vertex in the part. (See A032198 for the number of cyclic n-color compositions.) The dual of a cyclic n-color composition is obtained by switching the roles of edges and vertices in C_n, then removing each edge that came from a previously marked vertex while marking each vertex that came from a previously removed edge. Each cyclic n-color composition of n either belongs to a dual pair or is self-dual. (See A365859 for the number of self-dual cyclic n-color compositions.)

A. K. Agarwal, n-colour compositions, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.
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. 25.
Meghann Moriah Gibson, Daniel Gray, and Hua Wang, Combinatorics of n-color cyclic compositions, Discrete Mathematics 341 (2018), 3209-3226.

Cf. A001350, A032189, A032198, A365858, A365859.

N=99;  x='x+O('x^N); B(x)=x/(1-x^2);
A=Vec(sum(k=1, N, eulerphi(k)/k*log(1/(1-B(x^k)))));
vector(#A\2,n,A[2*n]) \\ Joerg Arndt, Sep 22 2023

from sympy import totient, lucas, divisors
def A365857(n): return sum(totient((n<<1)//k)*(lucas(k)-((k&1^1)<<1)) for k in divisors(n<<1,generator=True))//n>>1 # Chai Wah Wu, Sep 23 2023

G.f.: (1/2)*(Sum_{k>=1} phi(k)/k * log((1-2*x^k+x^(2*k))/(1-3*x^k+x^(2*k))) + Sum_{m>=1} phi(2*m)/(2*m) * log((1+x^m-x^(2*m))/(1-x^m-x^(2*m)))).
a(n) = (1/(2*n)) * Sum_{k divides 2*n} phi(k)*A001350((2*n)/k).
a(n) = (A032198(n) + A365859(n))/2.

A365859 Number of self-dual cyclic n-color compositions.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 5, 1, 10, 3, 19, 2, 41, 5, 94, 1, 211, 10, 493, 3, 1170, 19, 2787, 2, 6713, 41, 16274, 5, 39651, 94, 97109, 1, 238838, 211, 589527, 10, 1459961, 493, 3626242, 3, 9030451, 1170, 22542397, 19, 56393862, 2787, 141358275, 2, 354975433, 6713, 892893262, 41, 2249412291, 16274, 5674891017

Offset: 1

Joshua P. Bowman, Sep 20 2023

nonn

A cyclic composition is a sum in which the order of the parts is considered up to cyclic permutation. In other words, it is the collection of components remaining in the cycle graph C_n on n vertices when one or more edges are removed, and rotations are considered equivalent. In an n-color composition, each part of size k is assigned one of k "colors" which may be represented graphically by marking one vertex in the part. The dual of a cyclic n-color composition is obtained by switching the roles of edges and vertices in C_n, then removing each edge that came from a previously marked vertex while marking each vertex that came from a previously removed edge. A cyclic n-color composition is self-dual if it is invariant under this process.
a(n) is also the number of cyclic compositions of A000265(n) into odd parts.
This sequence is self-similar; removing all odd-indexed terms results in the same sequence.

			Every power of 2 has only one self-dual cyclic n-color composition, which has all parts of size 1.
The self-dual cyclic n-color compositions of 5 are 1_1+1_1+1_1+1_1+1_1, 1_1+2_2+2_1, and 5_3, where the subscript indicates the color of the part, or which vertex is marked within the part.

A. K. Agarwal, n-colour compositions, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.
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. 33.
Meghann Moriah Gibson, Daniel Gray, and Hua Wang, Combinatorics of n-color cyclic compositions, Discrete Mathematics 341 (2018), 3209-3226.
Brian Hopkins, Jesús Sistos Barrón, and Hua Wang, Conjugating cyclic n-color compositions, Utilitas Mathematica (2025) Vol. 122, 53-64. See p. 61.
Jesus Omar Sistos Barron, Counting Conjugates of Colored Compositions, Honors College Thesis, Georgia Southern Univ. (2024), No. 985. See p. 25.

Cf. A000204 (Lucas), A000265, A032189, A032198, A365857, A365858.

my(N=66,x='x+O('x^N)); Vec( sum(k=1,N, eulerphi(2*k)/(2*k) * log((1+x^k-x^(2*k))/(1-x^k-x^(2*k))) ) )  \\ Joerg Arndt, Sep 21 2023

from sympy import totient, lucas, divisors
def A365859(n):
    m = n>>(~n&n-1).bit_length()
    return sum(totient(k)*lucas(m//k) for k in divisors(m,generator=True))//m # Chai Wah Wu, Sep 23 2023

G.f.: Sum_{k>=1} phi(2*k)/(2*k) * log((1+x^k-x^(2*k))/(1-x^k-x^(2*k))).
a(n) = (1/(b(n)))*[Sum_{k divides A000265(n)} phi(k)*lucas(b(n)/k)], where b(n) = A000265(n) and lucas(n) = A000204(n).
a(n) = 2*A365857(n) - A032198(n).

cp's OEIS Frontend

A032170 "CHK" (necklace, identity, unlabeled) transform of 1, 2, 3, 4, ...

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A322059 Expansion of generating function related to a certain class of combinatorial objects.

Views

Author

Keywords

Comments

Links

Crossrefs

A329156 Expansion of Product_{k>=1} 1 / (1 - Sum_{j>=1} j * x^(k*j)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A005594 States of a dynamic storage system.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A308723 Total number of parts in all m-cyclic compositions of n (where each part of size m can be colored with one of m colors).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A329157 Expansion of Product_{k>=1} (1 - Sum_{j>=1} j * x^(k*j)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica