A001867 -id:A001867 - cp's OEIS frontend

A215327 Smooth necklaces with 3 colors.

1, 3, 5, 8, 15, 27, 58, 115, 252, 541, 1196, 2629, 5894, 13156, 29667, 66978, 151966, 345497, 788396, 1802678, 4133161, 9495317, 21861393, 50423468, 116514553, 269666605, 625108573, 1451128479, 3373267275, 7851415838, 18296568717

Offset: 0

Joerg Arndt, Aug 08 2012

nonn

We call a necklace (x[1],x[2],...,x[n]) smooth if abs(x[k]-x[k-1]) <= 1 for 2<=k<=n.

All binary necklaces (2 colors, A000031) are necessarily smooth.

			The smooth pre-necklaces, necklaces (N), and Lyndon words (L) of length 4 with 3 colors (using symbols ".", "1", and "2") are:
    ....   1       .  N
    ...1   4    ...1  N L
    ..1.   3     .1.
    ..11   4    ..11  N L
    ..12   4    ..12  N L
    .1.1   2      .1  N
    .11.   3     11.
    .111   4    .111  N L
    .112   4    .112  N L
    .121   4    .121  N L
    .122   4    .122  N L
    1111   1       1  N
    1112   4    1112  N L
    1121   3     121
    1122   4    1122  N L
    1212   2      12  N
    1221   3     221
    1222   4    1222  N L
    2222   1       2  N
There are 19 pre-necklaces, 15 necklaces, and 10 Lyndon words.
So a(4) = 15.

Cf. A001867 (necklaces, 3 colors), A215328 (smooth Lyndon words, 3 colors).

More terms from Joerg Arndt, Jun 17 2019

A054610 a(n) = Sum_{d|n} phi(d)*3^(n/d).

Original entry on oeis.org

0, 3, 12, 33, 96, 255, 780, 2205, 6672, 19755, 59340, 177177, 532416, 1594359, 4785228, 14349525, 43053504, 129140211, 387441756, 1162261521, 3486844320, 10460357775, 31381236876, 94143178893, 282430082832, 847288610475

Offset: 0

N. J. A. Sloane, Apr 16 2000

nonn

Dirichlet convolution of phi(n) and 3^n. - Richard L. Ollerton, May 07 2021

Seiichi Manyama, Table of n, a(n) for n = 0..2095

Column k=3 of A185651.

Cf. A001867, A034754.

a(n) = sum(k=1, n, 3^gcd(n,k)); \\ Michel Marcus, Apr 16 2021

a(n) = n * A001867(n).
a(n) = 3*A034754(n). - R. J. Mathar, May 18 2014
a(n) = Sum_{k=1..n} 3^gcd(n,k). - Ilya Gutkovskiy, Apr 16 2021
a(n) = Sum_{k=1..n} 3^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 07 2021

A056283 Number of n-bead necklaces with exactly three different colored beads.

Original entry on oeis.org

0, 0, 2, 9, 30, 91, 258, 729, 2018, 5613, 15546, 43315, 120750, 338259, 950062, 2678499, 7573350, 21480739, 61088874, 174184755, 497812638, 1425847623, 4092087522, 11765822365, 33887517870, 97756387365, 282414624746, 816999710223, 2366509198350, 6862930841141

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed.

			For n=3, the two necklaces are ABC and ACB.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A000031, A001867, A052823.

Column k=3 of A087854.

k=3; Table[k!DivisorSum[n,EulerPhi[#]StirlingS2[n/#,k]&]/n,{n,1,30}] (* Robert A. Russell, Sep 26 2018 *)

a(n) = A001867(n) - 3*A000031(n) + 3.
From Robert A. Russell, Sep 26 2018: (Start)
a(n) = (k!/n) Sum_{d|n} phi(d) S2(n/d,k), where k=3 is the number of colors and S2 is the Stirling subset number A008277.
G.f.: -Sum_{d>0} (phi(d)/d) * Sum_{j} (-1)^(k-j) * C(k,j) * log(1-j x^d), where k=3 is the number of colors. (End)

A056284 Number of n-bead necklaces with exactly four different colored beads.

Original entry on oeis.org

0, 0, 0, 6, 48, 260, 1200, 5106, 20720, 81876, 318000, 1223136, 4675440, 17815020, 67769552, 257700906, 980240880, 3731753180, 14222737200, 54278580036, 207438938000, 793940475900, 3043140078000, 11681057249536, 44900438149296, 172824331826580, 666070256489680

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed.

			For n=4, the six necklaces are ABCD, ABDC, ACBD, ACDB, ADBC and ADCB.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A001868.

Column k=4 of A087854.

k=4; Table[k!DivisorSum[n,EulerPhi[#]StirlingS2[n/#,k]&]/n,{n,1,30}] (* Robert A. Russell, Sep 26 2018 *)

a(n) = my(k=4);(k!/n)*sumdiv(n, d, eulerphi(d)*stirling(n/d,k,2)); \\ Michel Marcus, Sep 27 2018

a(n) = A001868(n) - 4*A001867(n) + 6*A000031(n) - 4.
From Robert A. Russell, Sep 26 2018: (Start)
a(n) = (k!/n) Sum_{d|n} phi(d) S2(n/d,k), where k=4 is the number of colors and S2 is the Stirling subset number A008277.
G.f.: -Sum_{d>0} (phi(d)/d) * Sum_{j} (-1)^(k-j) * C(k,j) * log(1-j x^d), where k=4 is the number of colors. (End)

A056285 Number of n-bead necklaces with exactly five different colored beads.

Original entry on oeis.org

0, 0, 0, 0, 24, 300, 2400, 15750, 92680, 510312, 2691600, 13794150, 69309240, 343501500, 1686135376, 8221437000, 39901776360, 193054016840, 932142850800, 4495236798162, 21664357535320, 104388120866100, 503044634004000, 2425003924383900, 11696087875731624

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed.

			For n=5, the 24 necklaces are A followed by the 24 permutations of BCDE.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A000031, A001867, A001868, A001869, A008277.

Column k=5 of A087854.

k=5; Table[k!DivisorSum[n,EulerPhi[#]StirlingS2[n/#,k]&]/n,{n,1,30}] (* Robert A. Russell, Sep 26 2018 *)

a(n) = my(k=5); k!*sumdiv(n, d, eulerphi(d)*stirling(n/d, k, 2))/n; \\ Michel Marcus, Sep 27 2018

a(n) = A001869(n) - 5*A001868(n) + 10*A001867(n) - 10*A000031(n) + 5.
From Robert A. Russell, Sep 26 2018: (Start)
a(n) = (k!/n) Sum_{d|n} phi(d) S2(n/d,k), where k=5 is the number of colors and S2 is the Stirling subset number A008277.
G.f.: -Sum_{d>0} (phi(d)/d) * Sum_{j} (-1)^(k-j) * C(k,j) * log(1-j x^d), where k=5 is the number of colors. (End)

A056286 Number of n-bead necklaces with exactly six different colored beads.

Original entry on oeis.org

0, 0, 0, 0, 0, 120, 2160, 23940, 211680, 1643544, 11748240, 79419180, 516257280, 3262443120, 20193277104, 123071707080, 741419995680, 4427490147480, 26264144909520, 155018841055596, 911509010154720, 5344538384445120, 31272099902089200, 182707081122261480

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed.

			For n=6, the 120 necklaces are A followed by the 120 permutations of BCDEF.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A000031, A001867, A001868, A001869, A054625.

Column k=6 of A087854.

k=6; Table[k!DivisorSum[n,EulerPhi[#]StirlingS2[n/#,k]&]/n,{n,1,30}] (* Robert A. Russell, Sep 26 2018 *)

a(n) = A054625(n) - 6*A001869(n) + 15*A001868(n) - 20*A001867(n) + 15*A000031(n) - 6.
From Robert A. Russell, Sep 26 2018: (Start)
a(n) = (k!/n) Sum_{d|n} phi(d) S2(n/d,k), where k=6 is the number of colors and S2 is the Stirling subset number A008277.
G.f.: -Sum_{d>0} (phi(d)/d) * Sum_{j} (-1)^(k-j) * C(k,j) * log(1-j x^d), where k=6 is the number of colors. (End)

A209970 a(n) = 2^n - A000031(n).

Original entry on oeis.org

0, 0, 1, 4, 10, 24, 50, 108, 220, 452, 916, 1860, 3744, 7560, 15202, 30576, 61420, 123360, 247542, 496692, 996088, 1997272, 4003558, 8023884, 16077964, 32212248, 64527436, 129246660, 258847876, 518358120, 1037949256, 2078209980, 4160747500, 8329633416, 16674575056, 33378031536

Offset: 0

David Applegate and N. J. A. Sloane, Mar 17 2012

nonn

a(n) is also the number of 2-divided binary words of length n (see A210109 for definition, see A209919 for further details).
This is a special case of a more general result: Let A={0,1,...,s-1} be an alphabet of size s. Let A* = set of words over A. Let < denote lexicographic order on A*. Let f be the morphism on A* defined by i -> s-i for i in A.
Theorem: Let d(n) be the number of 2-divided words in A* of length n, and let b(n) be the number of rotationally inequivalent necklaces with n beads each in A. Then d(n)+b(n)=s^n.
Proof: Let w in A* have length n. If w is <= all of its cyclic shifts then w contributes to the b(n) count. Otherwise w = uv with vu < uv. But then f(w)=f(u)f(v) with f(u)f(v) < f(v)f(u) is 2-divided, and w contributes to the count in d(n). QED
Cor.: A000031(n) + A209970(n) = 2^n, A001867(n) + A210323(n) = 3^n, A001868(n) + A210424(n) = 4^n.

Cf. A000031, A210109, A209919.

A278639 Number of pairs of orientable necklaces with n beads and up to 3 colors; i.e., turning the necklace over does not leave it unchanged. The turned-over necklace is not included in the count.

Original entry on oeis.org

0, 0, 0, 1, 3, 12, 38, 117, 336, 976, 2724, 7689, 21455, 60228, 168714, 475037, 1338861, 3788400, 10742588, 30556305, 87112059, 248967564, 713032782, 2046325125, 5883428618, 16944975048, 48880471500, 141212377489, 408509453511, 1183275193908, 3431504760514

Offset: 0

Herbert Kociemba, Nov 24 2016

nonn

Number of chiral bracelets of n beads using up to three different colors.

			Example: The 3 orientable necklaces with 4 beads and the colors A, B and C are AABC, BBAC and CCAB. The turned-over necklaces AACB, BBCA and CCBA are not included in the count.
For n=6, the three chiral pairs using just two colors are AABABB-AABBAB, AACACC-AACCAC, and BBCBCC-BBCCBC.  The other 35 use three colors. - _Robert A. Russell_, Sep 24 2018

Column 3 of A293496.
Cf. A059076 (2 colors).
a(n) = (A001867(n) - A182751(n-1)) / 2.
Equals A001867 - A027671.
a(n) = A027671(n) - A182751(n-1).

mx=40;f[x_,k_]:=(1-Sum[EulerPhi[n]*Log[1-k*x^n]/n,{n,1,mx}]-Sum[Binomial[k,i]*x^i,{i,0,2}]/(1-k*x^2))/2;CoefficientList[Series[f[x,3],{x,0,mx}],x]
k=3; Prepend[Table[DivisorSum[n, EulerPhi[#] k^(n/#) &]/(2n) -(k^Floor[(n+1)/2] + k^Ceiling[(n+1)/2])/4, {n, 1, 30}], 0] (* Robert A. Russell, Sep 24 2018 *)

G.f.: k=3, (1 - Sum_{n>=1} phi(n)*log(1 - k*x^n)/n - Sum_{i=0..2} binomial(k,i)*x^i / (1 - k*x^2))/2.

For n > 0, a(n) = -(k^floor((n+1)/2) + k^ceiling((n+1)/2))/4 + (1/2n)* Sum_{d|n} phi(d)*k^(n/d), where k=3 is the maximum number of colors. - Robert A. Russell, Sep 24 2018

A343465 a(n) = -(1/n) * Sum_{d|n} phi(n/d) * (-3)^d.

Original entry on oeis.org

3, -3, 11, -21, 51, -119, 315, -831, 2195, -5883, 16107, -44357, 122643, -341487, 956635, -2690841, 7596483, -21522347, 61171659, -174342165, 498112275, -1426403751, 4093181691, -11767920107, 33891544419, -97764009003, 282429537947, -817028472645, 2366564736723, -6863037262207

Offset: 1

Ilya Gutkovskiy, Apr 16 2021

sign

Cf. A000010, A001867, A032308, A038064, A074763, A261582, A343466, A343467.

Table[-(1/n) Sum[EulerPhi[n/d] (-3)^d, {d, Divisors[n]}], {n, 1, 30}]
nmax = 30; CoefficientList[Series[Sum[EulerPhi[k] Log[1 + 3 x^k]/k, {k, 1, nmax}], {x, 0, nmax}], x] // Rest

G.f.: Sum_{k>=1} phi(k) * log(1 + 3*x^k) / k.
a(n) = -(1/n) * Sum_{k=1..n} (-3)^gcd(n,k).
Product_{n>=1} 1 / (1 - x^n)^a(n) = g.f. for A032308.
Product_{n>=1} (1 - x^n)^a(n) = g.f. for A261582.

A106365 Number of necklaces with n beads of 3 colors, no 2 adjacent beads the same color.

Original entry on oeis.org

3, 3, 2, 6, 6, 14, 18, 36, 58, 108, 186, 352, 630, 1182, 2190, 4116, 7710, 14602, 27594, 52488, 99878, 190746, 364722, 699252, 1342182, 2581428, 4971066, 9587580, 18512790, 35792568, 69273666, 134219796, 260301174, 505294128, 981706830

Offset: 1

Christian G. Bower, Apr 29 2005

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..500
Petros Hadjicostas, Proof of an explicit formula for Bower's CycleBG transform
Index entries for sequences related to necklaces

Column 3 of A208535.

Cf. A000031, A001867.

a[n_] := If[n==1, 3, Sum[EulerPhi[n/d]*(2*(-1)^d+2^d), {d, Divisors[n]}]/n ];
Array[a, 35] (* Jean-François Alcover, Jul 06 2018, after Andrew Howroyd *)

a(n) = if(n==1, 3, sumdiv(n, d, eulerphi(n/d)*(2*(-1)^d + 2^d))/n); \\ Andrew Howroyd, Oct 14 2017

CycleBG transform of (3, 0, 0, 0, ...)
CycleBG transform T(A) = invMOEBIUS(invEULER(Carlitz(A)) + A(x^2) - A) + A.
Carlitz transform T(A(x)) has g.f. 1/(1-sum(k>0, (-1)^(k+1)*A(x^k))).
a(n) = (1/n)*sum_{d divides n} phi(n/d)*A092297(d) (n>1). - Seiichi Azuma, Oct 25 2014
a(n) = -1+(-1)^n+A000031(n) (n>1). - Seiichi Azuma, Oct 25 2014 [Corrected by Petros Hadjicostas, Feb 16 2018.]
From Petros Hadjicostas, Feb 16 2018: (Start)
General formula for the CycleBG transform: T(A)(x) = A(x) - Sum_{k>=0} A(x^(2k+1)) + Sum_{k>=1} (phi(k)/k)*log(Carlitz(A)(x^k)). For a proof, see the links above. (For this sequence, A(x) = 3*x.)
G.f.: Sum_{n>=1} a(n)*x^n = 3*x - 2*x/(1-x^2) - Sum_{n>=1} (phi(n)/n)*log(1-2*x^n) = 3*x - Sum_{n>=1} (phi(n)/n)*(2*log(1+x^n) + log(1-2*x^n)).
(End)

cp's OEIS Frontend

A215327 Smooth necklaces with 3 colors.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A054610 a(n) = Sum_{d|n} phi(d)*3^(n/d).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A056283 Number of n-bead necklaces with exactly three different colored beads.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A056284 Number of n-bead necklaces with exactly four different colored beads.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A056285 Number of n-bead necklaces with exactly five different colored beads.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A056286 Number of n-bead necklaces with exactly six different colored beads.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A209970 a(n) = 2^n - A000031(n).

Views

Author

Keywords

Comments

Crossrefs

A278639 Number of pairs of orientable necklaces with n beads and up to 3 colors; i.e., turning the necklace over does not leave it unchanged. The turned-over necklace is not included in the count.

Views

Author

Keywords

Comments