A000016 -id:A000016 - cp's OEIS frontend

A007147 Number of self-dual 2-colored necklaces with 2n beads.

1, 1, 2, 2, 4, 5, 9, 12, 23, 34, 63, 102, 190, 325, 612, 1088, 2056, 3771, 7155, 13364, 25482, 48175, 92205, 175792, 337594, 647326, 1246863, 2400842, 4636390, 8956060, 17334801, 33570816, 65108062, 126355336, 245492244, 477284182

Offset: 1

N. J. A. Sloane

For n>=4 also number of Napier cycle types for dimension d=n-3. See Böhm link. - Hugo Pfoertner, Oct 01 2013

Also the number of combinatorial types of simplicial neighborly polytopes in dimension 2n - 3 with 2n vertices. This sequence was described before the enumeration of self-dual necklaces: see references. See links for a bijection between the two objects. - Moritz Firsching, Aug 13 2015

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Zhe Sun, T Suenaga, P Sarkar, S Sato, M Kotani, H Isobe, Stereoisomerism, crystal structures, and dynamics of belt-shaped cyclonaphthylenes, Proc. Nath. Acead. Sci. USA, vol. 113 no. 29, pp. 8109-8114, doi: 10.1073/pnas.1606530113

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Oswin Aichholzer and Anna Brötzner, Bicolored Order Types, Comp. Geom. Topology (2024) Vol. 3, No. 2, 3:1-3:17.
Amos Altshuler and Peter McMullen, The number of simplicial neighbourly d-polytopes with d + 3 vertices, Mathematika, 20(02):263-266, 1973., Theorem 1, p. 263.
Johannes Böhm, Generalized hyperbolic Napier cycles and their hyperbolic kernels, Part III, Jenaer Schriften zur Mathematik und Informatik, Math/inf/06/08, 2008.
Moritz Firsching, Realizability and inscribability for some simplicial spheres and matroid polytopes, , arXiv:1508.02531 [math.MG], 2015. See Appendix A1.
Bernd Mulansky and Andreas Potschka, A zonogon approach for computing small polygons of maximum perimeter, arXiv:2404.01841 [math.OC], 2024. See p. 9. See also Math. Program., 2025.
E. M. Palmer and R. W. Robinson, Enumeration of self-dual configurations, Pacific J. Math., 110 (1984), 203-221.
Index entries for sequences related to necklaces

Cf. A000016, A016116, A263768.

a[n_] := (1/2)*(2^Quotient[n-1, 2] + Total[(Mod[#, 2]*EulerPhi[#]*2^(n/#) & ) /@ Divisors[n]]/(2*n)); Table[a[n], {n, 1, 36}] (* Jean-François Alcover, Oct 24 2011, after Pari *)

a(n)= (1/2) *(2^((n-1)\2)+sumdiv(n,k,(k%2)*eulerphi(k)*2^(n/k))/(2*n))

def a(n):
    return 2^floor((n-3)/2)+1/(4*(n))*sum([euler_phi(h)*2^((n)/h) for h in divisors(n) if is_odd(h)])
# Moritz Firsching, Aug 13 2015

a(n) = (1/2) * (A016116(n-1) + A000016(n)).

a(n) = A263768(n) + 1. - Bernd Mulansky, Mar 08 2023

More terms from Michael Somos.

A053545 Comparisons needed for Batcher's sorting algorithm applied to 2^n items.

Original entry on oeis.org

0, 1, 5, 19, 63, 191, 543, 1471, 3839, 9727, 24063, 58367, 139263, 327679, 761855, 1753087, 3997695, 9043967, 20316159, 45350911, 100663295, 222298111, 488636415, 1069547519, 2332033023, 5066719231, 10972299263, 23689428991, 51002736639, 109521666047, 234612588543, 501437431807

Offset: 0

N. J. A. Sloane, Mar 21 2000

Appears to be number of edges in graph where nodes are binary vectors of length n, two nodes u, v being joined by an edge if there's a vector of length n-1 that can be reached from u by deleting a bit and from v by deleting a bit. An independent set in this graph is a code that will correct single deletions.
Binomial transform of A005893: (1, 4, 10, 20, 34, 52, 74, ...) = (1, 5, 19, 63, 191, ...). - Gary W. Adamson, Apr 28 2008
Let A be the Hessenberg matrix of order n defined by: A[1,j]=1, A[i,i]:=2,(i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=2, a(n-1)= (-1)^n*coeff(charpoly(A,x),x^2). - Milan Janjic, Jan 26 2010

Vincenzo Librandi, Table of n, a(n) for n = 0..3000
I. Wegener, The Complexity of Boolean Functions, Wiley, 1987, see p. 151, (2.7).
Index entries for linear recurrences with constant coefficients, signature (7,-18,20,-8).

The size of a maximal independent set in this graph (1, 1, 2, 2, 4, 6, 10, ...) agrees with A000016 for n <= 7 (and probably for n=8).

Cf. A005893, A007466.

[2^(n-2)*(n^2-n+4)-1: n in [0..30]]; // Vincenzo Librandi, Oct 10 2011

A053545:=n->2^(n - 2)*(n^2 - n + 4) - 1; seq(A053545(n), n=0..30); # Wesley Ivan Hurt, Apr 01 2014

Table[2^(n-2)(n^2-n+4)-1,{n,0,30}] (* or *) LinearRecurrence[{7,-18,20,-8},{0,1,5,19},30] (* Harvey P. Dale, Apr 03 2013 *)

a(n)=2^(n-2)*(n^2-n+4)-1 \\ Charles R Greathouse IV, Feb 19 2017

G.f.: x*(1-2x+2x^2)/((1-x)*(1-2x)^3).
a(n) = 2^(n-2)*(n^2-n+4)-1.
Partial sums of A007466. - J. M. Bergot, Jan 20 2013
a(n) = 7*a(n-1) - 18*a(n-2) + 20*a(n-3) - 8*a(n-4); a(0)=0, a(1)=1, a(2)=5, a(3)=19. - Harvey P. Dale, Apr 03 2013

A327477 Number of subsets of {1..n} containing n whose mean is not an element.

Original entry on oeis.org

0, 0, 1, 2, 6, 12, 26, 54, 112, 226, 460, 930, 1876, 3780, 7606, 15288, 30720, 61680, 123786, 248346, 498072, 998636, 2001826, 4011942, 8039072, 16106124, 32263876, 64623330, 129424236, 259179060, 518975176, 1039104990, 2080374784, 4164816708, 8337289456

Offset: 0

Gus Wiseman, Sep 13 2019

nonn

			The a(1) = 1 through a(5) = 12 subsets:
  {1,2}  {1,3}  {1,4}      {1,5}
         {2,3}  {2,4}      {2,5}
                {3,4}      {3,5}
                {1,2,4}    {4,5}
                {1,3,4}    {1,2,5}
                {1,2,3,4}  {1,4,5}
                           {2,3,5}
                           {2,4,5}
                           {1,2,3,5}
                           {1,2,4,5}
                           {1,3,4,5}
                           {2,3,4,5}

Subsets whose mean is an element are A065795.
Subsets whose mean is not an element are A327471.
Subsets containing n whose mean is an element are A000016.
Cf. A007865, A051293, A082550, A135342, A240851, A324741, A327472.

Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&!MemberQ[#,Mean[#]]&]],{n,0,10}]

from sympy import totient, divisors
def A327477(n): return (1<>(~n&n-1).bit_length(),generator=True))//n if n else 0 # Chai Wah Wu, Feb 21 2023

From Alois P. Heinz, Feb 21 2023: (Start)
a(n) = A327471(n) - A327471(n-1) for n>=1.
a(n) = 2^(n-1) - A000016(n) for n>=1. (End)

a(25)-a(34) from Alois P. Heinz, Feb 21 2023

A363527 Number of integer partitions of n with weighted sum 3*n.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 3, 4, 4, 6, 8, 7, 10, 13, 13, 21, 25, 24, 37, 39, 40, 58, 63, 72, 94, 106, 118, 144, 165, 181, 224, 256, 277, 341, 387, 417, 504, 560, 615, 743, 818, 899, 1066, 1171, 1285, 1502, 1655, 1819, 2108, 2315, 2547, 2915

Offset: 0

Gus Wiseman, Jun 11 2023

nonn

Are the partitions counted all of length > 4?

The (one-based) weighted sum of a sequence (y_1,...,y_k) is Sum_{i=1..k} i*y_i. The reverse-weighted sum is the weighted sum of the reverse, also the sum of partial sums. For example, the weighted sum of (4,2,2,1) is 1*4 + 2*2 + 3*2 + 4*1 = 18 and the reverse-weighted sum is 4*4 + 3*2 + 2*2 + 1*1 = 27.

			The partition (2,2,1,1,1,1) has sum 8 and weighted sum 24 so is counted under a(8).
The a(13) = 1 through a(18) = 8 partitions:
  (332221)  (333221)    (33333)     (442222)    (443222)    (443331)
            (4322111)   (522222)    (5322211)   (4433111)   (444222)
            (71111111)  (4332111)   (55111111)  (5332211)   (533322)
                        (63111111)  (63211111)  (55211111)  (4443111)
                                                (63311111)  (7222221)
                                                (72221111)  (55311111)
                                                            (64221111)
                                                            (A11111111)

The version for compositions is A231429.
The reverse version is A363526.
These partitions have ranks A363531.
A000041 counts integer partitions, strict A000009.
A053632 counts compositions by weighted sum, rank statistic A029931/A359042.
A264034 counts partitions by weighted sum, reverse A358194.
A304818 gives weighted sum of prime indices, row-sums of A359361.
A318283 gives weighted sum of reversed prime indices, row-sums of A358136.
A320387 counts multisets by weighted sum, zero-based A359678.
Cf. A000016, A008284, A067538, A222855, A222970, A359755, A360672, A360675, A362559, A362560, A363525, A363528, A363532.

Table[Length[Select[IntegerPartitions[n],Total[Accumulate[Reverse[#]]]==3n&]],{n,0,30}]

A054601 a(n) = Sum_{d|n, d odd} d*2^(n/d - 1), a(0)=0.

Original entry on oeis.org

0, 1, 2, 7, 8, 21, 38, 71, 128, 277, 522, 1035, 2072, 4109, 8206, 16467, 32768, 65553, 131186, 262163, 524328, 1048817, 2097174, 4194327, 8388992, 16777321, 33554458, 67109695, 134217784, 268435485, 536872638, 1073741855, 2147483648

Offset: 0

N. J. A. Sloane, Apr 16 2000

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A054598, A054599, A054600, A000016, A000031.

a(n) = if (n, sumdiv(n, d, if (d%2, d*2^(n/d - 1))), 0); \\ Michel Marcus, Mar 10 2021

G.f.: Sum_{k>0} (1-(-1)^k)/2*k*x^k/(1-2*x^k). - Vladeta Jovovic, Oct 17 2003

A327478 Numbers whose average binary index is also a binary index.

Original entry on oeis.org

1, 2, 4, 7, 8, 14, 16, 21, 28, 31, 32, 39, 42, 56, 57, 62, 64, 73, 78, 84, 93, 107, 112, 114, 124, 127, 128, 141, 146, 155, 156, 168, 175, 177, 186, 214, 217, 224, 228, 245, 248, 254, 256, 267, 273, 282, 287, 292, 310, 312, 313, 336, 341, 350, 354, 371, 372

Offset: 1

Gus Wiseman, Sep 13 2019

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

			The sequence of terms together with their binary indices begins:
   1: 1
   2: 2
   4: 3
   7: 1 2 3
   8: 4
  14: 2 3 4
  16: 5
  21: 1 3 5
  28: 3 4 5
  31: 1 2 3 4 5
  32: 6
  39: 1 2 3 6
  42: 2 4 6
  56: 4 5 6
  57: 1 4 5 6
  61: 2 3 4 5 6

Numbers whose binary indices have integer mean are A326669.

Cf. A000016, A000120, A029931, A048793, A065795, A070939, A237984, A240850, A327473, A327474, A327481.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[100],MemberQ[bpe[#],Mean[bpe[#]]]&]

A054600 Sum_{d|n, d odd} d*2^(n/d).

Original entry on oeis.org

0, 2, 4, 14, 16, 42, 76, 142, 256, 554, 1044, 2070, 4144, 8218, 16412, 32934, 65536, 131106, 262372, 524326, 1048656, 2097634, 4194348, 8388654, 16777984, 33554642, 67108916, 134219390, 268435568, 536870970, 1073745276, 2147483710

Offset: 0

N. J. A. Sloane, Apr 16 2000

nonn

Cf. A054598-A054601, A000016, A000031.

f[n_]:=With[{od=Select[Divisors[n],OddQ]},Total[od 2^(n/od)]]; Join[{0}, Array[f, 40]] (* Harvey P. Dale, Aug 31 2024 *)

A057608 Maximal size of binary code of length n that corrects one transposition (end-around transposition not included).

Original entry on oeis.org

1, 2, 3, 4, 8, 12, 20, 38, 63, 110, 196, 352

Offset: 0

N. J. A. Sloane, Oct 09 2000

S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk, Estimating the size of correcting codes using extremal graph problems, Optimization, 227-243, Springer Optim. Appl., 32, Springer, New York, 2009.
N. J. A. Sloane, On single-deletion-correcting codes, in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.

José Manuel Gómez Soto, Jesús Leaños, Luis Manuel Ríos-Castro, Luis Manuel Rivera, On an error-correcting code problem, arXiv:1711.03682 [math.CO], 2017.
N. J. A. Sloane, On single-deletion-correcting codes
N. J. A. Sloane, Challenge Problems: Independent Sets in Graphs

Cf. A057657, A000016, A057591, A010101. Row sums of A085684.

a(9) = 110 from Butenko et al., Nov 28 2001 (see reference).
a(9) = 110 also from Ketan Narendra Patel (knpatel(AT)eecs.umich.edu), Apr 29 2002. Confirmed by N. J. A. Sloane, Jul 07 2003
a(10) >= 196 and a(11) >= 352 from Butenko et al., Nov 28 2001 (see reference).
a(10) = 196 found by N. J. A. Sloane, Jul 17 2003
a(11) = 352 proved by Brian Borchers (borchers(AT)nmt.edu), Oct 16 2009

A057657 Maximal size of binary code of length n that corrects one transposition (end-around transposition included).

Original entry on oeis.org

2, 3, 4, 5, 8, 18, 28, 50, 100, 171, 316

Offset: 1

N. J. A. Sloane, Oct 15 2000

S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk, Estimating the size of correcting codes using extremal graph problems, Optimization, 227-243,
Springer Optim. Appl., 32, Springer, New York, 2009.
N. J. A. Sloane, On single-deletion-correcting codes, in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.

N. J. A. Sloane, Challenge Problems: Independent Sets in Graphs
N. J. A. Sloane, On single-deletion-correcting codes

Cf. A057608, A000016, A057591. Row sums of A085685.

Typo in a(8) corrected and a(9) added, Jul 09 2003
a(9) = 100 from Butenko et al., Nov 28 2001 (see reference). Confirmed by N. J. A. Sloane, Jul 09 2003
a(10) >= 171 and a(100) >= 316 from Butenko et al., Nov 28 2001 (see reference).
a(10) = 171 from Brian Borchers (borchers(AT)nmt.edu), Apr 14 2005
a(11) = 316 from Brian Borchers (borchers(AT)nmt.edu), Nov 04 2009

A115114 Asymmetric rhythm cycles (patterns): binary necklaces of length 2n subject to the restriction that for any k if the k-th bead is of color 1 then the (k+n)-th bead (modulo 2n) is of color 0.

Original entry on oeis.org

2, 3, 6, 11, 26, 63, 158, 411, 1098, 2955, 8054, 22151, 61322, 170823, 478318, 1345211, 3798242, 10761723, 30585830, 87169619, 249056138, 713205903, 2046590846, 5883948951, 16945772210, 48882035163, 141214768974

Offset: 1

Valery A. Liskovets, Jan 17 2006

			For n=3, the 27=3^3 admissible words are separated into 6 shift-equivalence classes (necklaces) containing, resp., the words 000000, 100000, 110000, 101000, 111000 and 101010. Thus a(3)=6.

R. W. Hall and P. Klingsberg, Asymmetric Rhythms, Tiling Canons and Burnside's Lemma, Bridges Proceedings, pp. 189-194, 2004 (Winfield, Kansas).
R. W. Hall and P. Klingsberg, Asymmetric Rhythms and Tiling Canons, Preprint, 2004; The American Mathematical Monthly, Volume 113, 2006 - Issue 10, [alternative link].

Cf. A000016, A006575.

a[n_] := Sum[EulerPhi[2d] + Boole[OddQ[d]] EulerPhi[d] 3^(n/d), {d, Divisors[n]}]/(2n);
Array[a, 27] (* Jean-François Alcover, Aug 29 2019 *)

a(n) = (Sum_{d|n}phi(2d)+Sum_{d|n, d odd}phi(d)3^(n/d))/(2n), where phi(n) is the Euler function A000010.

a(n) ~ 3^n/(2*n). - Vaclav Kotesovec, Oct 27 2024

cp's OEIS Frontend

A007147 Number of self-dual 2-colored necklaces with 2n beads.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

Extensions

A053545 Comparisons needed for Batcher's sorting algorithm applied to 2^n items.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A327477 Number of subsets of {1..n} containing n whose mean is not an element.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A363527 Number of integer partitions of n with weighted sum 3*n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A054601 a(n) = Sum_{d|n, d odd} d*2^(n/d - 1), a(0)=0.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A327478 Numbers whose average binary index is also a binary index.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A054600 Sum_{d|n, d odd} d*2^(n/d).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A057608 Maximal size of binary code of length n that corrects one transposition (end-around transposition not included).

Views

Author

Keywords

References

Links

Crossrefs