A056493 -id:A056493 - cp's OEIS frontend

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

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

A007055 Let S denote the palindromes in the language {0,1}*; a(n) = number of words of length n in the language SS.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 52, 100, 160, 260, 424, 684, 1036, 1640, 2552, 3728, 5920, 8672, 13408, 19420, 30136, 42736, 66840, 94164, 145900, 204632, 317776, 441764, 685232, 950216, 1469632, 2031556, 3139360, 4323888, 6675904, 9174400, 14139496, 19398584, 29864888, 40891040, 62882680, 85983152

Offset: 0

N. J. A. Sloane, Mira Bernstein, R. Kemp

nonn

Number of words in {0,1}* of length n that are rotations of their reversals. - David W. Wilson, Jan 01 2012

a(n) = sum of the orbit sizes of all achiral necklaces (or bracelets) under the action of the cyclic (or dihedral) group. - Mathieu Gagne, Jul 29 2025

			S = {e, 0, 1, 11, 101, 111, 1001, 1111, 10001, 10101, 11011, 11111, 100001, ...}, where e is the empty word.
SS contains all words in {0,1}* of length <= 5, but at length 6 is missing the 12 words { 001011, 001101, 010011, 010110, 011001, 011010, 100101, 100110, 101001, 101100, 110010, 110100 }.
In more detail: All words in SS of length 6 have one of the following 6 patterns: abccba, abbacc, aabccb, abcbad, abacdc, abcdcb. This gives a total of 3*(2^3 + 2^4) = 72 = A187272(n) words with some words being counted multiple times as follows: (x6): 000000, 111111; (x3): 010101, 101010; (x2): 001001, 010010, 011011, 100100, 101101, 110110. These are exactly the repetitions of shorter words in SS. Subtracting gives a(6) = 72 - 5*2 - 2*2 - 1*6 = 52.
For length n=7: All words in SS of length 7 have one of the following 7 patterns: abcdcba, abccbad, abcbadd, abbacdc, abacddc, aabcdcb, abcddcb. This gives a total of 7*2^4 = 112 = A187272(n) words with some words being counted multiple times. In particular, the words 0000000 and 1111111 are counted 7 times each so a(7) = 112 - 6*2 = 100. - Information about examples courtesy of _Andrew Howroyd_, Mar 30 2016
For n=6, there are 2 achiral necklaces with orbit size s=1, 1 with s=2, 2 with s=3, and 7 with s=6, giving a total of 2*1+1*2+2*3+7*6 = 52. - _Mathieu Gagne_, Jul 29 2025

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

Chai Wah Wu, Table of n, a(n) for n = 0..6617
Chuan Guo, J. Shallit, and A. M. Shur, On the Combinatorics of Palindromes and Antipalindromes, arXiv preprint arXiv:1503.09112 [cs.FL], 2015.
R. Kemp, On the number of words in the language {w in Sigma* | w = w^R }^2, Discrete Math., 40 (1982), 225-234.

Column 2 of A284873.
For the nonempty words in the language S, see A057148 and A006995.
Cf. A007056-A007058, A023900, A187272-A187275.

# A023900:
f:=proc(n) local t0,t1,t2; if n=1 then RETURN(1) else
t0:=1; t1:=ifactors(n); t2:=t1[2]; for i from 1 to nops(t2) do t0:=t0*(1-t2[i][1]); od; RETURN(t0); fi; end;
# A187272, A187273, A187274, A187275:
R:=(a,n)->
expand(simplify( (n/4)*a^(n/2)*( (1+sqrt(a))^2+ (-1)^n*(1-sqrt(a))^2 ) ));
# A007055, A007056, A007057, A007058
F:=(b,n)-> if n=0 then 1 else expand(simplify( add( f(d)*R(b,n/d),d in divisors(n) ) )); fi;
# A007055:
[seq(F(2,n),n=0..60)];

A187272[n_] := A187272[n] = (n/4)*2^(n/2)*((1 + Sqrt[2])^2 + (-1)^n*(1 - Sqrt[2])^2) // Round;
a[n_ /; n <= 5] := 2^n; a[n_] := a[n] = A187272[n] - Sum[n, EulerPhi[n/d] * a[d], {d, Most[Divisors[n]]}];
Table[a[n], {n, 0, 41}] (* Jean-François Alcover, Oct 08 2017, after Andrew Howroyd *)
Table[Sum[s * Sum[MoebiusMu[s/d] If[EvenQ[d], 3*2^((d/2) - 1), 2^((d + 1)/2)] , {d, Divisors[s]}], {s, Divisors[n]}], {n, 1, 41}] (* Mathieu Gagne, Jul 29 2025 *)

from functools import lru_cache
from sympy import totient, proper_divisors
@lru_cache(maxsize=None)
def A007055(n): return (n<<(n+1>>1) if n&1 else 3*n<<(n-2>>1))-sum(totient(n//d)*A007055(d) for d in proper_divisors(n,generator=True)) if n else 1 # Chai Wah Wu, Feb 18 2024

a(n) = A187272(n) - Sum_{d|n, dAndrew Howroyd, Mar 29 2016
a(0)=1; a(n) = Sum_{s|n} s * A056493(s) for n>0. - Mathieu Gagne, Jul 29 2025
a(0)=1; a(n) = Sum_{s|n} s * (Sum_{d|s} mu(d) * A164090(s/d)) for n>0. - Mathieu Gagne, Jul 29 2025

Entry revised by N. J. A. Sloane, Mar 07 2011

A284856 Array read by antidiagonals: T(n,k) = number of aperiodic necklaces (Lyndon words) with n beads and k colors that are the same when turned over.

Original entry on oeis.org

1, 2, 0, 3, 1, 0, 4, 3, 2, 0, 5, 6, 6, 3, 0, 6, 10, 12, 12, 6, 0, 7, 15, 20, 30, 24, 7, 0, 8, 21, 30, 60, 60, 42, 14, 0, 9, 28, 42, 105, 120, 138, 78, 18, 0, 10, 36, 56, 168, 210, 340, 252, 144, 28, 0, 11, 45, 72, 252, 336, 705, 620, 600, 234, 39, 0

Offset: 1

Andrew Howroyd, Apr 04 2017

Number of primitive (period n) periodic palindromes of length n using a maximum of k different symbols.

			Table starts:
1  2   3    4    5     6     7      8      9     10 ...
0  1   3    6   10    15    21     28     36     45 ...
0  2   6   12   20    30    42     56     72     90 ...
0  3  12   30   60   105   168    252    360    495 ...
0  6  24   60  120   210   336    504    720    990 ...
0  7  42  138  340   705  1302   2212   3528   5355 ...
0 14  78  252  620  1290  2394   4088   6552   9990 ...
0 18 144  600 1800  4410  9408  18144  32400  54450 ...
0 28 234 1008 3100  7740 16758  32704  58968  99900 ...
0 39 456 2490 9240 26985 66864 146916 294480 548955 ...
...

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]

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Columns 2-6 are: A056493, A056494, A056495, A056496, A056497.

b[d_, k_] := If[EvenQ[d], (k^(d/2) + k^(d/2 + 1))/2, k^((d + 1)/2)];
a[n_, k_] := DivisorSum[n, MoebiusMu[n/#] b[#, k] &];
Table[a[n - k + 1, k], {n, 1, 11}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jun 06 2017, translated from PARI *)

b(d,k) = if(d % 2 == 0, (k^(d/2) + k^(d/2+1))/2, k^((d+1)/2));
a(n,k) = sumdiv(n,d, moebius(n/d) * b(d,k));
for(n=1, 10, for(k=1, 10, print1( a(n,k),", ");); print(););

T(n, k) = Sum_{d | n} mu(n/d) * A284855(d, k).

A180249 a(n) is the total number of k-reverses of n.

Original entry on oeis.org

1, 2, 4, 8, 16, 26, 50, 80, 130, 212, 342, 518, 820, 1276, 1864, 2960, 4336, 6704, 9710, 15068, 21368, 33420, 47082, 72950, 102316, 158888, 220882, 342616, 475108, 734816, 1015778, 1569680, 2161944, 3337952, 4587200, 7069748, 9699292, 14932444, 20445520

Offset: 1

John P. McSorley, Aug 19 2010

nonn

See sequence A180171 for the definition of a k-reverse of n.
Briefly, a k-reverse of n is a k-composition of n whose reverse is cyclically equivalent to itself.
This sequence is the total number of k-reverses of n for k=1,2,...,n.
It is the row sums of the 'R(n,k)' triangle from sequence A180171.
For example a(6)=26 because there are 26 k-reverses of n=6 for k=1,2,3,4,5, or 6.
They are, in cyclically equivalent, classes: {6}, {15,51}, {24,42},{33},{114,411,141},{222} {1113,3111,1311,1131}, {1122,2112,2211,1221}, {1212,2121}, {11112,21111,12111,11211,11121}, {111111}.

John P. McSorley: Counting k-compositions with palindromic and related structures. Preprint, 2010.

Andrew Howroyd, Table of n, a(n) for n = 1..200

If we ask for the number of cyclically equivalent classes we get sequence A052955.
For example the 6th term of A052955 is 11, corresponding to the 11 classes in the example above.
Row sums of A180171.
Cf. A056493, A180322.

f[n_Integer] := Block[{c = 0, k = 1, ip = IntegerPartitions@ n, lmt = 1 + PartitionsP@ n, ipk}, While[k < lmt, c += g[ ip[[k]]]; k++ ]; c]; g[lst_List] := Block[{c = 0, len = Length@ lst, per = Permutations@ lst}, While[ Length@ per > 0, rl = Union[ RotateLeft[ per[[1]], # ] & /@ Range@ len]; If[ MemberQ[rl, Reverse@ per[[1]]], c += Length@ rl]; per = Complement[ per, rl]]; c]; Array[f, 24] (* Robert G. Wilson v, Aug 25 2010 *)
b[n_] := Sum[MoebiusMu[n/d] * If[OddQ[d], 2, 3] * 2^Quotient[d-1, 2], {d, Divisors[n]}]; a[n_] := Sum[d*b[d], {d, Divisors[n]}] / 2; Array[a, 39] (* Jean-François Alcover, Nov 04 2017, after Andrew Howroyd *)

\\ here b(n) is A056493
b(n) = sumdiv(n, d, moebius(n/d) * if(d%2,2,3) * 2^((d-1)\2));
a(n) = sumdiv(n, d, d*b(d)) / 2; \\ Andrew Howroyd, Oct 07 2017

a(n) = Sum_{d|n} d*A056493(d)/2. - Andrew Howroyd, Oct 07 2017
From Petros Hadjicostas, Oct 15 2017: (Start)
a(n) = (n/2)*Sum_{d|n} (phi^(-1)(d)/d)*b(n/d), where phi^(-1)(n) = A023900(n) is the Dirichlet inverse of the Euler totient function and b(n) = A029744(n+1) (= 3*2^((n/2)-1), if n is even, and = 2^((n+1)/2), if n is odd).
G.f.: Sum_{n>=1} phi^(-1)(n)*g(x^n), where phi^(-1)(n) = A023900(n) and g(x) = x*(x+1)*(2*x+1)/(1-2*x^2)^2.
(End)

a(11) - a(24) from Robert G. Wilson v, Aug 25 2010
a(25) - a(27) from Robert G. Wilson v, Aug 29 2010
Terms a(28) and beyond from Andrew Howroyd, Oct 07 2017

A180322 a(n) = AR(n) is the total number of aperiodic k-reverses of n.

Original entry on oeis.org

1, 1, 3, 6, 15, 21, 49, 72, 126, 195, 341, 486, 819, 1225, 1845, 2880, 4335, 6552, 9709, 14850, 21315, 33077, 47081, 72360, 102300, 158067, 220752, 341334, 475107, 732735, 1015777, 1566720, 2161599, 3333615, 4587135, 7062552, 9699291, 14922733, 20444697

Offset: 1

John P. McSorley, Aug 27 2010

nonn

The n-th term of this sequence a(n) = AR(n) gives the total number of aperiodic k-reverses of n for k=1,2,...,n. It is the sum of the n-th row of the 'AR(n,k)' triangle from sequence A180279.
See sequence A180279 for the definition of an aperiodic k-reverse of n.
Briefly, a k-reverse of n is a k-composition of n whose reverse is cyclically equivalent to itself, and an aperiodic k-reverse of n is a k-reverse of n which is also aperiodic.
For example a(6)=21 because there are 21 aperiodic k-reverses of n=6 for k=1,2,3,4,5, or 6.
They are, in cyclically equivalent classes: {6}, {15,51}, {24,42}, {114,411,141}, {1113,3111,1311,1131}, {1122,2112,2211,1221},{11112,21111,12111,11211,11121}.

John P. McSorley: Counting k-compositions with palindromic and related structures. Preprint, 2010.

Andrew Howroyd, Table of n, a(n) for n = 1..200

If we ask for the number of cyclically equivalent classes we get sequence A056493 (except for the first term). For example, the 6th term of A056493 is 7, corresponding to the 7 classes in the example above.

Row sums of A180279.

a[n_] := n*Sum[MoebiusMu[n/d]*If[OddQ[d], 2, 3]*2^Quotient[d-1, 2], {d, Divisors[n]}]/2;
Array[a, 40] (* Jean-François Alcover, Jul 06 2018, after Andrew Howroyd *)

a(n) = n * sumdiv(n, d, moebius(n/d) * if(d%2,2,3) * 2^((d-1)\2)) / 2; \\ Andrew Howroyd, Oct 07 2017

a(n) = n * A056493(n) / 2. - Andrew Howroyd, Oct 07 2017

Terms a(11) and beyond from Andrew Howroyd, Oct 07 2017

A180424 "ARE(n,k)" triangle read by rows. ARE(n,k) is the number of aperiodic k-reverses of n up to cyclic equivalence.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 1, 2, 1, 0, 1, 3, 3, 3, 3, 1, 0, 1, 3, 3, 4, 3, 3, 1, 0, 1, 4, 3, 6, 6, 3, 4, 1, 0, 1, 4, 4, 8, 5, 8, 4, 4, 1, 0, 1, 5, 5, 10, 10, 10, 10, 5, 5, 1, 0, 1, 5, 4, 12, 10, 17, 10, 12, 4, 5, 1, 0

Offset: 1

John P. McSorley, Sep 03 2010

A k-composition of n is an ordered collection of k positive integers (parts) which sum to n.
A k-composition is aperiodic (primitive) if its period is k, or if it is not the concatenation of at least two smaller compositions.
Two k-compositions are cyclically equivalent if one can be obtained from the other by a cyclic permutation of its parts.
The reverse of a k-composition is the k-composition obtained by writing its parts in reverse. For example, the reverse of 123 is 321.
A k-reverse of n is a k-composition of n which is cyclically equivalent to its reverse. And an aperiodic k-reverse of n is a k-reverse of n which is aperiodic.
For example, 114 is an aperiodic 3-reverse of 6 since it is aperiodic and its set of cyclic equivalents {114,411,141} contains its reverse 411.
But 123 is not an aperiodic 3-reverse of 6 since, even though it is aperiodic, its set of cyclic equivalents {123,312,231} does not contain its reverse 321.
Let AR(n,k) denote the number of aperiodic k-reverses of n, then sequence A180279 is the 'AR(n,k)' triangle read by rows.
For the above sequence we count the aperiodic k-reverses of n up to cyclic equivalence, ARE(n,k), in other words, the number of equivalence classes under cyclic permutation which contain at least one aperiodic k-reverse of n.

			The triangle begins
  1
  1 0
  1 1 0
  1 1 1 0
  1 2 2 1 0
  1 2 1 2 1 0
  1 3 3 3 3 1 0
  1 3 3 4 3 3 1 0
  1 4 3 6 6 3 4 1 0
  1 4 4 8 5 8 4 4 1 0
For example, row 8 is 1 3 3 4 3 3 1 0.
We have ARE(8,3)=3 because there are 9 aperiodic 3-reverses of 8 in the 3 classes {116,611,161}, {224,422,242}, and {233,323,332}, and so there are ARE(8,3)=3 aperiodic 3-reverses of 8 up to cyclic equivalence.
We have ARE(8,6)=3 because there are 3 aperiodic 6-reverses of 8 up to cyclic equivalence. The representatives of the 3 classes are 111113, 111122, and 111212.

John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010.

Andrew Howroyd, Table of n, a(n) for n = 1..1275

As mentioned above, if we don't count the classes, but rather the elements in the classes, we get sequence A180279.
If we remove the aperiodic requirement, see sequence A119963.
The row sums of the "ARE(n, k)" triangle above give sequence A056493 (except for the first term). See also sequence A056498.

Table[DivisorSum[GCD[n, k], MoebiusMu[#]*Binomial[Floor[((n/#) - Boole[OddQ[k/#]])/2], Floor[k/(2 #)]] &], {n, 12}, {k, n}] // Flatten (* Michael De Vlieger, Oct 31 2021 *)

\\ here RE(n,k) is A119963(n,k).
RE(n,k) = binomial((n-k%2)\2, k\2);
T(n,k) = sumdiv(gcd(n,k), d, moebius(d)*RE(n/d,k/d));
for(n=1, 10, for(k=1, n, print1(T(n,k), ", ")); print) \\ Andrew Howroyd, Oct 07 2017

ARE(n,k) = Sum_{d|gcd(n,k)} mu(d) * A119963(n/d,k/d). - Andrew Howroyd, Oct 07 2017

Terms a(56) and beyond from Andrew Howroyd, Oct 07 2017

A203399 T(n, k), a triangular array read by rows, is the number of classes of equivalent 2-color n-bead necklaces (turning over is allowed) that contain k necklaces.

Original entry on oeis.org

2, 0, 2, 1, 0, 0, 2, 0, 2, 0, 0, 0, 2, 1, 0, 3, 0, 0, 0, 0, 2, 0, 0, 0, 6, 0, 0, 0, 0, 0, 2, 1, 2, 0, 0, 7, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 14, 0, 0, 0, 0, 0, 0, 2, 2, 1, 0, 3, 0, 0, 0, 18, 0, 0, 0, 0, 0, 0, 0, 6, 2, 0, 2, 0, 0, 0, 0, 0, 28, 0, 0, 0, 0, 0, 0, 0, 0, 14, 2, 1, 0, 0, 6, 0, 0, 0, 0, 39, 0, 0, 0, 0, 0, 0, 0, 0, 0, 30

Offset: 1

Geoffrey Critzer, Jan 01 2012

Equivalently, the dihedral group of order n acts on the set of length n binary sequences. T(n,k) is the number of orbits that contain k elements.

By "n-bead necklaces (turning over is allowed)" the author means "bracelets". By saying that the classes of these n-bead bracelets (turnover necklaces) "contain k necklaces" the author means that the classes "contain k marked necklaces". - Petros Hadjicostas, Jun 06 2019

			Triangle begins (with rows n >= 1 and columns k >= 1):
  2  0
  2  1  0  0
  2  0  2  0  0  0
  2  1  0  3  0  0  0  0
  2  0  0  0  6  0  0  0  0  0
  2  1  2  0  0  7  0  0  0  0  0  1
  2  0  0  0  0  0 14  0  0  0  0  0  0  2
  2  1  0  3  0  0  0 18  0  0  0  0  0  0  0  6
  2  0  2  0  0  0  0  0 28  0  0  0  0  0  0  0  0 14
From _Petros Hadjicostas_, Jun 07 2019: (Start)
Consider all bracelets (turnover necklaces) of two colors (B and W) that can be generated using one of Ruskey's websites above. We keep his numbering, declare whether it has reflexive symmetry or not (achiral or chiral, resp.), and find its value of k (= number of different marked necklaces belonging to its equivalence class).
We have: (1) BBBBBB (k=1, achiral), (2) BBBBBW (k=6, achiral), (3) BBBBWW (k=6, achiral), (4) BBBWBW (k=6, achiral), (5) BBBWWW (k=6, achiral), (6) BBWBBW (k=3, achiral), (7) BBWBWW (k=12, chiral), (8) BBWWWW (k=6, achiral), (9) BWBWBW (k=2, achiral), (10) BWBWWWW (k=6, achiral), (11) BWWBWW (k=3, achiral), (12) BWWWWW (k=6, achiral), (13) WWWWWW (k=1, achiral).
Hence, only bracelet (7) has no reflection symmetry, and thus it is chiral. The k=12 marked necklaces of its equivalence class are as follows:
BBWBWW, WBBWBW, WWBBWB, BWWBBW, WBWWBB, BWBWWB, and their mirror images BWWBWB, BBWWBW, WBBWWB, BWBBWW, WBWBBW, WWBWBB.
We see that T(n=6, k=1) = 2, T(n=6, k=2) = 1, T(n=6, k=3) = 2, T(n=6, k=6) = 7, and T(n=6, k=12) = 1, which agree with line n=6 in the triangle above. (End)

Petros Hadjicostas, Table of n, a(n) for n = 1..210, flattened.
Petros Hadjicostas, Formulas for chiral bracelets, 2019.
S. Karim, J. Sawada, Z. Alamgirz, and S. M. Husnine, Generating bracelets with fixed content, 2011.
S. Karim, J. Sawada, Z. Alamgirz, and S. M. Husnine, Generating bracelets with fixed content, Theoretical Computer Science, Volume 475, 4 March 2013, Pages 103-112.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Frank Ruskey, Combinatorial Generation Algorithm Algorithm 4.24, p. 95.
Joe Sawada, Generating bracelets in constant amortized time, SIAM J. Comput. 31 (2001), 259-268.
R. M. Thompson and R. T. Downs, Systematic generation of all nonequivalent closest packed stacking sequences of length N using group theory, Acta Cryst. B57 (2001), 766-771; B58 (2002), 153.

Cf. A000029 (row sums), A032239 (T(n, 2n) for n >= 3), A056493, A203398.

Needs["Combinatorica`"];
f[list_]:= Sort[NestList[RotateLeft, list, Length[list]-1] ~Join~NestList[RotateLeft, Reverse[list], Length[list]-1]]; Flatten[Table[Distribution[Map[Length, Map[Union, Union[Map[f, Strings[{0, 1}, n]]]]], Range[2 n]], {n, 1, 10}]]

From Petros Hadjicostas, Jun 06 2019: (Start)
Conjectures: For n >= 1, let b(n) be the number of bracelets of two colors with n beads that are either periodic (period >= 2), or have reflection symmetry (achiral), or both. Then b(n) = A000029(n) - A032239(n) for n >= 3 with b(n) = A000029(n) for n = 1, 2. We have A000029(n) = 2^floor(-3 + n/2) * (7 - (-1)^n) + (1/(2*n)) * Sum_{d|n} phi(d) * 2^(n/d) for n >= 1 and A032239(n) = (1/2) * Sum_{d|n} mu(d) * (-2^floor(-2 + (n/(2*d))) * (7 - (-1)^(n/d)) + 2^(n/d)/n) for n >= 3.
For 1 <= k <= n, we conjecture that T(n, k) = Sum_{d|k} mu(d)*b(k/d) for k|n, and = 0 otherwise. Note that, if 3 <= n <= 11, we have T(n, k) = A056493(k) when k|n, but this is not true (for example) for n = 12 and n = 14. We have T(12, 12) = 82 <> 81 = A056493(12) and T(14, 14) = 177 <> 175 = A056493(14).
Apparently, T(n, 2*n) = A032239(n) for all n >= 3, and T(n, k) = 0 for n < k < 2*n. (End)
From Petros Hadjicostas, Jun 16 2019: (Start)
I ran the author's Mathematica program for n = 1..21 and I saw that the conjecture is OK except for n = 18 and n = 21. The program gives T(n=18, k=12) = 1 and T(n=18, k=18) = 742 while my conjecture implies that T(n=18, k=12) = 0 (since k = 12 does not divide n = 18) and T(n=18, k=18) = 743. In addition, the program gives T(n=21, k=14) = 2 and T(n=21, k=21) = 2030, while my conjecture implies that T(n=21, k=14) = 0 (since k = 14 does not divide n = 21) and T(n=21, k=21) = 2032. Apparently, my conjecture needs to be refined.
For n = 18, the single bracelet whose equivalence class has 12 marked necklaces is (BBWBWW)^3 (with period 3).
For n = 21, the two bracelets whose equivalence classes have 14 marked necklaces each are (BBWBWWW)^3 and (WWBWBBB)^3 (each with period 3). (End)

A181314 a(n) = ADPE(n) is the total number of aperiodic k-double-palindromes of n up to cyclic equivalence, where 1 <= k <= n.

Original entry on oeis.org

0, 0, 1, 2, 5, 6, 13, 17, 27, 38, 61, 80, 125, 174, 245, 359, 509, 727, 1021, 1484, 2029, 3006, 4093, 6029, 8183, 12158, 16351, 24380, 32765, 48848, 65533, 97919, 131005, 196094, 262121, 392363, 524285, 785406, 1048445, 1571309, 2097149, 3143496, 4194301, 6288380, 8388323

Offset: 1

John P. McSorley, Oct 12 2010

nonn

a(n) = ADPE(n) is the total number of aperiodic k-double-palindromes of n up to cyclic equivalence. See sequence A181169 for the definitions of an aperiodic k-double-palindrome of n and of cyclic equivalence.
Sequence A181169 is the 'ADPE(n,k)' triangle read by rows where ADPE(n,k) is the number of aperiodic k-double-palindromes of n up to cyclic equivalence.
For example, we have a(6) = ADPE(6) = ADPE(6,1) + ADPE(6,2) + ADPE(6,3) + ADPE(6,4) + ADPE(6,5) + ADPE(6,6) = 0 + 2 + 1 + 2 + 1 + 0 = 6. The 6 aperiodic double-palindromes of 6 up to cyclic equivalence are: 15, 24, 114, 1113, 1122, 11112. They are the representatives of the cyclic equivalence classes: {15,51}, {24,42}, {114,411,141},{1113,3111,1311,1131}, {1122,2112,2211,1221} and {11112,21111,12111,11211,11121}.
Hence a(n) = ADPE(n) is the total number of cyclic equivalence classes of compositions of n containing at least one aperiodic double-palindrome of n.

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Row sums of A181169.
If we remove the aperiodic requirement, we get sequence A027383, see the comment from McSorley there. Also see sequences A181111 and A181135.
Cf. A056493.

a(n)={sumdiv(n, d, moebius(n/d)*((3 + d%2)*2^(d\2-1) - 1)) - 1} \\ Andrew Howroyd, Sep 28 2019

From Andrew Howroyd, Sep 28 2019: (Start)
a(n) = A056493(n) - 1 for n > 1.
G.f.: (x^2-2*x)/(1-x) + Sum_{k=1..n} mu(k)*x^k*(2 + 3*x^k)/(1 - 2*x^(2*k)).
(End)

Terms a(11) and beyond from Andrew Howroyd, Sep 27 2019

cp's OEIS Frontend

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

A007055 Let S denote the palindromes in the language {0,1}*; a(n) = number of words of length n in the language SS.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A284856 Array read by antidiagonals: T(n,k) = number of aperiodic necklaces (Lyndon words) with n beads and k colors that are the same when turned over.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A180249 a(n) is the total number of k-reverses of n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A180322 a(n) = AR(n) is the total number of aperiodic k-reverses of n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A180424 "ARE(n,k)" triangle read by rows. ARE(n,k) is the number of aperiodic k-reverses of n up to cyclic equivalence.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs