A000029 -id:A000029 - cp's OEIS frontend

A000031 Number of n-bead necklaces with 2 colors when turning over is not allowed; also number of output sequences from a simple n-stage cycling shift register; also number of binary irreducible polynomials whose degree divides n.

1, 2, 3, 4, 6, 8, 14, 20, 36, 60, 108, 188, 352, 632, 1182, 2192, 4116, 7712, 14602, 27596, 52488, 99880, 190746, 364724, 699252, 1342184, 2581428, 4971068, 9587580, 18512792, 35792568, 69273668, 134219796, 260301176, 505294128, 981706832

Offset: 0

N. J. A. Sloane

Also a(n)-1 is the number of 1's in the truth table for the lexicographically least de Bruijn cycle (Fredricksen).
In music, a(n) is the number of distinct classes of scales and chords in an n-note equal-tempered tuning system. - Paul Cantrell, Dec 28 2011
Also, minimum cardinality of an unavoidable set of length-n binary words (Champarnaud, Hansel, Perrin). - Jeffrey Shallit, Jan 10 2019
(1/n) * Dirichlet convolution of phi(n) and 2^n, n>0. - Richard L. Ollerton, May 06 2021
From Jianing Song, Nov 13 2021: (Start)
a(n) is even for n != 0, 2. Proof: write n = 2^e * s with odd s, then a(n) * s = Sum_{d|s} Sum_{k=0..e} phi((2^e*s)/(2^k*d)) * 2^(2^k*d-e) = Sum_{d|s} Sum_{k=0..e-1} phi(s/d) * 2^(2^k*d-k-1) + Sum_{d|s} phi(s/d) * 2^(2^e*d-e) == Sum_{k=0..e-1} 2^(2^k*s-k-1) + 2^(2^e*s-e) == Sum_{k=0..min{e-1,1}} 2^(2^k*s-k-1) (mod 2). a(n) is odd if and only if s = 1 and e-1 = 0, or n = 2.
a(n) == 2 (mod 4) if and only if n = 1, 4 or n = 2*p^e with prime p == 3 (mod 4).
a(n) == 4 (mod 8) if and only if n = 2^e, 3*2^e for e >= 3, or n = p^e, 4*p^e != 12 with prime p == 3 (mod 4), or n = 2s where s is an odd number such that phi(s) == 4 (mod 8). (End)

			For n=3 and n=4 the necklaces are {000,001,011,111} and {0000,0001,0011,0101,0111,1111}.
The analogous shift register sequences are {000..., 001001..., 011011..., 111...} and {000..., 00010001..., 00110011..., 0101..., 01110111..., 111...}.

S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, pp. 120, 172.
May, Robert M. "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).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.112(a).

Seiichi Manyama, Table of n, a(n) for n = 0..3333 (first 201 terms from T. D. Noe)
Nicolás Álvarez, Verónica Becher, Martín Mereb, Ivo Pajor, and Carlos Miguel Soto, On extremal factors of de Bruijn-like graphs, arXiv:2308.16257 [math.CO], 2023. See references.
Joerg Arndt, Matters Computational (The Fxtbook), p. 151, pp. 379-383.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
J.-M. Champarnaud, G. Hansel, and D. Perrin, Unavoidable sets of constant length, Internat. J. Alg. Comput. 14 (2004), 241-251.
Vladimir Dotsenko and Irvin Roy Hentzel, On the conjecture of Kashuba and Mathieu about free Jordan algebras, arXiv:2507.00437 [math.RA], 2025. See p. 14.
James East and Ron Niles, Integer polygons of given perimeter, arXiv:1710.11245 [math.CO], 2017.
S. N. Ethier and J. Lee, Parrondo games with spatial dependence, arXiv preprint arXiv:1202.2609 [math.PR], 2012.
S. N. Ethier, Counting toroidal binary arrays, arXiv preprint arXiv:1301.2352 [math.CO], 2013 and J. Int. Seq. 16 (2013) #13.4.7.
N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see pages 18, 64.
H. Fredricksen, The lexicographically least de Bruijn cycle, J. Combin. Theory, 9 (1970) 1-5.
Harold Fredricksen, An algorithm for generating necklaces of beads in two colors, Discrete Mathematics, Volume 61, Issues 2-3, September 1986, Pages 181-188.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 2
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 130
Juhani Karhumäki, S. Puzynina, M. Rao, and M. A. Whiteland, On cardinalities of k-abelian equivalence classes, arXiv preprint arXiv:1605.03319 [math.CO], 2016.
Abraham Lempel, On extremal factors of the de Bruijn graph, J. Combinatorial Theory Ser. B 11 1971 17--27. MR0276126 (43 #1874).
Karyn McLellan, Periodic coefficients and random Fibonacci sequences, Electronic Journal of Combinatorics, 20(4), 2013, #P32.
Johannes Mykkeltveit, A proof of Golomb's conjecture for the de Bruijn graph, J. Combinatorial Theory Ser. B 13 (1972), 40-45. MR0323629 (48 #1985).
Matthew Parker, The first 25K terms (7-Zip compressed file) [a large file]
J. Riordan, Letter to N. J. A. Sloane, Jul. 1978
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Ville Salo, Universal gates with wires in a row, arXiv:1809.08050 [math.GR], 2018.
J. A. Siehler, The Finite Lamplighter Groups: A Guided Tour, College Mathematics Journal, Vol. 43, No. 3 (May 2012), pp. 203-211.
N. J. A. Sloane, On single-deletion-correcting codes
N. J. A. Sloane, On single-deletion-correcting codes, arXiv:math/0207197 [math.CO], 2002; in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.
David Thomson, Musical Polygons, Mathematics Today, Vol. 57, No. 2 (April 2021), pp. 50-51.
R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.
A. M. Uludag, A. Zeytin and M. Durmus, Binary Quadratic Forms as Dessins, 2012.
Eric Weisstein's World of Mathematics, Necklace
Wolfram Research, Number of necklaces
Index entries for "core" sequences
Index entries for sequences related to necklaces

Column 2 of A075195.
Cf. A001037 (primitive solutions to same problem), A014580, A000016, A000013, A000029 (if turning over is allowed), A000011, A001371, A058766.
Rows sums of triangle in A047996.
Dividing by 2 gives A053634.
A008965(n) = a(n) - 1 allowing different offsets.
Cf. A008965, A053635, A052823, A100447 (bisection).
Cf. A000010.

a000031 0 = 1
a000031 n = (`div` n) $ sum $
   zipWith (*) (map a000010 divs) (map a000079 $ reverse divs)
   where divs = a027750_row n
-- Reinhard Zumkeller, Mar 21 2013

with(numtheory); A000031 := proc(n) local d,s; if n = 0 then RETURN(1); else s := 0; for d in divisors(n) do s := s+phi(d)*2^(n/d); od; RETURN(s/n); fi; end; [ seq(A000031(n), n=0..50) ];

a[n_] := Sum[If[Mod[n, d] == 0, EulerPhi[d] 2^(n/d), 0], {d, 1, n}]/n
a[n_] := Fold[#1 + 2^(n/#2) EulerPhi[#2] &, 0, Divisors[n]]/n (* Ben Branman, Jan 08 2011 *)
Table[Expand[CycleIndex[CyclicGroup[n], t] /. Table[t[i]-> 2, {i, 1, n}]], {n,0, 30}] (* Geoffrey Critzer, Mar 06 2011*)
a[0] = 1; a[n_] := DivisorSum[n, EulerPhi[#]*2^(n/#)&]/n; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 03 2016 *)
mx=40; CoefficientList[Series[1-Sum[EulerPhi[i] Log[1-2*x^i]/i,{i,1,mx}],{x,0,mx}],x] (*Herbert Kociemba, Oct 29 2016 *)

{A000031(n)=if(n==0,1,sumdiv(n,d,eulerphi(d)*2^(n/d))/n)} \\ Randall L Rathbun, Jan 11 2002

from sympy import totient, divisors
def A000031(n): return sum(totient(d)*(1<Chai Wah Wu, Nov 16 2022

a(n) = (1/n)*Sum_{ d divides n } phi(d)*2^(n/d) = A053635(n)/n, where phi is A000010.
Warning: easily confused with A001037, which has a similar formula.
G.f.: 1 - Sum_{n>=1} phi(n)*log(1 - 2*x^n)/n. - Herbert Kociemba, Oct 29 2016
a(0) = 1; a(n) = (1/n) * Sum_{k=1..n} 2^gcd(n,k). - Ilya Gutkovskiy, Apr 16 2021
a(0) = 1; a(n) = (1/n)*Sum_{k=1..n} 2^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 06 2021
Dirichlet g.f.: f(s+1) * (zeta(s)/zeta(s+1)), where f(s) = Sum_{n>=1} 2^n/n^s. - Jianing Song, Nov 13 2021

There is an error in Fig. M3860 in the 1995 Encyclopedia of Integer Sequences: in the third line, the formula for A000031 = M0564 should be (1/n) sum phi(d) 2^(n/d).

A029744 Numbers of the form 2^n or 3*2^n.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576, 32768, 49152, 65536, 98304, 131072, 196608, 262144, 393216, 524288, 786432, 1048576, 1572864, 2097152, 3145728, 4194304

Offset: 1

N. J. A. Sloane

This entry is a list, and so has offset 1. WARNING: However, in this entry several comments, formulas and programs seem to refer to the original version of this sequence which had offset 0. - M. F. Hasler, Oct 06 2014
Number of necklaces with n-1 beads and two colors that are the same when turned over and hence have reflection symmetry. [edited by Herbert Kociemba, Nov 24 2016]
The subset {a(1),...,a(2k)} contains all proper divisors of 3*2^k. - Ralf Stephan, Jun 02 2003
Let k = any nonnegative integer and j = 0 or 1. Then n+1 = 2k + 3j and a(n) = 2^k*3^j. - Andras Erszegi (erszegi.andras(AT)chello.hu), Jul 30 2005
Smallest number having no fewer prime factors than any predecessor, a(0)=1; A110654(n) = A001222(a(n)); complement of A116451. - Reinhard Zumkeller, Feb 16 2006
A093873(a(n)) = 1. - Reinhard Zumkeller, Oct 13 2006
a(n) = a(n-1) + a(n-2) - gcd(a(n-1), a(n-2)), n >= 3, a(1)=2, a(2)=3. - Ctibor O. Zizka, Jun 06 2009
Where records occur in A048985: A193652(n) = A048985(a(n)) and A193652(n) < A048985(m) for m < a(n). - Reinhard Zumkeller, Aug 08 2011
A002348(a(n)) = A000079(n-3) for n > 2. - Reinhard Zumkeller, Mar 18 2012
Without initial 1, third row in array A228405. - Richard R. Forberg, Sep 06 2013
Also positions of records in A048673. A246360 gives the record values. - Antti Karttunen, Sep 23 2014
Known in numerical mathematics as "Bulirsch sequence", used in various extrapolation methods for step size control. - Peter Luschny, Oct 30 2019
For n > 1, squares of the terms can be expressed as the sum of two powers of two: 2^x + 2^y. - Karl-Heinz Hofmann, Sep 08 2022

Vincenzo Librandi, Table of n, a(n) for n = 1..2000
Spencer Daugherty, Pamela E. Harris, Ian Klein, and Matt McClinton, Metered Parking Functions, arXiv:2406.12941 [math.CO], 2024. See pp. 11, 22.
Michael De Vlieger, Thomas Scheuerle, Rémy Sigrist, N. J. A. Sloane, and Walter Trump, The Binary Two-Up Sequence, arXiv:2209.04108 [math.CO], Sep 11 2022.
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
Guo-Niu Han, Enumeration of Standard Puzzles. [Cached copy]
John P. McSorley and Alan H. Schoen, Rhombic tilings of (n,k)-ovals, (n, k, lambda)-cyclic difference sets, and related topics, Discrete Math., 313 (2013), 129-154. - From _N. J. A. Sloane_, Nov 26 2012
Index entries for linear recurrences with constant coefficients, signature (0,2).
Index entries for sequences related to necklaces

Cf. A056493, A038754, A063759. Union of A000079 and A007283.
First differences are in A016116(n-1).
Cf. A082125, A094958, A048739, A048985, A193652, A048673, A064216, A246360, A354785.
Row sums of the triangle in sequence A119963. - John P. McSorley, Aug 31 2010
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent. There may be minor differences from (s(n)) at the start, and a shift of indices. A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A060482 (s(n)-3); A136252 (s(n)-3); A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4);   A354785 (3*s(n)), A061776 (3*s(n)-6); A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

a029744 n = a029744_list !! (n-1)
a029744_list = 1 : iterate
   (\x -> if x `mod` 3 == 0 then 4 * x `div` 3 else 3 * x `div` 2) 2
-- Reinhard Zumkeller, Mar 18 2012

1,seq(op([2^i,3*2^(i-1)]),i=1..100); # Robert Israel, Sep 23 2014

CoefficientList[Series[(-x^2 - 2*x - 1)/(2*x^2 - 1), {x, 0, 200}], x] (* Vladimir Joseph Stephan Orlovsky, Jun 10 2011 *)
Function[w, DeleteCases[Union@ Flatten@ w, k_ /; k > Max@ First@ w]]@ TensorProduct[{1, 3}, 2^Range[0, 22]] (* Michael De Vlieger, Nov 24 2016 *)
LinearRecurrence[{0,2},{1,2,3},50] (* Harvey P. Dale, Jul 04 2017 *)

PARI
```
a(n)=if(n%2,3/2,2)<<((n-1)\2)\1
```

def A029744(n):
    if n == 1: return 1
    elif n % 2 == 0: return 2**(n//2)
    else: return 3 * 2**((n-3)//2) # Karl-Heinz Hofmann, Sep 08 2022

(define (A029744 n) (cond ((<= n 1) n) ((even? n) (expt 2 (/ n 2))) (else (* 3 (expt 2 (/ (- n 3) 2)))))) ;; Antti Karttunen, Sep 23 2014

a(n) = 2*A000029(n) - A000031(n).
For n > 2, a(n) = 2*a(n - 2); for n > 3, a(n) = a(n - 1)*a(n - 2)/a(n - 3). G.f.: (1 + x)^2/(1 - 2*x^2). - Henry Bottomley, Jul 15 2001, corrected May 04 2007
a(0)=1, a(1)=1 and a(n) = a(n-2) * ( floor(a(n-1)/a(n-2)) + 1 ). - Benoit Cloitre, Aug 13 2002
(3/4 + sqrt(1/2))*sqrt(2)^n + (3/4 - sqrt(1/2))*(-sqrt(2))^n. a(0)=1, a(2n) = a(n-1)*a(n), a(2n+1) = a(n) + 2^floor((n-1)/2). - Ralf Stephan, Apr 16 2003 [Seems to refer to the original version with offset=0. - M. F. Hasler, Oct 06 2014]
Binomial transform is A048739. - Paul Barry, Apr 23 2004
E.g.f.: (cosh(x/sqrt(2)) + sqrt(2)sinh(x/sqrt(2)))^2.
a(1) = 1; a(n+1) = a(n) + A000010(a(n)). - Stefan Steinerberger, Dec 20 2007
u(2)=1, v(2)=1, u(n)=2*v(n-1), v(n)=u(n-1), a(n)=u(n)+v(n). - Jaume Oliver Lafont, May 21 2008
For n => 3, a(n) = sqrt(2*a(n-1)^2 + (-2)^(n-3)). - Richard R. Forberg, Aug 20 2013
a(n) = A064216(A246360(n)). - Antti Karttunen, Sep 23 2014
a(n) = sqrt((17 - (-1)^n)*2^(n-4)) for n >= 2. - Anton Zakharov, Jul 24 2016
Sum_{n>=1} 1/a(n) = 8/3. - Amiram Eldar, Nov 12 2020
a(n) = 2^(n/2) if n is even. a(n) = 3 * 2^((n-3)/2) if n is odd and for n>1. - Karl-Heinz Hofmann, Sep 08 2022

Corrected and extended by Joe Keane (jgk(AT)jgk.org), Feb 20 2000

A052307 Triangle read by rows: T(n,k) = number of bracelets (reversible necklaces) with n beads, k of which are black and n - k are white.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3, 3, 1, 1, 1, 1, 3, 4, 4, 3, 1, 1, 1, 1, 4, 5, 8, 5, 4, 1, 1, 1, 1, 4, 7, 10, 10, 7, 4, 1, 1, 1, 1, 5, 8, 16, 16, 16, 8, 5, 1, 1, 1, 1, 5, 10, 20, 26, 26, 20, 10, 5, 1, 1, 1, 1, 6, 12, 29, 38, 50, 38, 29, 12, 6, 1, 1, 1, 1, 6, 14, 35, 57, 76, 76, 57, 35, 14, 6, 1, 1

Offset: 0

Christian G. Bower, Nov 15 1999

Equivalently, T(n,k) is the number of orbits of k-element subsets of the vertices of a regular n-gon under the usual action of the dihedral group D_n, or under the action of Euclidean plane isometries. Note that each row of the table is symmetric and unimodal. - Austin Shapiro, Apr 20 2009

Also, the number of k-chords in n-tone equal temperament, up to (musical) transposition and inversion. Example: there are 29 tetrachords, 38 pentachords, 50 hexachords in the familiar 12-tone equal temperament. Called "Forte set-classes," after Allen Forte who first cataloged them. - Jon Wild, May 21 2004

			Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins:
   1;
   1,  1;
   1,  1,  1;
   1,  1,  1,  1;
   1,  1,  2,  1,  1;
   1,  1,  2,  2,  1,  1;
   1,  1,  3,  3,  3,  1,  1;
   1,  1,  3,  4,  4,  3,  1,  1;
   1,  1,  4,  5,  8,  5,  4,  1,  1;
   1,  1,  4,  7, 10, 10,  7,  4,  1,  1;
   1,  1,  5,  8, 16, 16, 16,  8,  5,  1,  1;
   1,  1,  5, 10, 20, 26, 26, 20, 10,  5,  1,  1;
   1,  1,  6, 12, 29, 38, 50, 38, 29, 12,  6,  1,  1;
   ...

Martin Gardner, "New Mathematical Diversions from Scientific American" (Simon and Schuster, New York, 1966), pages 245-246.
N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

Washington Bomfim, Rows n = 0..130, flattened
N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
G. Gori, S. Paganelli, A. Sharma, P. Sodano, and A. Trombettoni, Bell-Paired States Inducing Volume Law for Entanglement Entropy in Fermionic Lattices, arXiv:1405.3616 [cond-mat.stat-mech], 2014. See Section V.
H. Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10(8) (1979), 964-999.
S. Karim, J. Sawada, Z. Alamgirz, and S. M. Husnine, Generating bracelets with fixed content, Theoretical Computer Science, 475 (2013), 103-112.
John P. McSorley and Alan H. Schoen, Rhombic tilings of (n, k)-ovals, (n, k, lambda)-cyclic difference sets, and related topics, Discrete Math., 313 (2013), 129-154. - From _N. J. A. Sloane_, Nov 26 2012
A. L. Patterson, Ambiguities in the X-Ray Analysis of Crystal Structures, Phys. Rev. 65 (1944), 195 - 201 (see Table I). [From _N. J. A. Sloane_, Mar 14 2009]
Richard H. Reis, A formula for C(T) in Gupta's paper, Indian J. Pure and Appl. Math., 10(8) (1979), 1000-1001.
Vladimir Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35(5) (2004), 629-638.
Vladimir Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35(5) (2004), 629-638.
Index entries for sequences related to bracelets

Row sums: A000029. Columns 0-12: A000012, A000012, A008619, A001399, A005232, A032279, A005513, A032280, A005514, A032281, A005515, A032282, A005516.

Cf. A047996, A051168, A052308, A052309, A052310.

A052307 := proc(n,k)
        local hk,a,d;
        if k = 0 then
                return 1 ;
        end if;
        hk := k mod 2 ;
        a := 0 ;
        for d in numtheory[divisors](igcd(k,n)) do
                a := a+ numtheory[phi](d)*binomial(n/d-1,k/d-1) ;
        end do:
        %/k + binomial(floor((n-hk)/2),floor(k/2)) ;
        %/2 ;
end proc: # R. J. Mathar, Sep 04 2011

Table[If[m*n===0,1,1/2*If[EvenQ[n], If[EvenQ[m], Binomial[n/2, m/2], Binomial[(n-2)/2, (m-1)/2 ]], If[EvenQ[m], Binomial[(n-1)/2, m/2], Binomial[(n-1)/2, (m-1)/2]]] + 1/2*Fold[ #1 +(EulerPhi[ #2]*Binomial[n/#2, m/#2])/n &, 0, Intersection[Divisors[n], Divisors[m]]]], {n,0,12}, {m,0,n}] (* Wouter Meeussen, Aug 05 2002, Jan 19 2009 *)

B(n,k)={ if(n==0, return(1)); GCD = gcd(n, k); S = 0;
for(d = 1, GCD, if((k%d==0)&&(n%d==0), S+=eulerphi(d)*binomial(n/d,k/d)));
return (binomial(floor(n/2)- k%2*(1-n%2), floor(k/2))/2 + S/(2*n)); }
n=0;k=0; for(L=0, 8645, print(L, " ", B(n,k)); k++; if(k>n, k=0; n++))
/* Washington Bomfim, Jun 30 2012 */

from sympy import binomial as C, totient, divisors, gcd
def T(n, k): return 1 if n==0 else C((n//2) - k%2 * (1 - n%2), (k//2))/2 + sum(totient(d)*C(n//d, k//d) for d in divisors(gcd(n, k)))/(2*n)
for n in range(11): print([T(n, k) for k in range(n + 1)]) # Indranil Ghosh, Apr 23 2017

T(0,0) = 1. If n > 0, T(n,k) = binomial(floor(n/2) - (k mod 2) * (1 - (n mod 2)), floor(k/2)) / 2 + Sum_{d|n, d|k} (phi(d)*binomial(n/d, k/d)) / (2*n). - Washington Bomfim, Jun 30 2012 [edited by Petros Hadjicostas, May 29 2019]
From Freddy Barrera, Apr 21 2019: (Start)
T(n,k) = (1/2) * (A119963(n,k) + A047996(n,k)).
T(n,k) = T(n, n-k) for each k < n (Theorem 2 of H. Gupta). (End)
G.f. for column k >= 1: (x^k/2) * ((1/k) * Sum_{m|k} phi(m)/(1 - x^m)^(k/m) + (1 + x)/(1 - x^2)^floor((k/2) + 1)). (This formula is due to Herbert Kociemba.) - Petros Hadjicostas, May 25 2019
Bivariate o.g.f.: Sum_{n,k >= 0} T(n, k)*x^n*y^k = (1/2) * ((x + 1) * (x*y + 1) / (1 - x^2 * (y^2 + 1)) + 1 - Sum_{d >= 1} (phi(d)/d) * log(1 - x^d * (1 + y^d))). - Petros Hadjicostas, Jun 13 2019

A002729 Number of equivalence classes of binary sequences of period n.

Original entry on oeis.org

1, 2, 3, 4, 6, 6, 13, 10, 24, 22, 45, 30, 158, 74, 245, 368, 693, 522, 2637, 1610, 7386, 8868, 19401, 16770, 94484, 67562, 216275, 277534, 815558, 662370, 4500267, 2311470, 8466189, 13045108, 31593285, 40937606, 159772176, 103197490, 401913697

Offset: 0

N. J. A. Sloane

From Pab Ter (pabrlos2(AT)yahoo.com), Jan 24 2006: (Start)
The number of equivalence classes of sequences of period p, taking values in a set with b elements, is given by:
N(p) = (1/(p*phi(p)))*Sum_{t=0..p-1} Sum_{k=1..p-1 & gcd(p,k)=1} b^C(k,t) where C(k,t), the number of disjoint cycles of the permutations considered, is C(k,t) = Sum_{u=0..p-1} 1/M(k,p/gcd(p,u(k-1)+t)).
If gcd(k,L)=1, M(k,L) denotes the least positive integer M such that 1+k+...+k^(M-1) == 0 (mod L). Also if gcd(k,L)=1 and Ek(L) denotes the exponent of k mod L: M(k,L)=L*Ek(L)/gcd(L,1+k+...+k^(Ek(L)-1)).
(End)
Number of two-colored necklaces of length n, where similar necklaces are counted only once. Two necklaces of length n, given by color functions c and d from {0, ..., n-1} to N (set of natural numbers) are considered similar iff there is a factor f, 0 < f < n, satisfying gcd(f,n) = 1, such that, for all k from {0, ..., n-1}, d(f * k mod n) = c(k). I.e., the bead at position k is moved to f * k mod n. In other words: the sequence counts the orbits of the action of the multiplicative group {f | 0 < f < n, gcd(f,n) = 1} on the set of two-colored necklaces where f maps c to d with the formula above. - Matthias Engelhardt
Counts the same necklaces as A000029 but some of the necklaces viewed as distinct in A000029 are now viewed as equal. In particular, this implies that a(n) <= A000029(n) for every n.

D. Z. Dokovic, I. Kotsireas, D. Recoskie, J. Sawada, Charm bracelets and their application to the construction of periodic Golay pairs, Discrete Applied Mathematics, Volume 188, 19 June 2015, Pages 32-40.
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).

Vincenzo Librandi, Table of n, a(n) for n = 0..50
CombOS - Combinatorial Object Server, Generate necklaces, Lyndon words, chord diagrams, and relatives.
D. Z. Dokovic, I. Kotsireas et al., Charm bracelets and their application to the construction of periodic Golay pairs, arXiv:1405.7328 [math.CO], 2014.
M. Engelhardt, The N queens problem.
R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.
Index entries for sequences related to necklaces

Row 2 of A285548.

Cf. A002730.

with(numtheory): M:=proc(k,L) local e,s: s:=1: for e from 1 do if(s mod L = 0) then RETURN(e) else s:=s+k^e fi od: end; C:=proc(k,t,p) local u: RETURN(add(M(k,p/igcd(p,u*(k-1)+t))^(-1),u=0..p-1)) :end; N:=proc(p) options remember: local s,t,k: if(p=1) then RETURN(2) fi: s:=0: for t from 0 to p-1 do for k from 1 to p-1 do if igcd(p,k)=1 then s:=s+2^C(k,t,p) fi od od: RETURN(s/(p*phi(p))):end;seq(N(p),p=1..51); # first M expression
with(numtheory): E:=proc(k,L) if(L=1) then RETURN(1) else RETURN(order(k,L)) fi end; M:=proc(k,L) local s,EkL: EkL:=E(k,L): if(k>1) then s:=(k^EkL-1)/(k-1): RETURN(L*EkL/igcd(L,s)) else RETURN(L*EkL/igcd(L,EkL)) fi end; C:=proc(k,t,p) local u: RETURN(add(M(k,p/igcd(p,u*(k-1)+t))^(-1),u=0..p-1)) :end; N:=proc(p) options remember: local s,t,k: if(p=1) then RETURN(2) fi: s:=0: for t from 0 to p-1 do for k from 1 to p-1 do if igcd(p,k)=1 then s:=s+2^C(k,t,p) fi od od: RETURN(s/(p*phi(p))):end;seq(N(p),p=1..51);# second M expression (Pab Ter)

max = 38; m[k_, n_] := (s = 1; Do[ If[ Mod[s, n] == 0, Return[e], s = s + k^e ] , {e, 1, max}]); c[k_, t_, n_] := Sum[ m[k, n/GCD[n, u*(k-1) + t]]^(-1), {u, 0, n-1}]; a[n_] := (s = 0; Do[ If[ GCD[n, k] == 1 , s = s + 2^c[k, t, n]] , {k, 1, n-1}, {t, 0, n-1}]; s/(n*EulerPhi[n])); a[0] = 1; a[1] = 2; Table[a[n], {n, 0, max}] (* Jean-François Alcover, Dec 06 2011, after Maple *)

Reference gives formula.

More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005

Entry revised by N. J. A. Sloane at the suggestion of Max Alekseyev, Jun 20 2007

A081720 Triangle T(n,k) read by rows, giving number of bracelets (turnover necklaces) with n beads of k colors (n >= 1, 1 <= k <= n).

Original entry on oeis.org

1, 1, 3, 1, 4, 10, 1, 6, 21, 55, 1, 8, 39, 136, 377, 1, 13, 92, 430, 1505, 4291, 1, 18, 198, 1300, 5895, 20646, 60028, 1, 30, 498, 4435, 25395, 107331, 365260, 1058058, 1, 46, 1219, 15084, 110085, 563786, 2250311, 7472984, 21552969, 1, 78, 3210, 53764, 493131, 3037314

Offset: 1

N. J. A. Sloane, based on information supplied by Gary W. Adamson, Apr 05 2003

From Petros Hadjicostas, Nov 29 2017: (Start)
The formula given below is clear from the programs given in the Maple and Mathematica sections, while the g.f. for column k can be obtained using standard techniques.
If we differentiate the column k g.f. m times, then we can get a formula for row m. (For this sequence, we only need to use this row m formula for 1 <= k <= m, but it is valid even for k>m.) For example, to get the formula for row 8, we have T(n=8,k) = d^8/dx^8 (column k g.f.)/8! evaluated at x=0. Here, "d^8/dx^8" means "8th derivative w.r.t. x" of the column k g.f. Doing so, we get T(n=8, k) = (k^6 - k^5 + k^4 + 3*k^3 + 2*k^2 - 2*k + 4)*(k + 1)*k/16, which is the formula given for sequence A060560. (Here, we use this formula only for 1 <= k <= 8.)
(End)

			1;                                                (A000027)
1,  3;                                            (A000217)
1,  4,  10;                                       (A000292)
1,  6,  21,   55;                                 (A002817)
1,  8,  39,  136,   377;                          (A060446)
1, 13,  92,  430,  1505,   4291;                  (A027670)
1, 18, 198, 1300,  5895,  20646,  60028;          (A060532)
1, 30, 498, 4435, 25395, 107331, 365260, 1058058; (A060560)
...
For example, when n=k=3, we have the following T(3,3)=10 bracelets of 3 beads using up to 3 colors: 000, 001, 002, 011, 012, 022, 111, 112, 122, and 222. (Note that 012 = 120 = 201 = 210 = 102 = 021.) _Petros Hadjicostas_, Nov 29 2017

N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Yi Hu, Numerical Transfer Matrix Method of Next-nearest-neighbor Ising Models, Master's Thesis, Duke Univ. (2021).
Yi Hu and Patrick Charbonneau, Numerical transfer matrix study of frustrated next-nearest-neighbor Ising models on square lattices, arXiv:2106.08442 [cond-mat.stat-mech], 2021, cites the 4th column.

Cf. A321791 (extension to n >= 0, k >= 0).

Cf. A081721 (diagonal), A081722 (row sums), column sequences k=2..6: A000029, A027671, A032275, A032276, A056341.

A081720 := proc(n, k)
    local d, t1;
    t1 := 0;
    if n mod 2 = 0 then
        for d from 1 to n do
            if n mod d = 0 then
                t1 := t1+numtheory[phi](d)*k^(n/d);
            end if;
        end do:
        (t1+(n/2)*(1+k)*k^(n/2)) /(2*n) ;
    else
        for d from 1 to n do
            if n mod d = 0 then
                t1 := t1+numtheory[phi](d)*k^(n/d);
            end if;
        end do;
        (t1+n*k^((n+1)/2)) /(2*n) ;
    end if;
end proc:
seq(seq(A081720(n,k),k=1..n),n=1..10) ;

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)]); Table[t[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 13 2012, after Maple, updated Nov 02 2017 *)
Needs["Combinatorica`"]; Table[Table[NumberOfNecklaces[n,k,Dihedral],{k,1,n}],{n,1,8}]//Grid  (* Geoffrey Critzer, Oct 07 2012, after code by T. D. Noe in A027671 *)

See Maple code.
From Petros Hadjicostas, Nov 29 2017: (Start)
T(n,k) = ((1+k)*k^{n/2}/2 + (1/n)*Sum_{d|n} phi(n/d)*k^d)/2, if n is even, and = (k^{(n+1)/2} + (1/n)*Sum_{d|n} phi(n/d)*k^d)/2, if n is odd.
G.f. for column k: (1/2)*((k*x+k*(k+1)*x^2/2)/(1-k*x^2) - Sum_{n>=1} (phi(n)/n)*log(1-k*x^n)) provided we chop off the Taylor expansion starting at x^k (and ignore all the terms x^n with n(End)
2*n*T(n,k) = A054618(n,k)+n*(1+k)^(n/2)/2 if n even, = A054618(n,k)+n*k^((n+1)/2) if n odd. - R. J. Mathar, Jan 23 2022

Name edited by Petros Hadjicostas, Nov 29 2017

Showing 1-10 of 42 results. Next

cp's OEIS Frontend

A054192 Binomial transform of A000029.

Views

Author

Keywords

Links

Programs

Maple

Mathematica

Formula

A054155 Inverse Moebius transform of A000029 (starting at term 0).

Views

Author

Keywords

A054156 Moebius transform of A000029 (starting at term 0).

Views

Author

Keywords

A354464 Number of distinct bracelets of length n (A000029) that eventually result in a cycle with length 2 or greater when used as the starting conditions for a rule 18 cellular automaton in a cyclic universe of circumference n.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A367036 Number of distinct bracelets of length n (A000029) that eventually result in a cycle with length 2 or greater when used as the starting conditions for a rule 161 cellular automaton in a cyclic universe of circumference n.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A000031 Number of n-bead necklaces with 2 colors when turning over is not allowed; also number of output sequences from a simple n-stage cycling shift register; also number of binary irreducible polynomials whose degree divides n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A029744 Numbers of the form 2^n or 3*2^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Scheme

Formula

Extensions

A052307 Triangle read by rows: T(n,k) = number of bracelets (reversible necklaces) with n beads, k of which are black and n - k are white.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula