cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-6 of 6 results.

A000029 Number of necklaces with n beads of 2 colors, allowing turning over (these are also called bracelets).

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 13, 18, 30, 46, 78, 126, 224, 380, 687, 1224, 2250, 4112, 7685, 14310, 27012, 50964, 96909, 184410, 352698, 675188, 1296858, 2493726, 4806078, 9272780, 17920860, 34669602, 67159050, 130216124, 252745368, 490984488, 954637558, 1857545300
Offset: 0

Views

Author

Keywords

Comments

"Necklaces with turning over allowed" are usually called bracelets. - Joerg Arndt, Jun 10 2016

Examples

			For n=2, the three bracelets are AA, AB, and BB. For n=3, the four bracelets are AAA, AAB, ABB, and BBB. - _Robert A. Russell_, Sep 24 2018
		

References

  • J. L. Fisher, Application-Oriented Algebra (1977), ISBN 0-7002-2504-8, circa p. 215.
  • Martin Gardner, "New Mathematical Diversions from Scientific American" (Simon and Schuster, New York, 1966), pages 245-246.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

Crossrefs

Row sums of triangle in A052307, second column of A081720, column 2 of A051137.
Cf. A000011, A000013, A000031 (turning over not allowed), A001371 (primitive necklaces), A059076, A164090.

Programs

  • Maple
    with(numtheory): A000029 := proc(n) local d,s; if n = 0 then return 1 else if n mod 2 = 1 then s := 2^((n-1)/2) else s := 2^(n/2-2)+2^(n/2-1) fi; for d in divisors(n) do s := s+phi(d)*2^(n/d)/(2*n) od; return s; fi end:
  • Mathematica
    a[0] := 1; a[n_] := Fold[#1 + EulerPhi[#2]2^(n/#2)/(2n) &, If[OddQ[n], 2^((n - 1)/2), 2^(n/2 - 1) + 2^(n/2 - 2)], Divisors[n]]
    mx=40;CoefficientList[Series[(1-Sum[ EulerPhi[n]*Log[1-2*x^n]/n,{n,mx}]+(1+x)^2/(1-2*x^2))/2,{x,0,mx}],x] (* Herbert Kociemba, Nov 02 2016 *)
    a[0] = 1; a[n_] := (1/4)*(Mod[n, 2] + 3)*2^Quotient[n, 2] + DivisorSum[n, EulerPhi[#]*2^(n/#)&]/(2*n); Array[a, 36, 0] (* Jean-François Alcover, Nov 05 2017 *)
  • PARI
    a(n)=if(n<1,!n,(n%2+3)/4*2^(n\2)+sumdiv(n,d,eulerphi(n/d)*2^d)/2/n)
    
  • Python
    from sympy import divisors, totient
    def a(n):
        return 1 if n<1 else ((2**(n//2+1) if n%2 else 3*2**(n//2-1)) + sum(totient(n//d)*2**d for d in divisors(n))//n)//2
    print([a(n) for n in range(51)]) # Indranil Ghosh, Apr 23 2017

Formula

a(n) = Sum_{d divides n} phi(d)*2^(n/d)/(2*n) + either 2^((n - 1)/2) if n odd or 2^(n/2 - 1) + 2^(n/2 - 2) if n even.
G.f.: (1 - Sum_{n>=1} phi(n)*log(1 - 2*x^n)/n + (1 + x)^2/(1 - 2*x^2))/2. - Herbert Kociemba, Nov 02 2016
Equals (A000031 + A164090) / 2 = A000031 - A059076 = A059076 + A164090. - Robert A. Russell, Sep 24 2018
From Richard L. Ollerton, May 04 2021: (Start)
a(0) = 1; a(n) = Sum_{k=1..n} 2^gcd(n,k)/(2*n) + either 2^((n - 1)/2) if n odd or 2^(n/2 - 1) + 2^(n/2 - 2) if n even.
a(0) = 1; a(n) = A000031(n)/2 + (2^floor((n+1)/2) + 2^ceiling((n+1)/2))/4. See A051137. (End)

Extensions

More terms from Christian G. Bower

A027671 Number of necklaces with n beads of 3 colors, allowing turning over.

Original entry on oeis.org

1, 3, 6, 10, 21, 39, 92, 198, 498, 1219, 3210, 8418, 22913, 62415, 173088, 481598, 1351983, 3808083, 10781954, 30615354, 87230157, 249144711, 713387076, 2046856566, 5884491500, 16946569371, 48883660146, 141217160458, 408519019449, 1183289542815
Offset: 0

Views

Author

Keywords

Comments

Number of bracelets of n beads using up to three different colors. - Robert A. Russell, Sep 24 2018

Examples

			For n=2, the six bracelets are AA, AB, AC, BB, BC, and CC. - _Robert A. Russell_, Sep 24 2018
		

References

  • J. L. Fisher, Application-Oriented Algebra (1977), ISBN 0-7002-2504-8, circa p. 215.
  • M. Gardner, "New Mathematical Diversions from Scientific American" (Simon and Schuster, New York, 1966), pp. 245-246.

Crossrefs

a(n) = A081720(n,3), n >= 3. - Wolfdieter Lang, Jun 03 2012
Column 3 of A051137.
a(n) = A278639(n) + A182751(n+1).
Equals A001867 - A278639.

Programs

  • Mathematica
    Needs["Combinatorica`"];  Join[{1}, Table[CycleIndex[DihedralGroup[n], s]/.Table[s[i]->3, {i,1,n}], {n,1,30}]] (* Geoffrey Critzer, Sep 29 2012 *)
    Needs["Combinatorica`"]; Join[{1}, Table[NumberOfNecklaces[n, 3, Dihedral], {n, 30}]] (* T. D. Noe, Oct 02 2012 *)
    mx=40;CoefficientList[Series[(1-Sum[ EulerPhi[n]*Log[1-3*x^n]/n,{n,mx}]+(1+3 x+3 x^2)/(1-3 x^2))/2,{x,0,mx}],x] (* Herbert Kociemba, Nov 02 2016 *)
    t[n_, k_] := (For[t1 = 0; d = 1, d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[d]*k^(n/d)]]; If[EvenQ[n], (t1 + (n/2)*(1+k)*k^(n/2))/(2*n), (t1 + n*k^((n+1)/2))/(2*n)]); a[0] = 1; a[n_] := t[n, 3]; Array[a, 30, 0] (* Jean-François Alcover, Nov 02 2017, after Maple code for A081720 *)
    k=3; Prepend[Table[DivisorSum[n, EulerPhi[#] k^(n/#) &]/(2n) + (k^Floor[(n+1)/2] + k^Ceiling[(n+1)/2])/4, {n, 1, 30}], 1] (* Robert A. Russell, Sep 24 2018 *)
  • PARI
    a(n,k=3) = if(n==0,1,(k^floor((n+1)/2) + k^ceil((n+1)/2))/4 + (1/(2*n))* sumdiv(n, d, eulerphi(d)*k^(n/d) ) );
    vector(55,n,a(n-1)) \\ Joerg Arndt, Oct 20 2019

Formula

G.f.: (1 - Sum_{n>=1} phi(n)*log(1 - 3*x^n)/n + (1+3*x+3*x^2)/(1-3*x^2))/2. - Herbert Kociemba, Nov 02 2016
For n > 0, a(n) = (k^floor((n+1)/2) + k^ceiling((n+1)/2))/4 + (1/(2*n))* Sum_{d|n} phi(d)*k^(n/d), where k=3 is the maximum number of colors. - Robert A. Russell, Sep 24 2018
a(0) = 1; a(n) = (k^floor((n+1)/2) + k^ceiling((n+1)/2))/4 + (1/(2*n))*Sum_{i=1..n} k^gcd(n,i), where k=3 is the maximum number of colors.
(See A075195 formulas.) - Richard L. Ollerton, May 04 2021
2*a(n) = A182751(n+1) + A001867(n), n>0.

Extensions

More terms from Christian G. Bower

A032275 Number of bracelets (turnover necklaces) of n beads of 4 colors.

Original entry on oeis.org

4, 10, 20, 55, 136, 430, 1300, 4435, 15084, 53764, 192700, 704370, 2589304, 9608050, 35824240, 134301715, 505421344, 1909209550, 7234153420, 27489127708, 104717491064, 399827748310, 1529763696820
Offset: 1

Views

Author

Keywords

Examples

			For n=2, the ten bracelets are AA, AB, AC, AD, BB, BC, BD, CC, CD, and DD. - _Robert A. Russell_, Sep 24 2018
		

Crossrefs

Column 4 of A051137.

Programs

  • Mathematica
    mx=40;CoefficientList[Series[(1-Sum[ EulerPhi[n]*Log[1-4*x^n]/n,{n,mx}]+(1+4 x+6 x^2)/(1-4 x^2))/2,{x,0,mx}],x] (* Herbert Kociemba, Nov 02 2016 *)
    k=4; Table[DivisorSum[n, EulerPhi[#] k^(n/#) &]/(2n) + (k^Floor[(n+1)/2] + k^Ceiling[(n+1)/2])/4, {n, 1, 30}] (* Robert A. Russell, Sep 24 2018 *)

Formula

"DIK" (bracelet, indistinct, unlabeled) transform of 4, 0, 0, 0, ...
Equals (A001868(n) + A056486(n)) / 2 = A001868(n) - A278640(n) = A278640(n) + A056486(n), for n>=1.
a(n) = A081720(n,4), n >= 4. - Wolfdieter Lang, Jun 03 2012
G.f.: (1 - Sum_{n>=1} phi(n)*log(1 - 4*x^n)/n + (1+4*x+6*x^2)/(1-4*x^2))/2. - Herbert Kociemba, Nov 02 2016
a(n) = (k^floor((n+1)/2) + k^ceiling((n+1)/2))/4 + (1/(2*n))* Sum_{d|n} phi(d)*k^(n/d), where k=4 is the maximum number of colors. - Robert A. Russell, Sep 24 2018
a(n) = (k^floor((n+1)/2) + k^ceiling((n+1)/2))/4 + (1/(2*n))*Sum_{i=1..n} k^gcd(n,i), where k=4 is the maximum number of colors. (See A075195 formulas.) - Richard L. Ollerton, May 04 2021

A032276 Number of bracelets (turnover necklaces) with n beads of 5 colors.

Original entry on oeis.org

5, 15, 35, 120, 377, 1505, 5895, 25395, 110085, 493131, 2227275, 10196680, 46989185, 218102685, 1017448143, 4768969770, 22440372245, 105966797755, 501938733555, 2384200683816, 11353290089305
Offset: 1

Views

Author

Keywords

Comments

From Petros Hadjicostas, Sep 01 2018: (Start)
The DIK transform of the sequence (c(n): n >= 1), with g.f. C(x) = Sum_{n >= 1} c(n)*x^n, has g.f. -(1/2)*Sum_{m >= 1} (phi(m)/m))*log(1-C(x^m)) + (1 + C(x))^2/(4*(1-C(x^2))) - 1/4.
Here, c(1) = 5 and c(n) = 0 for n >= 2, and thus, C(x) = 5*x. Substituting this to the above g.f., we get that the g.f. of the current sequence is A(x) = Sum_{n >= 1} a(n)*x^n = -(1/2)*Sum_{m >= 1} (phi(m)/m))*log(1-5*x^m) + (1 + 5*x)^2/(4*(1-5*x^2)) - 1/4. This agrees with Herbert Kociemba's g.f. below except for an extra 1 because (1 + (1+5*x+10*x^2)/(1-5*x^2))/2 = 1 + (1 + 5*x)^2/(4*(1-5*x^2)) - 1/4.
(End)

Examples

			For n=2, the 15 bracelets are AA, AB, AC, AD, AE, BB, BC, BD, BE, CC, CD, CE, DD, DE, and EE. - _Robert A. Russell_, Sep 24 2018
		

Crossrefs

Cf. A081720.
Column 5 of A051137.
Cf. A001869 (oriented), A056487 (achiral), A278641 (chiral).

Programs

  • Mathematica
    mx=40;CoefficientList[Series[(1-Sum[ EulerPhi[n]*Log[1-5*x^n]/n,{n,mx}]+(1+5 x+10 x^2)/(1-5 x^2))/2,{x,0,mx}],x] (* Herbert Kociemba, Nov 02 2016 *)
    k=5; Table[DivisorSum[n, EulerPhi[#] k^(n/#) &]/(2n) + (k^Floor[(n+1)/2] + k^Ceiling[(n+1)/2])/4, {n, 1, 30}] (* Robert A. Russell, Sep 24 2018 *)

Formula

"DIK" (bracelet, indistinct, unlabeled) transform of 5, 0, 0, 0, ...
a(n) = A081720(n,5), n >= 1. - Wolfdieter Lang, Jun 03 2012
G.f.: (1 - Sum_{n>=1} phi(n)*log(1 - 5*x^n)/n + (1+5*x+10*x^2)/(1-5*x^2))/2. - Herbert Kociemba, Nov 02 2016
a(n) = (3/2)*5^(n/2) + (1/(2*n))*Sum_{d|n} phi(n/d)*5^d, if n is even, and = (1/2)*5^((n+1)/2) + (1/(2*n))*Sum_{d|n} phi(n/d)*5^d, if n is odd. - Petros Hadjicostas, Sep 01 2018
a(n) = (A001869(n) + A056487(n+1)) / 2 = A278641(n) + A056487(n+1) = A001869(n) - A278641(n). - Robert A. Russell, Oct 13 2018
a(n) = (k^floor((n+1)/2) + k^ceiling((n+1)/2))/4 + (1/(2*n))*Sum_{d divides n} phi(d)*k^(n/d), where k=5 is the maximum number of colors. - Richard L. Ollerton, May 04 2021
a(n) = (k^floor((n+1)/2) + k^ceiling((n+1)/2))/4 + (1/(2*n))*Sum_{i=1..n} k^gcd(n,i), where k=5 is the maximum number of colors. (See A051137.) - Richard L. Ollerton, May 04 2021

A056341 Number of bracelets of length n using a maximum of six different colored beads.

Original entry on oeis.org

6, 21, 56, 231, 888, 4291, 20646, 107331, 563786, 3037314, 16514106, 90782986, 502474356, 2799220041, 15673673176, 88162676511, 497847963696, 2821127825971, 16035812864946, 91404068329560
Offset: 1

Views

Author

Keywords

Comments

Turning over will not create a new bracelet.

Examples

			For n=2, the 21 bracelets are AA, AB, AC, AD, AE, AF, BB, BC, BD, BE, BF, CC, CD, CE, CF, DD, DE, DF, EE, EF, and FF. - _Robert A. Russell_, Sep 24 2018
		

References

  • 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.]

Crossrefs

Cf. a(n) = A081720(n,6), n >= 6. - Wolfdieter Lang, Jun 03 2012
Column 6 of A051137.
Equals (A054625 + A056488) / 2 = A054625 - A278642 = A278642 + A056488.

Programs

  • Mathematica
    mx=40;CoefficientList[Series[(1-Sum[ EulerPhi[n]*Log[1-6*x^n]/n,{n,mx}]+(1+6 x+15 x^2)/(1-6 x^2))/2,{x,0,mx}],x] (* Herbert Kociemba, Nov 02 2016 *)
    k=6; Table[DivisorSum[n, EulerPhi[#] k^(n/#) &]/(2n) + (k^Floor[(n+1)/2] + k^Ceiling[(n+1)/2])/4, {n, 1, 30}] (* Robert A. Russell, Sep 24 2018 *)

Formula

a(n) = Sum_{d|n} phi(d)*6^(n/d)/(2*n);
a(n) = 6^((n+1)/2)/2 for n odd,
(7/4)*6^(n/2) for n even.
G.f.: (1 - Sum_{n>=1} phi(n)*log(1 - 6*x^n)/n + (1+6*x+15*x^2)/(1-6*x^2))/2. - Herbert Kociemba, Nov 02 2016

A321791 Table read by descending antidiagonals: T(n,k) is the number of unoriented cycles (bracelets) of length n using up to k available colors.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 4, 6, 4, 1, 0, 1, 5, 10, 10, 6, 1, 0, 1, 6, 15, 20, 21, 8, 1, 0, 1, 7, 21, 35, 55, 39, 13, 1, 0, 1, 8, 28, 56, 120, 136, 92, 18, 1, 0, 1, 9, 36, 84, 231, 377, 430, 198, 30, 1, 0
Offset: 0

Views

Author

Robert A. Russell, Dec 18 2018

Keywords

Examples

			Table begins with T(0,0):
  1 1  1    1     1      1       1        1        1         1         1 ...
  0 1  2    3     4      5       6        7        8         9        10 ...
  0 1  3    6    10     15      21       28       36        45        55 ...
  0 1  4   10    20     35      56       84      120       165       220 ...
  0 1  6   21    55    120     231      406      666      1035      1540 ...
  0 1  8   39   136    377     888     1855     3536      6273     10504 ...
  0 1 13   92   430   1505    4291    10528    23052     46185     86185 ...
  0 1 18  198  1300   5895   20646    60028   151848    344925    719290 ...
  0 1 30  498  4435  25395  107331   365260  1058058   2707245   6278140 ...
  0 1 46 1219 15084 110085  563786  2250311  7472984  21552969  55605670 ...
  0 1 78 3210 53764 493131 3037314 14158228 53762472 174489813 500280022 ...
For T(3,3)=10, the unoriented cycles are 9 achiral (AAA, AAB, AAC, ABB, ACC, BBB, BBC, BCC, CCC) and 1 chiral pair (ABC-ACB).
		

Crossrefs

Cf. A075195 (oriented), A293496(chiral), A284855 (achiral).
Cf. A051137 (ascending antidiagonals).
Columns 0-6 are A000007, A000012, A000029, A027671, A032275, A032276, and A056341.
Main diagonal gives A081721.

Programs

  • Mathematica
    Table[If[k>0, DivisorSum[k, EulerPhi[#](n-k)^(k/#)&]/(2k) + ((n-k)^Floor[(k+1)/2]+(n-k)^Ceiling[(k+1)/2])/4, 1], {n, 0, 12}, {k, 0, n}] // Flatten

Formula

T(n,k) = [n==0] + [n>0] * (k^floor((n+1)/2) + k^ceiling((n+1)/2)) / 4 + (1/(2*n)) * Sum_{d|n} phi(d) * k^(n/d).
T(n,k) = (A075195(n,k) + A284855(n,k)) / 2.
T(n,k) = A075195(n,k) - A293496(n,k) = A293496(n,k) + A284855(n,k).
Linear recurrence for row n: T(n,k) = Sum_{j=0..n} -binomial(j-n-1,j+1) * T(n,k-1-j) for k >= n + 1.
O.g.f. for column k >= 0: Sum_{n>=0} T(n,k)*x^n = 3/4 + (1 + k*x)^2/(4*(1 - k*x^2)) - (1/2) * Sum_{d >= 1} (phi(d)/d) * log(1 - k*x^d). - Petros Hadjicostas, Feb 07 2021
Showing 1-6 of 6 results.