A000029 -id:A000029 - cp's OEIS frontend

A059076 Number of pairs of orientable necklaces with n beads and two colors; i.e., turning the necklace over does not leave it unchanged.

0, 0, 0, 0, 0, 0, 1, 2, 6, 14, 30, 62, 128, 252, 495, 968, 1866, 3600, 6917, 13286, 25476, 48916, 93837, 180314, 346554, 666996, 1284570, 2477342, 4781502, 9240012, 17871708, 34604066, 67060746, 130085052, 252548760, 490722344

Offset: 0

Henry Bottomley, Dec 22 2000

nonn

Number of chiral bracelets with n beads and two colors.

			For n=6, the only chiral pair is AABABB-AABBAB.  For n=7, the two chiral pairs are AAABABB-AAABBAB and AABABBB-AABBBAB. - _Robert A. Russell_, Sep 24 2018

G. C. Greubel, Table of n, a(n) for n = 0..1000
Daniel Gabric and Joe Sawada, Efficient Construction of Long Orientable Sequences, arXiv:2401.14341 [cs.DS], 2024.
Petros Hadjicostas, Formulas for chiral bracelets, 2019; see Section 5.
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

Column 2 of A293496.
Cf. A059053.
Column 2 of A305541.
Equals (A000031 - A164090) / 2.
a(n) = (A052823(n) - A027383(n-2)) / 2.

nn=35;Table[CoefficientList[Series[CycleIndex[CyclicGroup[n],s]-CycleIndex[DihedralGroup[n],s]/.Table[s[i]->2,{i,1,n}],{x,0,nn}],x],{n,1,nn}]//Flatten  (* Geoffrey Critzer, Mar 26 2013 *)
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 *)
terms = 36; a29[0] = 1; a29[n_] := (1/4)*(Mod[n, 2] + 3)*2^Quotient[n, 2] + DivisorSum[n, EulerPhi[#]*2^(n/#) & ]/(2*n); Array[a29, 36, 0] - LinearRecurrence[{0, 2}, {1, 2, 3}, 36] (* Jean-François Alcover, Nov 05 2017 *)
k = 2; 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 *)

a(n) = A000031(n) - A000029(n) = A000029(n) - A029744(n) = (A000031(n) - A029744(n))/2 = A008965(n) - A091696(n)
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
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 = 2 is the maximum number of colors. - Robert A. Russell, Sep 24 2018

A222188 Table read by antidiagonals: number of toroidal m X n binary arrays, allowing rotation and/or reflection of the rows and/or the columns.

Original entry on oeis.org

2, 3, 3, 4, 7, 4, 6, 13, 13, 6, 8, 34, 36, 34, 8, 13, 78, 158, 158, 78, 13, 18, 237, 708, 1459, 708, 237, 18, 30, 687, 4236, 14676, 14676, 4236, 687, 30, 46, 2299, 26412, 184854, 340880, 184854, 26412, 2299, 46

Offset: 1

N. J. A. Sloane, Feb 12 2013

			Array begins:
  2,  3,   4,     6,      8,      13,        18,         30, ...
  3,  7,  13,    34,     78,     237,       687,       2299, ...
  4, 13,  36,   158,    708,    4236,     26412,     180070, ...
  6, 34, 158,  1459,  14676,  184854,   2445918,   33888844, ...
  8, 78, 708, 14676, 340880, 8999762, 245619576, 6873769668, ...
  ...

G. C. Greubel, Table of n, a(n) for the first 100 antidiagonals, flattened
S. N. Ethier, Counting toroidal binary arrays, arXiv:1301.2352 [math.CO], 2013 and J. Int. Seq. 16 (2013) #13.4.7.
S. N. Ethier and Jiyeon Lee, Counting toroidal binary arrays, II, arXiv:1502.03792v1 [math.CO], Feb 12, 2015 and J. Int. Seq. 18 (2015) # 15.8.3.
S. N. Ethier and Jiyeon Lee, Parrondo games with two-dimensional spatial dependence, arXiv:1510.06947 [math.PR], 2015.
Peter Kagey and William Keehn, Counting tilings of the n X m grid, cylinder, and torus, arXiv:2311.13072 [math.CO], 2023. See p. 3.

Rows give A000029, A222187, A222189, A222190, A222191.
Main diagonal is A209251.
Cf. A184271.

b1[m_, n_] := Sum[EulerPhi[c]*EulerPhi[d]*2^(m*n/LCM[c, d]), {c, Divisors[ m]}, {d, Divisors[n]}]/(4*m*n); b2a[m_, n_] := If[OddQ[m], 2^((m+1)*n/2) /(4*n), (2^(m*n/2) + 2^((m+2)*n/2))/(8*n)]; b2b[m_, n_] := DivisorSum[n, If[# >= 2, EulerPhi[#]*2^((m*n)/#), 0]&]/(4*n); b2c[m_, n_] := If[OddQ[ m], Sum[If [OddQ[n/GCD[j, n]], 2^((m+1)*GCD[j, n]/2) - 2^(m*GCD[j, n]), 0], {j, 1, n-1}]/(4*n), Sum[If[OddQ[n/GCD[j, n]], 2^(m*GCD[j, n]/2) + 2^((m+2)*GCD[j, n]/2) - 2^(m*GCD[j, n]+1), 0], {j, 1, n-1}]/(8*n)]; b2[m_, n_] := b2a[m, n] + b2b[m, n] + b2c[m, n]; b3[m_, n_] := b2[n, m]; b4oo[m_, n_] := 2^((m*n-3)/2); b4eo[m_, n_] := 3*2^(m*n/2 - 3); b4ee[m_, n_] := 7*2^(m*n/2-4); a[m_, n_] := Module[{b}, If [OddQ[m], If [OddQ[n], b = b4oo[m, n], b = b4eo[m, n]], If[OddQ[n], b = b4eo[m, n], b = b4ee[m, n]]]; b += b1[m, n] + b2[m, n] + b3[m, n]; Return[b]]; Table[a[m - n+1, n], {m, 1, 10}, {n, 1, m}] // Flatten (* Jean-François Alcover, Dec 05 2015, adapted from Michel Marcus's PARI script *)

odd(n) = n%2;
b1(m,n) = sumdiv(m, c, sumdiv(n, d, eulerphi(c)*eulerphi(d)*2^(m*n/lcm(c,d))))/(4*m*n);
b2a(m,n) = if (odd(m), 2^((m+1)*n/2)/(4*n), (2^(m*n/2)+2^((m+2)*n/2))/(8*n));
b2b(m,n) = sumdiv(n, d, if (d>=2, eulerphi(d)*2^((m*n)/d), 0))/(4*n);
b2c(m,n) = if (odd(m), sum(j=1, n-1, if (odd(n/gcd(j,n)), 2^((m+1)*gcd(j,n)/2)-2^(m*gcd(j,n))))/(4*n), sum(j=1, n-1, if (odd(n/gcd(j,n)), 2^(m*gcd(j,n)/2)+2^((m+2)*gcd(j,n)/2)-2^(m*gcd(j,n)+1)))/(8*n));
b2(m,n) = b2a(m,n) + b2b(m,n) + b2c(m,n);
b3(m,n) = b2(n,m);
b4oo(m,n) = 2^((m*n - 3)/2);
b4eo(m,n) = 3*2^(m*n/2 - 3);
b4ee(m,n) = 7*2^(m*n/2 - 4);
a(m,n) = {if (odd(m), if (odd(n), b = b4oo(m,n), b = b4eo(m,n)), if (odd(n), b = b4eo(m,n), b = b4ee(m,n))); b += b1(m,n) + b2(m,n) + b3(m,n); return (b);}
\\ Michel Marcus, Feb 13 2013

A001371 Number of n-bead necklaces with beads of 2 colors and primitive period n, when turning over is allowed.

Original entry on oeis.org

1, 2, 1, 2, 3, 6, 8, 16, 24, 42, 69, 124, 208, 378, 668, 1214, 2220, 4110, 7630, 14308, 26931, 50944, 96782, 184408, 352450, 675180, 1296477, 2493680, 4805388, 9272778, 17919558, 34669600, 67156800, 130215996, 252741255, 490984464, 954629662, 1857545298

Offset: 0

N. J. A. Sloane

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence, in two entries, N0045 and N0285).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..400
Jairo Bochi and Piotr Laskawiec, Spectrum maximizing products are not generically unique, arXiv:2301.12574 [math.OC], 2023.
Edgar N. Gilbert and John Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Piotr Laskawiec, Joint Spectral Radius with focus on pairs of 2 X 2 matrices, Ph. D. Dissertation, Penn. State Univ. (2025). See p. 55.
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Frany Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Index entries for sequences related to necklaces

Column 2 of A276550.

with(numtheory); A001371 := proc(n) local s,d; if n = 0 then RETURN(1) else s := 0; for d in divisors(n) do s := s+mobius(d)*A000029(n/d); od; RETURN(s); fi; end;

a29[n_] := a29[n] = (s = If[OddQ[n], 2^((n-1)/2) , 2^(n/2 - 2) + 2^(n/2 - 1)]; a29[0] = 1; Do[s = s + EulerPhi[d]*2^(n/d)/(2*n), {d, Divisors[n]}]; s); a[n_] := Sum[ MoebiusMu[d]*a29[n/d], {d, Divisors[n]}]; a[0] = 1; Table[ a[n], {n, 0, 34}] (* Jean-François Alcover, Oct 04 2011 *)
mx=40;gf[x_,k_]:=Sum[ MoebiusMu[n]*(-Log[1-k*x^n]/n+Sum[Binomial[k,i]x^(n i),{i,0,2}]/( 1-k x^(2n)))/2,{n,mx}]; ReplacePart[CoefficientList[Series[gf[x,2],{x,0,mx}],x],1->1] (* Herbert Kociemba, Nov 28 2016 *)

from sympy import divisors, totient, mobius
def a000029(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
def a(n):
    return 1 if n<1 else sum(mobius(d)*a000029(n//d) for d in divisors(n))
print([a(n) for n in range(51)]) # Indranil Ghosh, Apr 23 2017

a(n) = Sum_{ d divides n } mu(d)*A000029(n/d).
From Herbert Kociemba, Nov 28 2016: (Start)
More generally, for n>0, gf(k) is the g.f. for the number of bracelets with primitive period n and beads of k colors.
gf(k): Sum_{n>=1} mu(n)*( -log(1-k*x^n)/n + Sum_{i=0..2} binomial(k,i)x^(n*i)/(1-k*x^(2*n)) )/2. (End)

More terms from Christian G. Bower

Entry revised by N. J. A. Sloane, Jun 10 2012

A208721 T(n,k) = number of n-bead necklaces labeled with numbers 1..k allowing reversal, with no adjacent beads differing by more than 1.

Original entry on oeis.org

1, 2, 1, 3, 3, 1, 4, 5, 4, 1, 5, 7, 7, 6, 1, 6, 9, 10, 12, 8, 1, 7, 11, 13, 18, 18, 13, 1, 8, 13, 16, 24, 28, 34, 18, 1, 9, 15, 19, 30, 38, 56, 56, 30, 1, 10, 17, 22, 36, 48, 78, 98, 111, 46, 1, 11, 19, 25, 42, 58, 100, 140, 208, 207, 78, 1, 12, 21, 28, 48, 68, 122, 182, 306, 418, 427, 126

Offset: 1

R. H. Hardin, Mar 01 2012

Table starts
.1..2...3...4...5...6...7...8...9..10..11..12...13...14...15...16...17...18
.1..3...5...7...9..11..13..15..17..19..21..23...25...27...29...31...33...35
.1..4...7..10..13..16..19..22..25..28..31..34...37...40...43...46...49...52
.1..6..12..18..24..30..36..42..48..54..60..66...72...78...84...90...96..102
.1..8..18..28..38..48..58..68..78..88..98.108..118..128..138..148..158..168
.1.13..34..56..78.100.122.144.166.188.210.232..254..276..298..320..342..364
.1.18..56..98.140.182.224.266.308.350.392.434..476..518..560..602..644..686
.1.30.111.208.306.404.502.600.698.796.894.992.1090.1188.1286.1384.1482.1580

			All solutions for n=4, k=3:
..2....3....2....2....1....2....1....2....1....1....1....1
..3....3....2....3....1....2....1....2....2....2....1....2
..2....3....3....3....2....2....1....2....1....3....1....2
..3....3....3....3....2....2....1....3....2....2....2....2

R. H. Hardin, Table of n, a(n) for n = 1..397

Column 2 is A000029.

A056342 Number of bracelets of length n using exactly two different colored beads.

Original entry on oeis.org

0, 1, 2, 4, 6, 11, 16, 28, 44, 76, 124, 222, 378, 685, 1222, 2248, 4110, 7683, 14308, 27010, 50962, 96907, 184408, 352696, 675186, 1296856, 2493724, 4806076, 9272778, 17920858, 34669600, 67159048, 130216122, 252745366, 490984486, 954637556, 1857545298, 3617214679, 7048675958, 13744694926, 26818405350

Offset: 1

Marks R. Nester

nonn

Turning over will not create a new bracelet.

			For a(6)=11, the arrangements are AAAAAB, AAAABB, AAABAB, AAABBB, AABAAB, AABBBB, ABABAB, ABABBB, ABBABB, ABBBBB, and AABABB, the last being chiral. Its reverse is AABBAB. - _Robert A. Russell_, Sep 26 2018

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]

G. C. Greubel, Table of n, a(n) for n = 1..3000

Column 2 of A273891.
Equals A052823 - A059076.
Cf. A008277, A027383.

a[n_] := (1/4)*(Mod[n, 2] + 3)*2^Quotient[n, 2] + DivisorSum[n, EulerPhi[#]*2^(n/#)&]/(2*n) - 2; Array[a, 41] (* Jean-François Alcover, Nov 05 2017 *)
k=2; Table[k! DivisorSum[n, EulerPhi[#] StirlingS2[n/#,k]&]/(2n) + k!(StirlingS2[Floor[(n+1)/2], k] + StirlingS2[Ceiling[(n+1)/2], k])/4, {n,1,30}] (* Robert A. Russell, Sep 26 2018 *)

a(n) = my(k=2); (k!/4)*(stirling(floor((n+1)/2),k,2) + stirling(ceil((n+1)/2),k,2)) + (k!/(2*n))*sumdiv(n,d,eulerphi(d)*stirling(n/d,k,2)); \\ Michel Marcus, Sep 28 2018

a(n) = A000029(n) - 2.
From Robert A. Russell, Sep 26 2018: (Start)
a(n) = (A052823(n) + A027383(n-2)) / 2 = A059076(n) + A027383(n-2).
a(n) = (k!/4) * (S2(floor((n+1)/2),k) + S2(ceiling((n+1)/2),k)) + (k!/2n) * Sum_{d|n} phi(d) * S2(n/d,k), where k=2 is the number of colors and S2 is the Stirling subset number A008277.
G.f.: (k!/4) * x^(2k-2) * (1+x)^2 / Product_{i=1..k} (1-i x^2) - Sum_{d>0} (phi(d)/2d) * Sum_{j} (-1)^(k-j) * C(k,j) * log(1-j x^d), where k=2 is the number of colors. (End)

More terms from Joerg Arndt, Jun 10 2016

A208671 T(n,k) = number of 2n-bead necklaces labeled with numbers 1..k allowing reversal, with neighbors differing by exactly 1.

Original entry on oeis.org

0, 1, 0, 2, 1, 0, 3, 3, 1, 0, 4, 5, 4, 1, 0, 5, 7, 8, 6, 1, 0, 6, 9, 12, 14, 8, 1, 0, 7, 11, 16, 23, 24, 13, 1, 0, 8, 13, 20, 32, 44, 47, 18, 1, 0, 9, 15, 24, 41, 65, 97, 89, 30, 1, 0, 10, 17, 28, 50, 86, 152, 212, 187, 46, 1, 0, 11, 19, 32, 59, 107, 208, 360, 512, 396, 78, 1, 0, 12, 21, 36

Offset: 1

R. H. Hardin, Feb 29 2012

Table starts
.0.1..2...3...4...5....6....7....8....9...10..11..12..13.14.15.16
.0.1..3...5...7...9...11...13...15...17...19..21..23..25.27.29
.0.1..4...8..12..16...20...24...28...32...36..40..44..48.52
.0.1..6..14..23..32...41...50...59...68...77..86..95.104
.0.1..8..24..44..65...86..107..128..149..170.191.212
.0.1.13..47..97.152..208..264..320..376..432.488
.0.1.18..89.212.360..514..669..824..979.1134
.0.1.30.187.512.937.1398.1866.2335.2804

			All solutions for n=4, k=3:
..1....1....1....1....1....2
..2....2....2....2....2....3
..3....1....1....1....3....2
..2....2....2....2....2....3
..1....3....1....1....3....2
..2....2....2....2....2....3
..3....3....3....1....3....2
..2....2....2....2....2....3

R. H. Hardin, Table of n, a(n) for n = 1..148

Column 3 is A000029.

Cf. A208727, A220062.

T(n,k) = (2*A208727(n) + A220062(n+1,k))/4. - Andrew Howroyd, Mar 19 2017

A051137 Table T(n,k) read by antidiagonals: number of necklaces allowing turnovers (bracelets) with n beads of k colors.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 6, 10, 10, 5, 1, 1, 8, 21, 20, 15, 6, 1, 1, 13, 39, 55, 35, 21, 7, 1, 1, 18, 92, 136, 120, 56, 28, 8, 1, 1, 30, 198, 430, 377, 231, 84, 36, 9, 1, 1, 46, 498, 1300, 1505, 888, 406, 120, 45, 10, 1

Offset: 0

Alford Arnold

Unlike A075195 and A284855, antidiagonals go from bottom-left to top-right.

			Table begins with T[0,1]:
1  1    1     1      1       1        1        1         1         1
1  2    3     4      5       6        7        8         9        10
1  3    6    10     15      21       28       36        45        55
1  4   10    20     35      56       84      120       165       220
1  6   21    55    120     231      406      666      1035      1540
1  8   39   136    377     888     1855     3536      6273     10504
1 13   92   430   1505    4291    10528    23052     46185     86185
1 18  198  1300   5895   20646    60028   151848    344925    719290
1 30  498  4435  25395  107331   365260  1058058   2707245   6278140
1 46 1219 15084 110085  563786  2250311  7472984  21552969  55605670
1 78 3210 53764 493131 3037314 14158228 53762472 174489813 500280022

C. G. Bower, Transforms (2)

Columns 2-6 are A000029, A027671, A032275, A032276, and A056341.
Rows 2-7 are A000217, A000292, A002817, A060446, A027670, and A060532.
Cf. A000031.
Cf. A081720, A081721.
T(n,k) = (A075195(n,k) + A284855(n,k)) / 2.

b[n_, k_] := DivisorSum[n, EulerPhi[#]*k^(n/#) &] / n;
c[n_, k_] := If[EvenQ[n], (k^(n/2) + k^(n/2+1))/2, k^((n+1)/2)];
T[0, ] = 1; T[n, k_] := (b[n, k] + c[n, k])/2;
Table[T[n, k-n], {k, 1, 11}, {n, k-1, 0, -1}] // Flatten
(* Robert A. Russell, Sep 21 2018 after Jean-François Alcover *)

T(n, k) = (k^floor((n+1)/2) + k^ceiling((n+1)/2)) / 4 + (1/(2*n)) * Sum_{d divides n} phi(d) * k^(n/d). - Robert A. Russell, Sep 21 2018
G.f. for column k: (kx/4)*(kx+x+2)/(1-kx^2) - Sum_{d>0} phi(d)*log(1-kx^d)/2d. - Robert A. Russell, Sep 28 2018
T(n, k) = (k^floor((n+1)/2) + k^ceiling((n+1)/2))/4 + (1/(2*n))*Sum_{i=1..n} k^gcd(n,i). (See A075195 formulas.) - 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

Marks R. Nester

nonn

Turning over will not create a new bracelet.

			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

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

Cf. A000029, A054625.
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.

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 *)

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

A056343 Number of bracelets of length n using exactly three different colored beads.

Original entry on oeis.org

0, 0, 1, 6, 18, 56, 147, 411, 1084, 2979, 8043, 22244, 61278, 171030, 477929, 1345236, 3795750, 10758902, 30572427, 87149124, 248991822, 713096352, 2046303339, 5883433409, 16944543810, 48879769575

Offset: 1

Marks R. Nester

nonn

Turning over will not create a new bracelet.

			For a(4)=6, the arrangements are ABAC, ABCB, ACBC, AABC, ABBC, and ABCC. Only the last three are chiral, their reverses being AACB, ACBB, and ACCB respectively. - _Robert A. Russell_, Sep 26 2018

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]

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Column 3 of A273891.

Equals (A056283 + A056489) / 2 = A056283 - A305542 = A305542 + A056489.

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)]);
T[n_, k_] := Sum[(-1)^i*Binomial[k, i]*t[n, k - i], {i, 0, k - 1}];
a[n_] := T[n, 3];
Array[a, 26] (* Jean-François Alcover, Nov 05 2017, after Andrew Howroyd *)
k=3; Table[k! DivisorSum[n, EulerPhi[#] StirlingS2[n/#,k]&]/(2n) + k!(StirlingS2[Floor[(n+1)/2], k] + StirlingS2[Ceiling[(n+1)/2], k])/4, {n,1,30}] (* Robert A. Russell, Sep 26 2018 *)

a(n) = A027671(n) - 3*A000029(n) + 3.
From Robert A. Russell, Sep 26 2018: (Start)
a(n) = (k!/4) * (S2(floor((n+1)/2),k) + S2(ceiling((n+1)/2),k)) + (k!/2n) * 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.: (k!/4) * x^(2k-2) * (1+x)^2 / Product_{i=1..k} (1-i x^2) - Sum_{d>0} (phi(d)/2d) * Sum_{j} (-1)^(k-j) * C(k,j) * log(1-j x^d), where k=3 is the number of colors. (End)

A006079 Number of asymmetric planted projective plane trees with n+1 nodes; bracelets (reversible necklaces) with n black beads and n-1 white beads.

Original entry on oeis.org

1, 1, 0, 1, 4, 16, 56, 197, 680, 2368, 8272, 29162, 103544, 370592, 1335504, 4844205, 17672400, 64810240, 238795040, 883585406, 3281967832, 12232957152, 45740929104, 171529130786, 644950721584, 2430970600576, 9183671335776, 34766765428852, 131873955816880

Offset: 1

N. J. A. Sloane

"DHK[ n ](2n-1)" (bracelet, identity, unlabeled, n parts, evaluated at 2n) transform of 1,1,1,1,...

For n > 2, half the number of asymmetric Dyck (n-1)-paths. E.g., the two asymmetric 3-paths are UDUUDD and UUDDUD, so a(4) = 2/2 = 1. - David Scambler, Aug 23 2012

			For the asymmetric planted projective plane trees sequence we have a(5) = 4, a(6) = 16, a(7) = 56, ...

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..200
C. G. Bower, Transforms (2).
Z. M. Himwich and N. A. Rosenberg, Roadblocked monotonic paths and the enumeration of coalescent histories for non-matching caterpillar gene trees and species trees, arXiv:1901.04465 [qbio.PE], 2019; Adv. Appl. Math. 113 (2020), 101939. (Table 1 shows twice this sequence.)
P. K. Stockmeyer, The charm bracelet problem and its applications, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.
P. J. Stockmeyer, The charm bracelet problem and its applications, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974. [Scanned annotated and corrected copy]
Index entries for sequences related to bracelets
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000029, A000031, A006080, A006081, A006082.

Equals half the difference of A000108 and A001405.

[1,1] cat [(Catalan(n) - Binomial(n, Floor(n/2)))/2: n in [2..40]]; // Vincenzo Librandi, Feb 16 2015

a[1] = a[2] = 1; a[n_] := (CatalanNumber[n-1] - Binomial[n-1, Floor[(n-1)/2]])/2; Table[ a[n], {n, 1, 26}] (* Jean-François Alcover, Mar 09 2012, after David Callan *)

Let c(x) = (1-sqrt(1-4*x))/(2*x) = g.f. for Catalan numbers (A000108), let d(x) = x/(1-x-x^2*c(x^2)) = g.f. for A001405. Then g.f. for the asymmetric planted projective plane trees sequence is (x*c(x)-d(x))/2 (the initial terms from this version are slightly different).

a(n+1) = (CatalanNumber(n) - binomial(n,floor(n/2)))/2 (for n>=3). - David Callan, Jul 14 2006

Alternative description and more terms from Christian G. Bower

cp's OEIS Frontend

A059076 Number of pairs of orientable necklaces with n beads and two colors; i.e., turning the necklace over does not leave it unchanged.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A222188 Table read by antidiagonals: number of toroidal m X n binary arrays, allowing rotation and/or reflection of the rows and/or the columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A001371 Number of n-bead necklaces with beads of 2 colors and primitive period n, when turning over is allowed.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A208721 T(n,k) = number of n-bead necklaces labeled with numbers 1..k allowing reversal, with no adjacent beads differing by more than 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A056342 Number of bracelets of length n using exactly two different colored beads.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A208671 T(n,k) = number of 2n-bead necklaces labeled with numbers 1..k allowing reversal, with neighbors differing by exactly 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A051137 Table T(n,k) read by antidiagonals: number of necklaces allowing turnovers (bracelets) with n beads of k colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author