A001868 -id:A001868 - cp's OEIS frontend

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

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.

A278640 Number of pairs of orientable necklaces with n beads and up to 4 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, 4, 15, 72, 270, 1044, 3795, 14060, 51204, 188604, 694130, 2572920, 9567090, 35758704, 134137875, 505159200, 1908554190, 7233104844, 27486506268, 104713296760, 399817262550, 1529746919604, 5864041395730, 22517964582504, 86607602546220, 333599838189804, 1286742419927070, 4969488707124120, 19215357085867800

Offset: 0

Herbert Kociemba, Nov 24 2016

nonn

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

			Example: For 3 beads and the colors A, B, C and D the 4 orientable necklaces are ABC, ABD, ACD and BCD. The turned-over necklaces ACB, ADB, ADC and BDC are not included in the count.

Column 4 of A293496.
Cf. A059076 (2 colors), A278639 (3 colors).
Equals (A001868 - A056486) / 2 = A001868 - A032275 = A032275 - A056486.

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,4],{x,0,mx}],x]
k=4; 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=4, (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=4 is the maximum number of colors. - Robert A. Russell, Sep 24 2018

A106366 Number of necklaces with n beads of 4 colors, no 2 adjacent beads the same color.

Original entry on oeis.org

4, 6, 8, 24, 48, 130, 312, 834, 2192, 5934, 16104, 44368, 122640, 341802, 956632, 2690844, 7596480, 21524542, 61171656, 174342216, 498112272, 1426419858, 4093181688, 11767920118, 33891544416, 97764131646, 282429537944

Offset: 1

Christian G. Bower, Apr 29 2005

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
Index entries for sequences related to necklaces

Column 4 of A208535.

Cf. A000031, A001868, A226493.

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

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

CycleBG transform of (4, 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 | n} totient(n/d) * (3*(-1)^d + 3^d) for n > 1. - Andrew Howroyd, Mar 12 2017

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

Original entry on oeis.org

4, -6, 24, -66, 208, -676, 2344, -8226, 29144, -104760, 381304, -1398476, 5162224, -19172796, 71582944, -268439586, 1010580544, -3817734596, 14467258264, -54975633768, 209430787824, -799644629556, 3059510616424, -11728124734476, 45035996273872, -173215367702376, 667199944815064

Offset: 1

Ilya Gutkovskiy, Apr 16 2021

sign

Cf. A000010, A001868, A038065, A074763, A261568, A343465, A343467.

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

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

A121775 T(n, k) = Sum_{d|n} phi(n/d)*binomial(d,k) for n>0, T(0, 0) = 1. Triangle read by rows, for 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 3, 5, 3, 1, 4, 8, 7, 4, 1, 5, 9, 10, 10, 5, 1, 6, 15, 20, 21, 15, 6, 1, 7, 13, 21, 35, 35, 21, 7, 1, 8, 20, 36, 60, 71, 56, 28, 8, 1, 9, 21, 42, 86, 126, 126, 84, 36, 9, 1, 10, 27, 59, 130, 215, 253, 210, 120, 45, 10, 1, 11, 21, 55, 165, 330, 462, 462, 330, 165, 55

Offset: 0

Paul D. Hanna, Aug 23 2006

For n>0, (1/n)*Sum_{k=0..n} T(n,k)*(c-1)^k is the number of n-bead necklaces with c colors. See the cross references.

			Triangle begins:
[ 0]  1;
[ 1]  1,  1;
[ 2]  2,  3,  1;
[ 3]  3,  5,  3,   1;
[ 4]  4,  8,  7,   4,   1;
[ 5]  5,  9, 10,  10,   5,   1;
[ 6]  6, 15, 20,  21,  15,   6,   1;
[ 7]  7, 13, 21,  35,  35,  21,   7,   1;
[ 8]  8, 20, 36,  60,  71,  56,  28,   8,  1;
[ 9]  9, 21, 42,  86, 126, 126,  84,  36,  9,  1;
[10] 10, 27, 59, 130, 215, 253, 210, 120, 45, 10, 1;

Cf. A053635 (row sums), A121776 (antidiagonal sums), A054630, A327029.

Cf. A000031 (c=2), A001867 (c=3), A001868 (c=4), A001869 (c=5), A054625 (c=6), A054626 (c=7), A054627 (c=8), A054628 (c=9), A054629 (c=10).

PARI
```
T(n,k)=if(n
				
```

# uses[DivisorTriangle from A327029]
DivisorTriangle(euler_phi, binomial, 13) # Peter Luschny, Aug 24 2019

A210424 Number of 2-divided words of length n over a 4-letter alphabet.

Original entry on oeis.org

0, 0, 6, 40, 186, 816, 3396, 14040, 57306, 233000, 943608, 3813000, 15378716, 61946640, 249260316, 1002158880, 4026527706, 16169288640, 64901712996, 260410648680, 1044535993800, 4188615723280, 16792541033556, 67309233561240, 269746851976156

Offset: 1

N. J. A. Sloane, Mar 21 2012

See A210109 for further information.
It appears that A027377 gives the number of 2-divided words that have a unique division into two parts. - David Scambler, Mar 21 2012
From R. J. Mathar, Mar 25 2012: (Start)
Row sums of the following table which shows how many words of length n over a 4-letter alphabet are 2-divided in k>=1 different ways:
  6;
  20, 20;
  60, 66, 60;
  204, 204, 204, 204;
  670, 690, 676, 690, 670;
  2340, 2340, 2340, 2340, 2340, 2340;
  8160, 8220, 8160, 8226, 8160, 8220, 8160;
First column of the following triangle which shows how many words of length n over a 4-letter alphabet are k-divided:
  6;
  40, 4;
  186, 60, 1;
  816, 374, 44, 0;
  3396, 1960, 450, 12, 0;
  14040, 9103, 3175, 275, 0, 0;
  57306, 40497, 17977, 2915, 66, 0, 0;
  233000, 174127, 91326, 22243, 1318,..
(End)

Cf. A210109, A209970, A001868.

a(n) = 4^n - A001868(n) (see A209970 for proof).

a(1)-a(10) computed by R. J. Mathar, Mar 20 2012

a(13) onwards from N. J. A. Sloane, Mar 21 2012

A161221 Consider necklaces with n beads, each black or white, where the n segments of cord between the beads are each colored red or green; a(n) is the number of different necklaces under the action of the dihedral group D_{2n}.

Original entry on oeis.org

1, 4, 9, 20, 51, 136, 414, 1300, 4371, 15084, 53508, 192700, 703346, 2589304, 9603954, 35824240, 134285331, 505421344, 1909144014, 7234153420, 27488865564, 104717491064, 399826699734, 1529763696820, 5864079144466, 22518031691368, 86607753541164

Offset: 0

H. O. Pollak (hpollak(AT)adsight.com) and N. J. A. Sloane, Nov 21 2009

nonn

If the group is changed to C_n we get A001868.

For n>=4 a(n) is the number of ways to color the edges of a wheel graph using at most 2 colors. A wheel graph is a graph that contains a cycle of order n and every graph vertex is connected to one other graph vertex (which is known as the hub).

			a(4) = 51: the following table shows the number of such necklaces with b black beads, 4-b white beads, r red chord segments and 4-r green chord segments. The sum of the numbers is 51.
b\r 0 1 2 3 4
-------------
0 | 1 1 2 1 1
1 | 1 2 4 2 1
2 | 2 4 7 4 2
3 | 1 2 4 2 1
4 | 1 1 2 1 1
The number of ways to color the edges of a wheel graph (whose vertices are a 4-cycle and a common hub) so that there are exactly 0,1,2,...8 "red" edges is 1,2,6,10,13,10,6,2,1. This corresponds to the sum of the diagonals in the example above.

Eric Weisstein's World of Mathematics, Wheel Graph

Cf. A000029, A000031, A001868, A161222.

with(numtheory); f:= n-> (1/2)*( (1/n) * add( phi(n/d)*2^(2*d), d in divisors(n)) + 2^(n+1) ); # this assumes n>0

Join[{1,4,9,20}, Table[CycleIndex[KSubsetGroup[Automorphisms[Wheel[n]], Edges[Wheel[n]]], s] /. Table[s[i]->2, {i,1,2(n)-2}], {n,5,25}]] (* Geoffrey Critzer, Nov 04 2011 *)

For n>0, a(n) = (1/2)*( (1/n) * Sum_{d|n} (phi(n/d)*2^(2*d)) + 2^(n+1) ).

cp's OEIS Frontend

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

A278640 Number of pairs of orientable necklaces with n beads and up to 4 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

Examples

Crossrefs

Programs

Mathematica

Formula

A106366 Number of necklaces with n beads of 4 colors, no 2 adjacent beads the same color.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A121775 T(n, k) = Sum_{d|n} phi(n/d)*binomial(d,k) for n>0, T(0, 0) = 1. Triangle read by rows, for 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

SageMath

A210424 Number of 2-divided words of length n over a 4-letter alphabet.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A161221 Consider necklaces with n beads, each black or white, where the n segments of cord between the beads are each colored red or green; a(n) is the number of different necklaces under the action of the dihedral group D_{2n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula