A269134 -id:A269134 - cp's OEIS frontend

A059966 a(n) = (1/n) * Sum_{ d divides n } mu(n/d) * (2^d - 1).

1, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630, 1161, 2182, 4080, 7710, 14532, 27594, 52377, 99858, 190557, 364722, 698870, 1342176, 2580795, 4971008, 9586395, 18512790, 35790267, 69273666, 134215680, 260300986, 505286415, 981706806

Offset: 1

Roland Bacher, Mar 05 2001

Dimensions of the homogeneous parts of the free Lie algebra with one generator in 1,2,3, etc. (Lie analog of the partition numbers).
This sequence is the Lie analog of the partition sequence (which gives the dimensions of the homogeneous polynomials with one generator in each degree) or similarly, of the partitions into distinct (or odd numbers) (which gives the dimensions of the homogeneous parts of the exterior algebra with one generator in each dimension).
The number of cycles of length n of rectangle shapes in the process of repeatedly cutting a square off the end of the rectangle. For example, the one cycle of length 1 is the golden rectangle. - David Pasino (davepasino(AT)yahoo.com), Jan 29 2009
In music, the number of distinct rhythms, at a given tempo, produced by a continuous repetition of measures with identical patterns of 1's and 0's (where 0 means no beat, and 1 means one beat), where each measure allows for n possible beats of uniform character, and when counted under these two conditions: (i) the starting and ending times for the measure are unknown or irrelevant and (ii) identical rhythms that can be produced by using a measure with fewer than n possible beats are excluded from the count. - Richard R. Forberg, Apr 22 2013
Richard R. Forberg's comment does not hold for n=1 because a(1)=1 but there are the two possible rhythms: "0" and "1". - Herbert Kociemba, Oct 24 2016
The comment does hold for n=1 as the rhythm "0" can be produced by using a measure of 0 beats and so is properly excluded from a(1)=1 by condition (ii) of the comment. - Travis Scott, May 28 2022
a(n) is also the number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n. - Gus Wiseman, Dec 19 2017
Mobius transform of A008965. - Jianing Song, Nov 13 2021
a(n) is the number of cycles of length n for the map x->1 - abs(2*x-1) applied on rationals 0Michel Marcus, Jul 16 2025

			a(4)=3: the 3 elements [a,c], [a[a,b]] and d form a basis of all homogeneous elements of degree 4 in the free Lie algebra with generators a of degree 1, b of degree 2, c of degree 3 and d of degree 4.
From _Gus Wiseman_, Dec 19 2017: (Start)
The sequence of Lyndon compositions organized by sum begins:
  (1),
  (2),
  (3),(12),
  (4),(13),(112),
  (5),(14),(23),(113),(122),(1112),
  (6),(15),(24),(114),(132),(123),(1113),(1122),(11112),
  (7),(16),(25),(115),(34),(142),(124),(1114),(133),(223),(1213),(1132),(1123),(11113),(1222),(11212),(11122),(111112). (End)

C. Reutenauer, Free Lie algebras, Clarendon press, Oxford (1993).

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Nicolas Andrews, Lucas Gagnon, Félix Gélinas, Eric Schlums, and Mike Zabrocki, When are Hopf algebras determined by integer sequences?, arXiv:2505.06941 [math.CO], 2025. See p. 17.
S. V. Duzhin and D. V. Pasechnik, Groups acting on necklaces and sandpile groups, Journal of Mathematical Sciences, August 2014, Volume 200, Issue 6, pp 690-697. See page 85. - N. J. A. Sloane, Jun 30 2014
Seok-Jin Kang and Myung-Hwan Kim, Free Lie Algebras, Generalized Witt Formula and the Denominator Identity, Journal of Algebra 183, 560-594 (1996).
Michael J. Mossinghoff and Timothy S. Trudgian, A tale of two omegas, arXiv:1906.02847 [math.NT], 2019.
G. Niklasch, Some number theoretical constants: 1000-digit values [Cached copy]
Jakob Oesinghaus, Quasi-symmetric functions and the Chow ring of the stack of expanded pairs, arXiv:1806.10700 [math.AG], 2018.
Robert Schneider, Andrew V. Sills, and Hunter Waldron, On the q-factorization of power series, arXiv:2501.18744 [math.CO], 2025. See p. 6.

Apart from initial terms, same as A001037.

Cf. A000225, A000740, A008683, A008965, A011782, A060223, A185700, A228369, A269134 A281013, A296302, A296373.

a059966 n = sum (map (\x -> a008683 (n `div` x) * a000225 x)
                     [d | d <- [1..n], mod n d == 0]) `div` n
-- Reinhard Zumkeller, Nov 18 2011

Table[1/n Apply[Plus, Map[(MoebiusMu[n/# ](2^# - 1)) &, Divisors[n]]], {n, 20}]
(* Second program: *)
Table[(1/n) DivisorSum[n, MoebiusMu[n/#] (2^# - 1) &], {n, 35}] (* Michael De Vlieger, Jul 22 2019 *)

from sympy import mobius, divisors
def A059966(n): return sum(mobius(n//d)*(2**d-1) for d in divisors(n,generator=True))//n # Chai Wah Wu, Feb 03 2022

G.f.: Product_{n>0} (1-q^n)^a(n) = 1-q-q^2-q^3-q^4-... = 2-1/(1-q).
Inverse Euler transform of A011782. - Alois P. Heinz, Jun 23 2018
G.f.: Sum_{k>=1} mu(k)*log((1 - x^k)/(1 - 2*x^k))/k. - Ilya Gutkovskiy, May 19 2019
a(n) ~ 2^n / n. - Vaclav Kotesovec, Aug 10 2019
Dirichlet g.f.: f(s+1)/zeta(s+1) - 1, where f(s) = Sum_{n>=1} 2^n/n^s. - Jianing Song, Nov 13 2021

Explicit formula from Paul D. Hanna, Apr 15 2002

Description corrected by Axel Kleinschmidt, Sep 15 2002

A281113 Number of twice-factorizations of n. Number of ways to choose a postpositive factorization of each part of a postpositive factorization of n.

Original entry on oeis.org

1, 1, 3, 1, 3, 1, 6, 3, 3, 1, 9, 1, 3, 3, 15, 1, 9, 1, 9, 3, 3, 1, 23, 3, 3, 6, 9, 1, 12, 1, 28, 3, 3, 3, 32, 1, 3, 3, 23, 1, 12, 1, 9, 9, 3, 1, 58, 3, 9, 3, 9, 1, 23, 3, 23, 3, 3, 1, 41, 1, 3, 9, 66, 3, 12, 1, 9, 3, 12, 1, 84, 1, 3, 9, 9, 3, 12, 1, 58, 15, 3

Offset: 2

Gus Wiseman, Jan 14 2017

nonn

A postpositive number is a positive integer other than 1. A postpositive factorization of n is a finite orderless sequence of postpositive numbers whose product is n.

			The a(20)=9 twice-factorizations are: ((20)), ((2*10)), ((4*5)), ((2*2*5)), ((2)*(10)), ((2)*(2*5)), ((4)*(5)), ((2*2)*(5)), ((2)*(2)*(5)).
Twice-factorizations of 32 organized by composite:
((2)(2)(2)(2)(2)) ((2)(2)(2)(2 2)) ((2)(2)(2 2 2)) ((2)(2 2)(2 2)) ((2)(2 2 2 2)) ((2 2)(2 2 2)) ((2 2 2 2 2))
((2)(2)(2)(4))    ((2)(2)(2 4))    ((2)(2 2)(4))   ((2)(4)(2 2))   ((2)(2 2 4))   ((2 2)(2 4))   ((4)(2 2 2))  ((2 2 2 4))
((2)(2)(8))       ((2)(2 8))       ((2 2)(8))      ((2 2 8))
((2)(4)(4))       ((2)(4 4))       ((4)(2 4))      ((2 4 4))
((2)(16))         ((2 16))
((4)(8))          ((4 8))
((32)).
Twice-factorizations of 32 organized by domain:
((2)(2)(2)(2)(2))
((2)(2)(2)(2 2)) ((2)(2)(2)(4))
((2)(2)(2 2 2))  ((2)(2)(2 4)) ((2)(2)(8))
((2)(2 2)(2 2))  ((2)(2 2)(4)) ((2)(4)(2 2)) ((2)(4)(4))
((2)(2 2 2 2))   ((2)(2 2 4))  ((2)(2 8))    ((2)(4 4))   ((2)(16))
((2 2)(2 2 2))   ((2 2)(2 4))  ((2 2)(8))    ((4)(2 2 2)) ((4)(2 4)) ((4)(8))
((2 2 2 2 2))    ((2 2 2 4))   ((2 2 8))     ((2 4 4))    ((2 16))   ((4 8)) ((32)).

Michael De Vlieger, Table of n, a(n) for n = 2..30030
Michael De Vlieger, Indices of records in A281113.

Cf. A001055(n) = number of factorizations of n, A050336(n) = number of orderless twice-factorizations of n, A162247(n) = factors of factorizations of n, A063834(n) = a(p^(n-1)), A007716, A269134, A281116.

postfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[postfacs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
twicefacs[n_]:=Join@@Tuples/@Map[postfacs,postfacs[n],{2}];
Table[Length[twicefacs[n]],{n,2,24}]

A102726 Number of compositions of the integer n into positive parts that avoid a fixed pattern of three letters.

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 31, 60, 114, 214, 398, 732, 1334, 2410, 4321, 7688, 13590, 23869, 41686, 72405, 125144, 215286, 368778, 629156, 1069396, 1811336, 3058130, 5147484, 8639976, 14463901, 24154348, 40244877, 66911558, 111026746, 183886685, 304034456, 501877227

Offset: 0

Herbert S. Wilf, Feb 07 2005

The sequence is the same no matter which of the six patterns of three letters is chosen as the one to be avoided.

			a(6) = 31 because there are 32 compositions of 6 into positive parts and only one of these, namely 6 = 1+2+3, contains the pattern (123), the other 31 compositions of 6 avoid that pattern.

Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..900 (first 400 terms from Alois P. Heinz)
M. Elder and V. Vatter, Problems and conjectures presented at the third international conference on permutation petterns
Carla D. Savage and Herbert S. Wilf, Pattern avoidance in compositions and multiset permutations, Advances in Applied Mathematics 36 (2006), pp.194-201.
Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

The version for patterns is A226316.
These compositions are ranked by the complement of A335479.
The matching version is A335514.
The version for prime indices is A335521.
Constant patterns are counted by A000005 and ranked by A272919.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Compositions are counted by A011782.
Strict compositions are counted by A032020 and ranked by A233564.
Patterns matched by compositions are counted by A335456.
Minimal patterns avoided by a given composition are counted by A335465.
Cf. A056986, A106356, A232464, A269134, A333755.

b:= proc(n, m, t) option remember; `if`(n=0, 1,
      add(b(n-i, min(m, i, n-i), min(t, n-i,
      `if`(i>m, i, t))), i=1..min(n, t)))
    end:
a:= n-> b(n$3):
seq(a(n), n=0..50);  # Alois P. Heinz, Mar 18 2014

b[n_, m_, t_] := b[n, m, t] = If[n == 0, 1, Sum[b[n - i, Min[m, i, n - i], Min[t, n - i, If[i > m, i, t]]], {i, 1, Min[n, t]}]];
a[n_] := b[n, n, n];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Nov 10 2017, after Alois P. Heinz *)
mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MemberQ[Union[mstype/@Subsets[#]],{1,2,3}]&]],{n,0,10}] (* Gus Wiseman, Jun 22 2020 *)

seq(n)={Vec(sum(i=1, n, prod(j=1, n, if(i==j, 1, (1-x^i)/((1-x^(j-i))*(1-x^i-x^j))) + O(x*x^n))/(1-x^i)))} \\ Andrew Howroyd, Dec 31 2020

G.f.: Sum_{i>=1} (1/(1-x^i))*Product_{j>=1, j<>i} (1-x^i)/((1-x^(j-i))*(1-x^i-x^j)).

Asymptotics (Savage and Wilf, 2005): a(n) ~ c * ((1+sqrt(5))/2)^n, where c = r/(r-1)/(r-s) * (r * Product_{j>=3} (1-1/r)/(1-r^(1-j))/(1-1/r-r^(-j)) - Product_{j>=3} (1-1/r^2)/(1-r^(2-j))/(1-1/r^2-r^(-j)) ) = 18.9399867283479198666671671745270505487677312850521421513193261105... and r = (1+sqrt(5))/2, s = (1-sqrt(5))/2. - Vaclav Kotesovec, May 02 2014

More terms from Ralf Stephan, May 27 2005

A335456 Number of normal patterns matched by compositions of n.

Original entry on oeis.org

1, 2, 5, 12, 32, 84, 211, 556, 1446, 3750, 9824, 25837, 67681, 178160, 468941, 1233837, 3248788, 8554709

Offset: 0

Gus Wiseman, Jun 16 2020

A composition of n is a finite sequence of positive integers summing to n.

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			The 8 compositions of 4 together with the a(4) = 32 patterns they match:
  4:   31:   13:   22:   211:   121:   112:   1111:
-----------------------------------------------------
  ()   ()    ()    ()    ()     ()     ()     ()
  (1)  (1)   (1)   (1)   (1)    (1)    (1)    (1)
       (21)  (12)  (11)  (11)   (11)   (11)   (11)
                         (21)   (12)   (12)   (111)
                         (211)  (21)   (112)  (1111)
                                (121)

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

References found in the link are not all included here.
The version for standard compositions is A335454.
The contiguous case is A335457.
The version for Heinz numbers of partitions is A335549.
Patterns are counted by A000670 and ranked by A333217.
The n-th composition has A124771(n) distinct consecutive subsequences.
Knapsack compositions are counted by A325676 and ranked by A333223.
The n-th composition has A333257(n) distinct subsequence-sums.
The n-th composition has A334299(n) distinct subsequences.
Minimal patterns avoided by a standard composition are counted by A335465.
Cf. A034691, A056986, A106356, A108917, A124770, A269134, A329744, A333224, A335458.

mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];
Table[Sum[Length[Union[mstype/@Subsets[y]]],{y,Join@@Permutations/@IntegerPartitions[n]}],{n,0,8}]

a(14)-a(16) from Jinyuan Wang, Jun 26 2020

a(17) from John Tyler Rascoe, Mar 14 2025

A060223 Number of orbits of length n under the map whose periodic points are counted by A000670.

Original entry on oeis.org

1, 1, 1, 4, 18, 108, 778, 6756, 68220, 787472, 10224702, 147512052, 2340963570, 40527565260, 760095923082, 15352212731820, 332228417589720, 7668868648772700, 188085259069430744, 4884294069438337428, 133884389812214097774, 3863086904690670182596

Offset: 0

Thomas Ward, Mar 21 2001

From Gus Wiseman, Oct 14 2016: (Start)
A finite sequence is normal if it spans an initial interval of positive integers. The *-product of two or more finite sequences is defined to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, (2 2 1) * (2 1 3) = (2 1 2 2 1 3). If Q is the set of compositions (finite sequences of positive integers) then (Q,*) is an Abelian group freely generated by a set P of prime sequences. The number of normal prime sequences of length n is equal to a(n). See example 2 and Mathematica program 2.
If N is the species (endofunctor over the category of finite sets and permutations) of unlabeled necklaces and N(S) represents the set of all non-isomorphic primitive necklaces of length n=|S|, then the numbers |N(S)| are equal to the numbers a(|S|) for any finite set S. This is because the number of orderless *-factorizations (see A034691 and A269134) of any finite sequence q is equal to the number of multiset partitions (see A007716 and A255906) of the multiset of prime factors of q. (End)

			a(5) = 108 since A000670(5) is 541 and A000670(1) is 1, so there must be (541-1)/5 = 108 orbits of length 5.
From _Gus Wiseman_, Oct 14 2016: (Start)
The a(4) = 18 normal prime sequences are the columns:
[2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4]
[1 2 2 1 1 1 2 2 2 2 3 3 1 1 2 2 3 3]
[1 1 2 1 2 2 1 1 2 3 1 2 2 3 1 3 1 2]
[1 1 1 2 1 2 1 2 1 1 2 1 3 2 3 1 2 1].
The symmetric function A(x_1,x_2,x_3,...) expanded in terms of monomial symmetric functions m(y) (indexed by integer partitions y) is equal to:
A = m(1) +
    m(11) +
    (2*m(21) + 2*m(111) +
    (m(22) + 2*m(31) + 9*m(211) + 6*m(1111)) +
    (4*m(32) + 2*m(41) + 18*m(221) + 12*m(311) + 48*m(2111) + 24*m(11111)) +
    (3*m(33) + 4*m(42) + 2*m(51) + 14*m(222) + 60*m(321) + 15*m(411) + 180*m(2211) + 80*m(3111) + 300*m(21111) + 120*m(111111)) + ... (End)

Alois P. Heinz, Table of n, a(n) for n = 0..200
Yash Puri and Thomas Ward, A dynamical property unique to the Lucas sequence, Fibonacci Quarterly, Volume 39, Number 5 (November 2001), pp. 398-402.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
T. Ward, Exactly realizable sequences

Cf. A000670, A034691 (multisets of compositions), A269134, A007716, A277427, A215474, A255906.

Row sums of A254040.

a[n_] := DivisorSum[n, MoebiusMu[#] HurwitzLerchPhi[1/2, -n/#, 0]/2 &] / n; a[0] = 1; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 30 2016 *)
thufbin[{},b_List]:=b;thufbin[a_List,{}]:=a;thufbin[a_List]:=a;
thufbin[{x_,a___},{y_,b___}]:=Switch[Ordering[If[x=!=y,{x,y},{thufbin[{a},{x,b}],thufbin[{x,a},{b}]}]],{1,2},Prepend[thufbin[{a},{y,b}],x],{2,1},Prepend[thufbin[{x,a},{b}],y]];
thufbin[a_List,b_List,c__List]:=thufbin[a,thufbin[b,c]];
priseqs[n_]:=Fold[Select,Tuples[Range[n],n],{Union[#]===Range[First[#]]&,Function[q,Select[Table[List[Take[q,{1,j}],Take[q,{j+1,n}]],{j,1,n-1}],thufbin@@Sort[#]===q&,1]==={}]}];
Table[Length[priseqs[n]],{n,1,7}] (* Gus Wiseman, Oct 14 2016 *)

\\ here b(n) is A000670
b(n)={polcoeff(serlaplace(1/(2-exp(x+O(x*x^n)))), n)}
a(n)={if(n<1, n==0, sumdiv(n, d, moebius(d)*b(n/d))/n)} \\ Andrew Howroyd, Dec 12 2017

a(n) = (1/n)* Sum_{d|n} mu(d)*A000670(n/d) for n > 0, where mu is A008683, the Moebius function. - Edited by Michel Marcus, Mar 30 2016
Let A = Sum_{q in P} Prod_i x_{q_i} = Sum_y c_y m(y) be the symmetric function whose coefficient of m(y) is equal to the number of permutations of the normal multiset [k]^y that belong to P, where the multiplicity of i in [k]^y is defined to be y_i. Then a(n) is the sum of c_y taken over all integer partitions of n. See example 3. - Gus Wiseman, Oct 14 2016
a(n) = Sum_{d|n} mu(d) * A019536(n/d) for n >= 1. - Petros Hadjicostas, Aug 19 2019

More terms from Alois P. Heinz, Jan 23 2015

A275692 Numbers k such that every rotation of the binary digits of k is less than k.

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 12, 14, 16, 20, 24, 26, 28, 30, 32, 40, 48, 50, 52, 56, 58, 60, 62, 64, 72, 80, 84, 96, 98, 100, 104, 106, 108, 112, 114, 116, 118, 120, 122, 124, 126, 128, 144, 160, 164, 168, 192, 194, 196, 200, 202, 208, 210, 212, 216, 218, 224, 226, 228

Offset: 1

Robert Israel, Aug 05 2016

nonn

0, and terms of A065609 that are not in A121016.
Number of terms with d binary digits is A001037(d).
Take the binary representation of a(n), reverse it, add 1 to each digit.  The result is the decimal representation of A102659(n).
From Gus Wiseman, Apr 19 2020: (Start)
Also numbers k such that the k-th composition in standard order (row k of A066099) is a Lyndon word. For example, the sequence of all Lyndon words begins:
()            52: (1,2,3)        118: (1,1,2,1,2)
(1)           56: (1,1,4)        120: (1,1,1,4)
(2)           58: (1,1,2,2)      122: (1,1,1,2,2)
(3)           60: (1,1,1,3)      124: (1,1,1,1,3)
(1,2)         62: (1,1,1,1,2)    126: (1,1,1,1,1,2)
(4)           64: (7)            128: (8)
(1,3)         72: (3,4)          144: (3,5)
(1,1,2)       80: (2,5)          160: (2,6)
(5)           84: (2,2,3)        164: (2,3,3)
(2,3)         96: (1,6)          168: (2,2,4)
(1,4)         98: (1,4,2)        192: (1,7)
(1,2,2)      100: (1,3,3)        194: (1,5,2)
(1,1,3)      104: (1,2,4)        196: (1,4,3)
(1,1,1,2)    106: (1,2,2,2)      200: (1,3,4)
(6)          108: (1,2,1,3)      202: (1,3,2,2)
(2,4)        112: (1,1,5)        208: (1,2,5)
(1,5)        114: (1,1,3,2)      210: (1,2,3,2)
(1,3,2)      116: (1,1,2,3)      212: (1,2,2,3)
(End)

			6 is in the sequence because its binary representation 110 is greater than all the rotations 011 and 101.
10 is not in the sequence because its binary representation 1010 is unchanged under rotation by 2 places.
From _Gus Wiseman_, Oct 31 2019: (Start)
The sequence of terms together with their binary expansions and binary indices begins:
    1:       1 ~ {1}
    2:      10 ~ {2}
    4:     100 ~ {3}
    6:     110 ~ {2,3}
    8:    1000 ~ {4}
   12:    1100 ~ {3,4}
   14:    1110 ~ {2,3,4}
   16:   10000 ~ {5}
   20:   10100 ~ {3,5}
   24:   11000 ~ {4,5}
   26:   11010 ~ {2,4,5}
   28:   11100 ~ {3,4,5}
   30:   11110 ~ {2,3,4,5}
   32:  100000 ~ {6}
   40:  101000 ~ {4,6}
   48:  110000 ~ {5,6}
   50:  110010 ~ {2,5,6}
   52:  110100 ~ {3,5,6}
   56:  111000 ~ {4,5,6}
   58:  111010 ~ {2,4,5,6}
(End)

Robert Israel, Table of n, a(n) for n = 1..9868

A similar concept is A328596.
Numbers whose binary expansion is aperiodic are A328594.
Numbers whose reversed binary expansion is a necklace are A328595.
Binary necklaces are A000031.
Binary Lyndon words are A001037.
Lyndon compositions are A059966.
Length of Lyndon factorization of binary expansion is A211100.
Length of co-Lyndon factorization of binary expansion is A329312.
Length of Lyndon factorization of reversed binary expansion is A329313.
Length of co-Lyndon factorization of reversed binary expansion is A329326.
Cf. A000031, A000740, A008965, A027375, A102659, A121016.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Rotational symmetries are counted by A138904.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon compositions are A275692 (this sequence).
- Co-Lyndon compositions are A326774.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Co-Lyndon factorizations are counted by A333765.
- Lyndon factorizations are counted by A333940.
- Reversed necklaces are A333943.
Cf. A034691, A060223, A124767, A269134, A292884.

filter:= proc(n) local L, k;
  L:= convert(convert(n,binary),string);
  for k from 1 to length(L)-1 do
    if lexorder(L,StringTools:-Rotate(L,k)) then return false fi;
  od;
  true
end proc:
select(filter, [$0..1000]);

filterQ[n_] := Module[{bits, rr}, bits = IntegerDigits[n, 2]; rr = NestList[RotateRight, bits, Length[bits]-1] // Rest; AllTrue[rr, FromDigits[#, 2] < n&]];
Select[Range[0, 1000], filterQ] (* Jean-François Alcover, Apr 29 2019 *)

def ok(n):
    b = bin(n)[2:]
    return all(b[i:] + b[:i] < b for i in range(1, len(b)))
print([k for k in range(230) if ok(k)]) # Michael S. Branicky, May 26 2022

A318284 Number of multiset partitions of a multiset whose multiplicities are the prime indices of n.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 5, 5, 9, 7, 7, 11, 11, 12, 16, 15, 15, 26, 22, 21, 29, 19, 30, 36, 31, 30, 66, 38, 42, 52, 56, 52, 47, 45, 57, 92, 77, 67, 77, 74, 101, 98, 135, 64, 137, 97, 176, 135, 109, 109, 118, 105, 231, 249, 97, 141, 181, 139, 297, 198, 385, 195, 269

Offset: 1

Gus Wiseman, Aug 23 2018

nonn

			The a(12) = 11 multiset partitions of {1,1,2,3}:
  {{1,1,2,3}}
  {{1},{1,2,3}}
  {{2},{1,1,3}}
  {{3},{1,1,2}}
  {{1,1},{2,3}}
  {{1,2},{1,3}}
  {{1},{1},{2,3}}
  {{1},{2},{1,3}}
  {{1},{3},{1,2}}
  {{2},{3},{1,1}}
  {{1},{1},{2},{3}}

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

Cf. A001055, A001970, A007716, A181821, A219727, A255906, A269134, A305936.

Cf. A317532, A318283, A318285, A318286, A318360, A318361.

nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[facs[Times@@Prime/@nrmptn[n]]],{n,60}]

permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
sig(n)={my(f=factor(n)); concat(vector(#f~, i, vector(f[i,2], j, primepi(f[i,1]))))}
count(sig)={my(n=vecsum(sig), A=O(x*x^vecmax(sig)), s=0); forpart(p=n, my(q=1/prod(i=1, #p, 1 - x^p[i] + A)); s+=prod(i=1, #sig, polcoef(q,sig[i]))*permcount(p)); s/n!}
a(n)={if(n==1, 1, my(s=sig(n)); if(#s==1, numbpart(s[1]), count(sig(n))))} \\ Andrew Howroyd, Dec 10 2018

a(n) = A001055(A181821(n)).

a(prime(n)^k) = A219727(n,k). - Andrew Howroyd, Dec 10 2018

A335465 Number of minimal normal patterns avoided by the n-th composition in standard order (A066099).

Original entry on oeis.org

1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 3, 12, 4, 3, 3, 3, 3, 4, 3, 4, 12, 4, 3, 12, 4, 12, 4, 12, 4, 3, 3, 3, 3, 4, 3, 3, 6, 4, 3, 6, 3, 3, 6, 10, 10, 4, 3, 12, 6, 12, 3, 10, 10, 12, 4, 12, 3, 12, 4, 12, 4, 3, 3, 3, 3, 4, 3, 3, 6

Offset: 0

Gus Wiseman, Jun 20 2020

These patterns comprise the basis of the class of patterns generated by this composition.
We define a (normal) pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).
The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The bases of classes generated by (), (1), (2,1,1), (3,1,2), (2,1,2,1), and (1,2,1), corresponding to n = 0, 1, 11, 38, 45, 13, are the respective columns below.
  (1)  (1,1)  (1,2)    (1,1)    (1,1,1)    (1,1,1)
       (1,2)  (1,1,1)  (1,2,3)  (1,1,2)    (1,1,2)
       (2,1)  (2,2,1)  (1,3,2)  (1,2,2)    (1,2,2)
              (3,2,1)  (2,1,3)  (1,2,3)    (1,2,3)
                       (2,3,1)  (1,3,2)    (1,3,2)
                       (3,2,1)  (2,1,3)    (2,1,1)
                                (2,3,1)    (2,1,2)
                                (3,1,2)    (2,1,3)
                                (3,2,1)    (2,2,1)
                                (2,2,1,1)  (2,3,1)
                                           (3,1,2)
                                           (3,2,1)

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.
Gus Wiseman, Statistics, classes, and transformations of standard compositions

Patterns matched by standard compositions are counted by A335454.
Patterns matched by compositions of n are counted by A335456(n).
The version for Heinz numbers of partitions is A335550.
Patterns are counted by A000670 and ranked by A333217.
Knapsack compositions are counted by A325676 and ranked by A333223.
The n-th composition has A334299(n) distinct subsequences.
Cf. A056986, A124767, A124770, A124771, A269134, A333218, A333257, A335549.

A261982 Number of compositions of n with some part repeated.

Original entry on oeis.org

0, 0, 1, 1, 5, 11, 21, 51, 109, 229, 455, 959, 1947, 3963, 7999, 16033, 32333, 64919, 130221, 260967, 522733, 1045825, 2093855, 4189547, 8382315, 16768455, 33543127, 67093261, 134193413, 268404995, 536829045, 1073686083, 2147408773, 4294869253, 8589803783

Offset: 0

Alois P. Heinz, Sep 07 2015

nonn

Also compositions matching the pattern (1,1). - Gus Wiseman, Jun 23 2020

			a(2) = 1: 11.
a(3) = 1: 111.
a(4) = 5: 22, 211, 121, 112, 1111.

Alois P. Heinz, Table of n, a(n) for n = 0..3322
Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Row sums of A261981 and of A262191.
Cf. A262047.
The version for patterns is A019472.
The (1,1)-avoiding version is A032020.
The case of partitions is A047967.
(1,1,1)-matching compositions are counted by A335455.
Patterns matched by compositions are counted by A335456.
(1,1)-matching compositions are ranked by A335488.
Cf. A011782, A056986, A106356, A181796, A238279, A269134, A333755.

b:= proc(n, k) option remember; `if`(k<0 or n<0, 0,
      `if`(k=0, `if`(n=0, 1, 0), b(n-k, k) +k*b(n-k, k-1)))
    end:
a:= n-> ceil(2^(n-1))-add(b(n, k), k=0..floor((sqrt(8*n+1)-1)/2)):
seq(a(n), n=0..40);

b[n_, k_] := b[n, k] = If[k<0 || n<0, 0, If[k==0, If[n==0, 1, 0], b[n-k, k] + k*b[n-k, k-1]]]; a[n_] := Ceiling[2^(n-1)]-Sum[b[n, k], {k, 0, Floor[ (Sqrt[8n+1]-1)/2]}]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 08 2017, translated from Maple *)
Table[Length[Join@@Permutations/@Select[IntegerPartitions[n],Length[#]>Length[Split[#]]&]],{n,0,10}] (* Gus Wiseman, Jun 24 2020 *)

a(n) = A011782(n) - A032020(n).

G.f.: (1 - x) / (1 - 2*x) - Sum_{k>=0} k! * x^(k*(k + 1)/2) / Product_{j=1..k} (1 - x^j). - Ilya Gutkovskiy, Jan 30 2020

A335454 Number of normal patterns matched by the n-th composition in standard order (A066099).

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 5, 3, 6, 5, 5, 2, 3, 3, 5, 3, 5, 6, 7, 3, 6, 5, 9, 5, 9, 7, 6, 2, 3, 3, 5, 3, 4, 5, 7, 3, 5, 4, 7, 5, 10, 9, 9, 3, 6, 5, 9, 4, 9, 10, 12, 5, 9, 7, 13, 7, 12, 9, 7, 2, 3, 3, 5, 3, 4, 5, 7, 3, 5, 5, 7, 6, 10, 9, 9, 3, 5, 6, 8, 5

Offset: 0

Gus Wiseman, Jun 14 2020

We define a (normal) pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The a(n) patterns for n = 0, 1, 3, 7, 11, 13, 23, 83, 27, 45:
  0:  1:   11:   111:   211:   121:   2111:   2311:   1211:   2121:
---------------------------------------------------------------------
  ()  ()   ()    ()     ()     ()     ()      ()      ()      ()
      (1)  (1)   (1)    (1)    (1)    (1)     (1)     (1)     (1)
           (11)  (11)   (11)   (11)   (11)    (11)    (11)    (11)
                 (111)  (21)   (12)   (21)    (12)    (12)    (12)
                        (211)  (21)   (111)   (21)    (21)    (21)
                               (121)  (211)   (211)   (111)   (121)
                                      (2111)  (231)   (121)   (211)
                                              (2311)  (211)   (212)
                                                      (1211)  (221)
                                                              (2121)

John Tyler Rascoe, Table of n, a(n) for n = 0..8192
Wikipedia, Permutation pattern
Gus Wiseman, Statistics, classes, and transformations of standard compositions
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

References found in the links are not all included here.
Summing over indices with binary length n gives A335456(n).
The contiguous case is A335458.
The version for Heinz numbers of partitions is A335549.
Patterns are counted by A000670 and ranked by A333217.
The n-th composition has A124771(n) distinct consecutive subsequences.
Knapsack compositions are counted by A325676 and ranked by A333223.
The n-th composition has A333257(n) distinct subsequence-sums.
The n-th composition has A334299(n) distinct subsequences.
Minimal avoided patterns are counted by A335465.
Cf. A034691, A056986, A108917, A124767, A124770, A158005, A269134, A333218, A333222, A333224, A334030.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];
Table[Length[Union[mstype/@Subsets[stc[n]]]],{n,0,30}]

from itertools import combinations
def comp(n):
    # see A357625
    return
def A335465(n):
    A,B,C = set(),set(),comp(n)
    c = range(len(C))
    for j in c:
        for k in combinations(c, j):
            A.add(tuple(C[i] for i in k))
    for i in A:
        D = {v: rank + 1 for rank, v in enumerate(sorted(set(i)))}
        B.add(tuple(D[v] for v in i))
    return len(B)+1 # John Tyler Rascoe, Mar 12 2025

cp's OEIS Frontend

A059966 a(n) = (1/n) * Sum_{ d divides n } mu(n/d) * (2^d - 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Formula

Extensions

A281113 Number of twice-factorizations of n. Number of ways to choose a postpositive factorization of each part of a postpositive factorization of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A102726 Number of compositions of the integer n into positive parts that avoid a fixed pattern of three letters.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A335456 Number of normal patterns matched by compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A060223 Number of orbits of length n under the map whose periodic points are counted by A000670.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A275692 Numbers k such that every rotation of the binary digits of k is less than k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

A318284 Number of multiset partitions of a multiset whose multiplicities are the prime indices of n.

Views

Author

Keywords