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-8 of 8 results.

A000048 Number of n-bead necklaces with beads of 2 colors and primitive period n, when turning over is not allowed but the two colors can be interchanged.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 5, 9, 16, 28, 51, 93, 170, 315, 585, 1091, 2048, 3855, 7280, 13797, 26214, 49929, 95325, 182361, 349520, 671088, 1290555, 2485504, 4793490, 9256395, 17895679, 34636833, 67108864, 130150493, 252645135, 490853403, 954437120, 1857283155
Offset: 0

Views

Author

Keywords

Comments

Also, for any m which is a multiple of n, the number of 2m-bead balanced binary necklaces of fundamental period 2n that are equivalent to their complements. [Clarified by Aaron Meyerowitz, Jun 01 2024]
Also binary Lyndon words of length n with an odd number of 1's (for n>=1).
Also number of binary irreducible polynomials of degree n having trace 1.
Also number of binary irreducible polynomials of degree n having linear coefficient 1 (this is the same as the trace-1 condition, as the reciprocal of an irreducible polynomial is again irreducible).
Also number of binary irreducible self-reciprocal polynomials of degree 2*n; there is no such polynomial for odd degree except for x+1.
Also number of binary vectors (x_1,...x_n) satisfying Sum_{i=1..n} i*x_i = 1 (mod n+1) = size of Varshamov-Tenengolts code VT_1(n).
Also the number of dynamical cycles of period 2n of a threshold Boolean automata network which is a quasi-minimal negative circuit of size nq where q is odd and which is updated in parallel. - Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Mar 03 2009
Also the number of 3-elements orbits of the symmetric group S3 action on irreducible polynomials of degree 2n, n>1, over GF(2). - Jean Francis Michon, Philippe Ravache (philippe.ravache(AT)univ-rouen.fr), Oct 04 2009
Conjecture: Also the number of caliber-n cycles of Zagier-reduced indefinite binary quadratic forms with sum invariant equal to s, where (s-1)/n is an odd integer. - Barry R. Smith, Dec 14 2014
The Metropolis, Stein, Stein (1973) reference on page 31 Table II lists a(k) for k = 2 to 15 and is actually for sequence A056303 since there a(k) = 0 for k<2. - Michael Somos, Dec 20 2014

Examples

			a(5) = 3 corresponding to the necklaces 00001, 00111, 01011.
a(6) = 5 from 000001, 000011, 000101, 000111, 001011.
		

References

  • B. D. Ginsburg, On a number theory function applicable in coding theory, Problemy Kibernetiki, No. 19 (1967), pp. 249-252.
  • H. Kawakami, Table of rotation sequences of x_{n+1} = x_n^2 - lambda, pp. 73-92 of G. Ikegami, Editor, Dynamical Systems and Nonlinear Oscillations, Vol. 1, World Scientific, 1986.
  • Robert M. May, "Simple mathematical models with very complicated dynamics." Nature, Vol. 261, June 10, 1976, pp. 459-467; reprinted in The Theory of Chaotic Attractors, pp. 85-93. Springer, New York, NY, 2004. The sequences listed in Table 2 are A000079, A027375, A000031, A001037, A000048, A051841. - N. J. A. Sloane, Mar 17 2019
  • 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).

Crossrefs

Like A000013, but primitive necklaces. Half of A064355.
Equals A042981 + A042982.
Cf. also A001037, A056303.
Very close to A006788 [Fisher, 1989].
bisection (odd terms) is A131203

Programs

  • Maple
    with(numtheory); A000048 := proc(n) local d,t1; if n = 0 then RETURN(1) else t1 := 0; for d from 1 to n do if n mod d = 0 and d mod 2 = 1 then t1 := t1+mobius(d)*2^(n/d)/(2*n); fi; od; RETURN(t1); fi; end;
  • Mathematica
    a[n_] := Total[ MoebiusMu[#]*2^(n/#)& /@ Select[ Divisors[n], OddQ]]/(2n); a[0] = 1; Table[a[n], {n,0,35}] (* Jean-François Alcover, Jul 21 2011 *)
    a[ n_] := If[ n < 1, Boole[n == 0], DivisorSum[ n, MoebiusMu[#] 2^(n/#) &, OddQ] / (2 n)]; (* Michael Somos, Dec 20 2014 *)
  • PARI
    A000048(n) = sumdiv(n,d,(d%2)*(moebius(d)*2^(n/d)))/(2*n) \\ Michael B. Porter, Nov 09 2009
    
  • PARI
    L(n, k) = sumdiv(gcd(n,k), d, moebius(d) * binomial(n/d, k/d) );
    a(n) = sum(k=0, n, if( (n+k)%2==1, L(n, k), 0 ) ) / n;
    vector(55,n,a(n)) \\ Joerg Arndt, Jun 28 2012
    
  • Python
    from sympy import divisors, mobius
    def a(n): return 1 if n<1 else sum(mobius(d)*2**(n//d) for d in divisors(n) if d%2)//(2*n) # Indranil Ghosh, Apr 28 2017

Formula

a(n) = (1/(2*n)) * Sum_{odd d divides n} mu(d)*2^(n/d), where mu is the Mobius function A008683.
a(n) = A056303(n) for all integer n>=2. - Michael Somos, Dec 20 2014
Sum_{k dividing m for which m/k is odd} k*a(k) = 2^(m-1). (This explains the observation that the sequence is very close to A006788. Unless m has some nontrivial odd divisors that are small relative to m, the term m*a(m) will dominate the sum. Thus, we see for instance that a(n) = A006788(n) when n has one of the forms 2^m or 2^m*p where p is an odd prime with a(2^m) < p.) - Barry R. Smith, Oct 24 2015
A000013(n) = Sum_{d|n} a(d). - Robert A. Russell, Jun 09 2019
G.f.: 1 + Sum_{k>=1} mu(2*k)*log(1 - 2*x^k)/(2*k). - Ilya Gutkovskiy, Nov 11 2019

Extensions

Additional comments from Frank Ruskey, Dec 13 1999

A130293 Number of necklaces of n beads with up to n colors, with cyclic permutation {1,..,n} of the colors taken to be equivalent.

Original entry on oeis.org

1, 2, 5, 20, 129, 1316, 16813, 262284, 4783029, 100002024, 2357947701, 61917406672, 1792160394049, 56693913450992, 1946195068379933, 72057594071484456, 2862423051509815809, 121439531097819321972, 5480386857784802185957, 262144000000051200072048, 13248496640331026150086281
Offset: 1

Views

Author

Wouter Meeussen, Aug 06 2007, Aug 14 2007

Keywords

Comments

From Olivier Gérard, Aug 01 2016: (Start)
Equivalent to the definition: number of classes of endofunctions of [n] under rotation and translation mod n.
Classes can be of size between n and n^2 depending on divisibility properties of n.
n n 2n 3n ... n^2
--------------------------
1 1
2 2
3 3 2
4 4 2 14
5 5 0 124
6 6 6 22 1282
7 7 0 16806
For prime n, the only possible class sizes are n and n^2, the classes of size n are the n arithmetical progression modulo n so #(c-n)=n, #(c-n^2)=(n^n - n*n)/n^2 = n^(n-2)-1 and a(n) = n^(n-2)+n-1.
(End)

Examples

			The 5 necklaces for n=3 are: 000, 001, 002, 012 and 021.
		

Crossrefs

Cf. A081720.
Cf. A000312: All endofunctions.
Cf. A000169: Classes under translation mod n.
Cf. A001700: Classes under sort.
Cf. A056665: Classes under rotation.
Cf. A168658: Classes under complement to n+1.
Cf. A130293: Classes under translation and rotation.
Cf. A081721: Classes under rotation and reversal.
Cf. A275549: Classes under reversal.
Cf. A275550: Classes under reversal and complement.
Cf. A275551: Classes under translation and reversal.
Cf. A275552: Classes under translation and complement.
Cf. A275553: Classes under translation, complement and reversal.
Cf. A275554: Classes under translation, rotation and complement.
Cf. A275555: Classes under translation, rotation and reversal.
Cf. A275556: Classes under translation, rotation, complement and reversal.
Cf. A275557: Classes under rotation and complement.
Cf. A275558: Classes under rotation, complement and reversal.

Programs

  • Mathematica
    tor8={};ru8=Thread[ i_ ->Table[ Mod[i+k,8],{k,8}]];Do[idi=IntegerDigits[k,8,8];try= Function[w, First[temp=Union[Join @@(Table[RotateRight[w,k],{k,8}]/.#&)/@ ru8]]][idi];If[idi===try, tor8=Flatten[ {tor8,{{Length[temp],idi}}},1] ],{k,0,8^8-1}];
    a[n_]:=Sum[d EulerPhi[d]n^(n/d),{d,Divisors[n]}]/n^2; Array[a,21] (* Stefano Spezia, May 21 2024 *)
  • PARI
    a(n) = sumdiv(n, d, d*eulerphi(d)*n^(n/d))/n^2; \\ Michel Marcus, Aug 05 2016

Formula

a(n) = (1/n^2)*Sum_{d|n} d*phi(d)*n^(n/d). - Vladeta Jovovic, Aug 14 2007, Aug 24 2007

A002076 Number of equivalence classes of base-3 necklaces of length n, where necklaces are considered equivalent under both rotations and permutations of the symbols.

Original entry on oeis.org

1, 1, 2, 3, 6, 9, 26, 53, 146, 369, 1002, 2685, 7434, 20441, 57046, 159451, 448686, 1266081, 3588002, 10195277, 29058526, 83018783, 237740670, 682196949, 1961331314, 5648590737, 16294052602, 47071590147, 136171497650, 394427456121, 1143839943618, 3320824711205
Offset: 0

Views

Author

Keywords

Comments

Number of set partitions of an oriented cycle of length n with 3 or fewer subsets. - Robert A. Russell, Nov 05 2018

Examples

			E.g., a(2) = 2 as there are two equivalence classes of the 9 strings {00,01,02,10,11,12,20,21,22}: {00,11,22} form one equivalence class and {01,02,10,12,20,21} form the other. To see that (for example) 01 and 02 are equivalent, rotate 01 to 10 and then subtract 1 mod 3 from each element in 10 to get 02.
For a(6)=26, there are 18 achiral patterns (AAAAAA, AAAAAB, AAAABB, AAABAB, AAABBB, AABAAB, AABABB, ABABAB, AAAABC, AAABAC, AAABCB, AABAAC, AABBCC, AABCBC, AABCCB, ABABAC, ABACBC, ABCABC) and 8 chiral patterns in four pairs (AAABBC-AAABCC, AABABC-AABCAC, AABACB-AABCAB, AABACC-AABBAC). - _Robert A. Russell_, Nov 05 2018
		

References

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

Crossrefs

Cf. A056353 (unoriented), A320743 (chiral), A182522 (achiral).

Programs

  • Mathematica
    Adn[d_, n_] := Module[{ c, t1, t2}, t2 = 0; For[c = 1, c <= d, c++, If[Mod[d, c] == 0 , t2 = t2 + (x^c/c)*(E^(c*z) - 1)]]; t1 = E^t2; t1 = Series[t1, {z, 0, n+1}]; Coefficient[t1, z, n]*n!]; Pn[n_] := Module[{ d, e, t1}, t1 = 0; For[d = 1, d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[d]*Adn[d, n/d]/n]]; t1/(1 - x)]; Pnq[n_, q_] := Module[{t1}, t1 = Series[Pn[n], {x, 0, q+1}] ; Coefficient[t1, x, q]]; a[n_] := Pnq[n, 3]; Print[1]; Table[Print[an = a[n]]; an, {n, 1, 28}] (* Jean-François Alcover, Oct 04 2013, after N. J. A. Sloane's Maple code *)
    (* This Mathematica program uses Gilbert and Riordan's recurrence formula, which they recommend for calculations: *)
    Adn[d_, n_] := Adn[d, n] = If[1==n, DivisorSum[d, x^# &],
      Expand[Adn[d, 1] Adn[d, n-1] + D[Adn[d, n-1], x] x]];
    Join[{1},Table[SeriesCoefficient[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &] /(n (1 - x)), {x, 0, 3}], {n,40}]]  (* Robert A. Russell, Feb 24 2018 *)
    From Robert A. Russell, May 29 2018: (Start)
    Join[{1},Table[(1/n) DivisorSum[n, EulerPhi[#] Which[Divisible[#, 6], 3 StirlingS2[n/#+2, 3] - 9 StirlingS2[n/#+1, 3] + 6 StirlingS2[n/#, 3], Divisible[#, 3], 2 StirlingS2[n/#+2, 3] - 7 StirlingS2[n/#+1, 3] + 6 StirlingS2[n/#, 3], Divisible[#, 2], 2 StirlingS2[n/#+2, 3] - 6 StirlingS2[n/#+1, 3] + 4 StirlingS2[n/#, 3], True, StirlingS2[n/#+2, 3] - 4 StirlingS2[n/#+1, 3] + 4 StirlingS2[n/#, 3]] &], {n,40}]] (* or *)
    mx = 40; CoefficientList[Series[1 - Sum[(EulerPhi[d] / d) Which[
      Divisible[d, 6], Log[1 - 3x^d], Divisible[d, 3], (Log[1 - 3x^d] +
      Log[1 - x^d]) / 2, Divisible[d, 2], 2 Log[1 - 3x^d] / 3, True, (Log[1 - 3x^d] + 3 Log[1 - x^d]) / 6], {d, 1, mx}], {x, 0, mx}], x]
    (End)
    (* Adnk(n,d,k) is coefficient of x^k in A(d,n)(x) from Gilbert & Riordan *)
    Adnk[d_,n_,k_] := Adnk[d,n,k] = If[n>0 && k>0, Adnk[d,n-1,k]k + DivisorSum[d,Adnk[d,n-1,k-#]&], Boole[n==0 && k==0]]
    k=3; Join[{1},Table[Sum[DivisorSum[n,EulerPhi[#] Adnk[#,n/#,j] &],{j,k}]/n,{n,40}]] (* Robert A. Russell, Nov 05 2018 *)

Formula

Reference gives formula.
From Robert A. Russell, May 29 2018: (Start)
For n>0, a(n) = (1/n) * Sum_{d|n} phi(d) * ([d==0 mod 6] * (3*S2(n/d+2, 3) - 9*S2(n/d+1, 3) + 6*S2(n/d, 3)) + [d==3 mod 6] * (2*S2(n/d+2, 3) - 7*S2(n/d+1, 3) + 6*S2(n/d, 3)) + [d==2 mod 6 | d==4 mod 6] * (2*S2(n/d+2, 3) - 6*S2(n/d+1, 3) + 4*S2(n/d, 3)) + [d==1 mod 6 | d=5 mod 6] * (S2(n/d+2, 3) - 4*S2(n/d+1, 3) + 4*S2(n/d, 3))), where S2(n,k) is the Stirling subset number, A008277.
G.f.: 1 - Sum_{d>0} (phi(d) / d) * ([d==0 mod 6] * log(1-3x^d) +
[d==3 mod 6] * (log(1-3x^d) + log(1-x^d)) / 2 +
[d==2 mod 6 | d==4 mod 6] * 2*log(1-3x^d) / 3 +
[d==1 mod 6 | d=5 mod 6] * (log(1-3x^d) + 3*log(1-x^d)) / 6).
(End)

Extensions

Better description and more terms from Mark Weston (mweston(AT)uvic.ca), Oct 06 2001
a(0)=1 prepended by Robert A. Russell, Nov 05 2018

A107424 Triangle read by rows: T(n, k) is the number of primitive (period n) n-bead necklace structures with k different colors. Only includes structures that contain all k colors.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 5, 2, 1, 0, 5, 17, 13, 3, 1, 0, 9, 43, 50, 20, 3, 1, 0, 16, 124, 220, 136, 36, 4, 1, 0, 28, 338, 866, 773, 296, 52, 4, 1, 0, 51, 941, 3435, 4280, 2303, 596, 78, 5, 1, 0, 93, 2591, 13250, 22430, 16317, 5817, 1080, 105, 5, 1, 0, 170, 7234, 51061
Offset: 1

Views

Author

David Wasserman, May 26 2005

Keywords

Comments

This classification is concerned with which beads are the same color, not with the colors themselves, so bbabcd is the same structure as aabacd. Cyclic permutations are also the same structure, e.g. abacda is also the same structure. However, order matters: the reverse of aabacd is equivalent to aabcad, which is also on the list.

Examples

			T(6, 4) = 13: {aaabcd, aabacd, aabcad, abacad, aabbcd, aabcbd, aabcdb, aacbbd, aacbdb, ababcd, abacbd, acabdb, abcabd}.
From _Andrew Howroyd_, Apr 09 2017 (Start)
Triangle starts:
1
0  1
0  1   1
0  2   2    1
0  3   5    2    1
0  5  17   13    3    1
0  9  43   50   20    3   1
0 16 124  220  136   36   4  1
0 28 338  866  773  296  52  4 1
0 51 941 3435 4280 2303 596 78 5 1
(End)
		

Crossrefs

Columns 2-6 are A056303, A056304, A056305, A056306, A056307.
Partial row sums include A000048, A002075, A056300, A056301, A056302.
Row sums are A276547.

Programs

  • Mathematica
    A[d_, n_] := A[d, n] = Which[n == 0, 1, n == 1, DivisorSum[d, x^# &], d == 1, Sum[StirlingS2[n, k] x^k, {k, 0, n}], True, Expand[A[d, 1] A[d, n-1] + D[A[d, n-1], x] x]];
    B[n_, k_] := Coefficient[DivisorSum[n, EulerPhi[#] A[#, n/#]&]/n/x, x, k];
    T[n_, k_] := DivisorSum[n, MoebiusMu[n/#] B[#, k]&];
    Table[T[n, k], {n, 1, 12}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Jun 06 2018, after Andrew Howroyd and Robert A. Russell *)
  • PARI
    \\ here R(n) is A152175 as square matrix.
    R(n) = {Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}
    T(n) = {my(M=R(n)); matrix(n, n, i, k, sumdiv(i, d, moebius(i/d)*M[d,k]))}
    { my(A=T(10)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Jan 09 2020

Formula

T(n, k) = Sum_{d|n} mu(n/d) * A152175(d, k). - Andrew Howroyd, Apr 09 2017

A056304 Number of primitive (period n) n-bead necklace structures using exactly three different colored beads.

Original entry on oeis.org

0, 0, 1, 2, 5, 17, 43, 124, 338, 941, 2591, 7234, 20125, 56407, 158349, 446492, 1262225, 3580330, 10181479, 29031306, 82968799, 237642659, 682014587, 1960974220, 5647919640, 16292741605, 47069104274, 136166647110, 394418199725, 1143821887473, 3320790074371
Offset: 1

Views

Author

Keywords

Comments

Turning over the necklace is not allowed. Colors may be permuted without changing the necklace structure.

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

Formula

a(n) = Sum_{d|n} mu(d)*A056296(n/d), where mu = A008683 is the Möbius function.
a(n) = A002075(n) - A000048(n).

Extensions

a(28)-a(31) from Pontus von Brömssen, Aug 04 2024

A056362 Number of primitive (period n) bracelet structures using a maximum of three different colored beads.

Original entry on oeis.org

1, 1, 1, 2, 4, 8, 18, 39, 94, 222, 572, 1463, 3934, 10584, 29211, 80808, 226430, 636320, 1800318, 5107479, 14548360, 41538874, 118927919, 341187047, 980838750, 2824561080, 8147547156, 23536592010, 68087313892, 197216119544, 571924673368, 1660419530055, 4825587979390
Offset: 0

Views

Author

Keywords

Comments

Turning over will not create a new bracelet. Permuting the colors of the beads will not change the structure.

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

Formula

a(n) = Sum_{d|n} mu(d)*A056353(n/d) for n > 0.
a(n) = Sum_{k=1..3} A276543(n, k) for n > 0. - Andrew Howroyd, Oct 26 2019

Extensions

a(0)=1 prepended and terms a(28) and beyond from Andrew Howroyd, Oct 26 2019

A056305 Number of primitive (period n) n-bead necklace structures using exactly four different colored beads.

Original entry on oeis.org

0, 0, 0, 1, 2, 13, 50, 220, 866, 3435, 13250, 51061, 194810, 742601, 2823764, 10738660, 40843370, 155493872, 592614050, 2261622287, 8643289484, 33080907357, 126797503250, 486710920300, 1870851589552
Offset: 1

Views

Author

Keywords

Comments

Turning over the necklace is not allowed. Colors may be permuted without changing the necklace structure.

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

Column 4 of A107424.
Cf. A056289.

Formula

Sum mu(d)*A056297(n/d) where d|n. Alternatively, A056300(n)-A002075(n)..

A328742 Number of n-bead necklace structures which are not self-equivalent under a nonzero rotation using a maximum of three different colored beads.

Original entry on oeis.org

1, 1, 0, 1, 2, 8, 17, 52, 130, 363, 968, 2684, 7338, 20440, 56836, 159424, 448130, 1266080, 3586479, 10195276, 29054568, 83018624, 237729932, 682196948, 1961301330, 5648590728, 16293970840, 47071589049, 136171269780, 394427456120, 1143839302904, 3320824711204
Offset: 0

Views

Author

Andrew Howroyd, Oct 26 2019

Keywords

Comments

Permuting the colors does not change the structure.

Crossrefs

Formula

a(n) = Sum_{k=1..3} A327693(n, k) for n > 0.
a(p) = A002075(p) for prime p >= 5.
Showing 1-8 of 8 results.