A008965 -id:A008965 - cp's OEIS frontend

A097805 Number of compositions of n with k parts, T(n, k) = binomial(n-1, k-1) for n, k >= 1 and T(n, 0) = 0^n, triangle read by rows for n >= 0 and 0 <= k <= n.

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 4, 6, 4, 1, 0, 1, 5, 10, 10, 5, 1, 0, 1, 6, 15, 20, 15, 6, 1, 0, 1, 7, 21, 35, 35, 21, 7, 1, 0, 1, 8, 28, 56, 70, 56, 28, 8, 1, 0, 1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 0, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 0, 1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1

Offset: 0

Paul Barry, Aug 25 2004

Previous name was: Riordan array (1, 1/(1-x)) read by rows.
Note this Riordan array would be denoted (1, x/(1-x)) by some authors.
Columns have g.f. (x/(1-x))^k. Reverse of A071919. Row sums are A011782. Antidiagonal sums are Fibonacci(n-1). Inverse as Riordan array is (1, 1/(1+x)). A097805=B*A059260*B^(-1), where B is the binomial matrix.
(0,1)-Pascal triangle. - Philippe Deléham, Nov 21 2006
(n+1) * each term of row n generates triangle A127952: (1; 0, 2; 0, 3, 3; 0, 4, 8, 4; ...). - Gary W. Adamson, Feb 09 2007
Triangle T(n,k), 0<=k<=n, read by rows, given by [0,1,0,0,0,0,0,...] DELTA [1,0,0,0,0,0,0,...] where DELTA is the operator defined in A084938. - Philippe Deléham, Dec 12 2008
From Paul Weisenhorn, Feb 09 2011: (Start)
Triangle read by rows: T(r,c) is the number of unordered partitions of n=r*(r+1)/2+c into (r+1) parts < (r+1) and at most pairs of equal parts and parts in neighboring pairs have difference 2.
Triangle read by rows: T(r,c) is the number of unordered partitions of the number n=r*(r+1)/2+(c-1) into r parts < (r+1) and at most pairs of equal parts and parts in neighboring pairs have difference 2. (End)
Triangle read by rows: T(r,c) is the number of ordered partitions (compositions) of r into c parts. - Juergen Will, Jan 04 2016
From Tom Copeland, Oct 25 2012: (Start)
Given a basis composed of a sequence of polynomials p_n(x) characterized by ladder (creation / annihilation, or raising / lowering) operators defined by R p_n(x) = p_(n+1)(x) and L p_n(x) = n p_(n-1)(x) with p_0(x)=1, giving the number operator # p_n(x) = RL p_n(x) = n p_n(x), the lower triangular padded Pascal matrix Pd (A097805) serves as a matrix representation of the operator exp(R^2*L) = exp(R#) =
  1) exp(x^2D) for the set x^n  and
  2) D^(-1) exp(t*x)D for the set x^n/n! (see A218234).
  (End)
From James East, Apr 11 2014: (Start)
Square array a(m,n) with m,n=0,1,2,... read by off-diagonals.
a(m,n) gives the number of order-preserving functions f:{1,...,m}->{1,...,n}. Order-preserving means that xa(n,n)=A088218(n) is the size of the semigroup O_n of all order-preserving transformations of {1,...,n}.
Read as a triangle, this sequence may be obtained by augmenting Pascal's triangle by appending the column 1,0,0,0,... on the left.
(End)
A formula based on the partitions of n with largest part k is given as a Sage program below. The 'conjugate' formula leads to A048004. - Peter Luschny, Jul 13 2015
From Wolfdieter Lang, Feb 17 2017: (Start)
The transposed of this lower triangular Riordan matrix of the associated type T provides the transition matrix between the monomial basis {x^n}, n >= 0, and the basis {y^n}, n >= 0, with y = x/(1-x): x^0 = 1 = y^0, x^n = Sum_{m >= n} Ttrans(n,m) y^m, for n >= 1, with Ttrans(n,m) = binomial(m-1,n-1).
Therefore, if a transformation with this Riordan matrix from a sequence {a} to the sequence {b} is given by b(n) = Sum_{m=0..n} T(n, m)*a(m), with T(n, m) = binomial(n-1, m-1), for n >= 1, then Sum_{n >= 0} a(n)*x^n = Sum_{n >= 0} b(n)*y^n, with y = x/(1-x) and vice versa. This is a modified binomial transformation; the usual one belongs to the Pascal Riordan matrix A007318. (End)
From Gus Wiseman, Jan 23 2022: (Start)
Also the number of compositions of n with alternating sum k, with k ranging from -n to n in steps of 2. For example, row n = 6 counts the following compositions (empty column indicated by dot):
  .  (15)  (24)    (33)      (42)     (51)   (6)
           (141)   (132)     (123)    (114)
           (1113)  (231)     (222)    (213)
           (1212)  (1122)    (321)    (312)
           (1311)  (1221)    (1131)   (411)
                   (2112)    (2121)
                   (2211)    (3111)
                   (11121)   (11112)
                   (12111)   (11211)
                   (111111)  (21111)
The reverse-alternating version is the same. Counting compositions by all three parameters (sum, length, alternating sum) gives A345197. Compositions of 2n with alternating sum 2k with k ranging from -n + 1 to n are A034871. (End)
Also the convolution triangle of A000012. - Peter Luschny, Oct 07 2022
From Sergey Kitaev, Nov 18 2023: (Start)
Number of permutations of length n avoiding simultaneously the patterns 123 and 132 with k right-to-left maxima. A right-to-left maximum in a permutation a(1)a(2)...a(n) is position i such that a(j) < a(i) for all i < j.
Number of permutations of length n avoiding simultaneously the patterns 231 and 312 with k right-to-left minima (resp., left-to-right maxima). A right-to-left minimum (resp., left-to-right maximum) in a permutation a(1)a(2)...a(n) is position i such that a(j) > a(i) for all j > i (resp., a(j) < a(i) for all j < i).
Number of permutations of length n avoiding simultaneously the patterns 213 and 312 with k right-to-left maxima (resp., left-to-right maxima).
Number of permutations of length n avoiding simultaneously the patterns 213 and 231 with k right-to-left maxima (resp., right-to-left minima). (End)

			G.f. = 1 + x * (x + x^3 * (1 + x) + x^6 * (1 + x)^2 + x^10 * (1 + x)^3 + ...). - _Michael Somos_, Aug 20 2006
The triangle T(n, k) begins:
n\k  0 1 2  3  4   5   6  7  8 9 10 ...
0:   1
1:   0 1
2:   0 1 1
3:   0 1 2  1
4:   0 1 3  3  1
5:   0 1 4  6  4   1
6:   0 1 5 10 10   5   1
7:   0 1 6 15 20  15   6  1
8:   0 1 7 21 35  35  21  7  1
9:   0 1 8 28 56  70  56 28  8 1
10:  0 1 9 36 84 126 126 84 36 9  1
... reformatted _Wolfdieter Lang_, Jul 31 2017
From _Paul Weisenhorn_, Feb 09 2011: (Start)
T(r=5,c=3) = binomial(4,2) = 6 unordered partitions of the number n = r*(r+1)/2+c = 18 with (r+1)=6 summands: (5+5+4+2+1+1), (5+5+3+3+1+1), (5+4+4+3+1+1), (5+5+3+2+2+1), (5+4+4+2+2+1), (5+4+3+3+2+1).
T(r=5,c=3) = binomial(4,2) = 6 unordered partitions of the number n = r*(r+1)/2+(c-1) = 17 with r=5 summands: (5+5+4+2+1), (5+5+3+3+1), (5+5+3+2+2), (5+4+4+3+1), (5+4+4+2+2), (5+4+3+3+2).  (End)
From _James East_, Apr 11 2014: (Start)
a(0,0)=1 since there is a unique (order-preserving) function {}->{}.
a(m,0)=0 for m>0 since there is no function from a nonempty set to the empty set.
a(3,2)=4 because there are four order-preserving functions {1,2,3}->{1,2}: these are [1,1,1], [2,2,2], [1,1,2], [1,2,2]. Here f=[a,b,c] denotes the function defined by f(1)=a, f(2)=b, f(3)=c.
a(2,3)=6 because there are six order-preserving functions {1,2}->{1,2,3}: these are [1,1], [1,2], [1,3], [2,2], [2,3], [3,3].
(End)

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Part 1, Section 7.2.1.3, 2011.

Alois P. Heinz, Rows n = 0..140, flattened
Tom Copeland, Infinitesimal Generators, the Pascal Pyramid, and the Witt and Virasoro Algebras
James East and Peter J. McNamara, On the work performed by a transformation semigroup, Australas. J. Combin. 49 (2011), 95-109.
Tian Han and Sergey Kitaev, Joint distributions of statistics over permutations avoiding two patterns of length 3, arXiv:2311.02974 [math.CO], 2023.
Wolfdieter Lang, On Generating functions of Diagonals Sequences of Sheffer and Riordan Number Triangles, arXiv:1708.01421 [math.NT], August 2017.
Huyile Liang, Yanni Pei, and Yi Wang, Analytic combinatorics of coordination numbers of cubic lattices, arXiv:2302.11856 [math.CO], 2023. See p. 8.
P. A. MacMahon, Memoir on the Theory of the Compositions of Numbers, Phil. Trans. Royal Soc. London A, 184 (1893), 835-901. - _Juergen Will_, Jan 02 2016
Franck Ramaharo, A generating polynomial for the pretzel knot, arXiv:1805.10680 [math.CO], 2018.

Case m=0 of the polynomials defined in A278073.
Cf. A000012 (diagonal), A011782 (row sums), A088218 (central terms).
Cf. A007318, A048004, A127952, A118800, A200139, A130595, A167374.
The terms just left of center in odd-indexed rows are A001791, even A002054.
The odd-indexed rows are A034871.
Row sums without the center are A058622.
The unordered version is A072233, without zeros A008284.
Right half without center has row sums A027306(n-1).
Right half with center has row sums A116406(n).
Left half without center has row sums A294175(n-1).
Left half with center has row sums A058622(n-1).
A025047 counts alternating compositions.
A098124 counts balanced compositions, unordered A047993.
A106356 counts compositions by number of maximal anti-runs.
A344651 counts partitions by sum and alternating sum.
A345197 counts compositions by sum, length, and alternating sum.
Cf. A000346, A000984, A001700, A008549, A008965, A114121, A124754, A238279, A345907, A345908, A346632.

b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
      expand(add(b(n-i*j, i-1, p+j)/j!*x^j, j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n$2, 0)):
seq(T(n), n=0..20);  # Alois P. Heinz, May 25 2014
# Alternatively:
T := proc(k,n) option remember;
if k=n then 1 elif k=0 then 0 else
add(T(k-1,n-i), i=1..n-k+1) fi end:
A097805 := (n,k) -> T(k,n):
for n from 0 to 12 do seq(A097805(n,k), k=0..n) od; # Peter Luschny, Mar 12 2016
# Uses function PMatrix from A357368.
PMatrix(10, n -> 1);  # Peter Luschny, Oct 07 2022

T[0, 0] = 1; T[n_, k_] := Binomial[n-1, k-1]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 03 2014, after Paul Weisenhorn *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[#]==k&]],{n,0,10},{k,0,n}] (* Gus Wiseman, Jan 23 2022 *)

{a(n) = my(m); if( n<2, n==0, n--; m = (sqrtint(8*n + 1) - 1)\2; binomial(m-1, n - m*(m + 1)/2))}; /* Michael Somos, Aug 20 2006 */

T(n,k) = if (k==0, 0^n, binomial(n-1, k-1)); \\ Michel Marcus, May 06 2022

row(n) = vector(n+1, k, k--; if (k==0, 0^n, binomial(n-1, k-1))); \\ Michel Marcus, May 06 2022

from math import comb
def T(n, k): return comb(n-1, k-1) if k != 0 else k**n  # Peter Luschny, May 06 2022

# Illustrates a basic partition formula, is not efficient as a program for large n.
def A097805_row(n):
    r = []
    for k in (0..n):
        s = 0
        for q in Partitions(n, max_part=k, inner=[k]):
            s += mul(binomial(q[j],q[j+1]) for j in range(len(q)-1))
        r.append(s)
    return r
[A097805_row(n) for n in (0..9)] # Peter Luschny, Jul 13 2015

Number triangle T(n, k) defined by T(n,k) = Sum_{j=0..n} binomial(n, j)*if(k<=j, (-1)^(j-k), 0).
T(r,c) = binomial(r-1,c-1), 0 <= c <= r. - Paul Weisenhorn, Feb 09 2011
G.f.: (-1+x)/(-1+x+x*y). - R. J. Mathar, Aug 11 2015
a(0,0) = 1, a(n,k) = binomial(n-1,n-k) = binomial(n-1,k-1) Juergen Will, Jan 04 2016
G.f.: (x^1 + x^2 + x^3 + ...)^k = (x/(1-x))^k. - Juergen Will, Jan 04 2016
From Tom Copeland, Nov 15 2016: (Start)
E.g.f.: 1 + x*[e^((x+1)t)-1]/(x+1).
This padded Pascal matrix with the odd columns negated is NpdP = M*S = S^(-1)*M^(-1) = S^(-1)*M, where M(n,k) = (-1)^n A130595(n,k), the inverse Pascal matrix with the odd rows negated, S is the summation matrix A000012, the lower triangular matrix with all elements unity, and S^(-1) = A167374, a finite difference matrix. NpdP is self-inverse, i.e., (M*S)^2 = the identity matrix, and has the e.g.f. 1 - x*[e^((1-x)t)-1]/(1-x).
M = NpdP*S^(-1) follows from the well-known recursion property of the Pascal matrix, implying NpdP = M*S.
The self-inverse property of -NpdP is implied by the self-inverse relation of its embedded signed Pascal submatrix M (cf. A130595). Also see A118800 for another proof.
Let P^(-1) be A130595, the inverse Pascal matrix. Then T = A200139*P^(-1) and T^(-1) = padded P^(-1) = P*A097808*P^(-1). (End)
The center (n>0) is T(2n+1,n+1) = A000984(n) = 2*A001700(n-1) = 2*A088218(n) = A126869(2n) = 2*A138364(2n-1). - Gus Wiseman, Jan 25 2022

Corrected by Philippe Deléham, Oct 05 2005

New name using classical terminology by Peter Luschny, Feb 05 2019

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

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

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

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

S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, pp. 120, 172.
May, Robert M. "Simple mathematical models with very complicated dynamics." Nature, Vol. 261, June 10, 1976, pp. 459-467; reprinted in The Theory of Chaotic Attractors, pp. 85-93. Springer, New York, NY, 2004. The sequences listed in Table 2 are A000079, A027375, A000031, A001037, A000048, A051841. - N. J. A. Sloane, Mar 17 2019
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.112(a).

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

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

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

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

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

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

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

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

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

A025047 Number of alternating compositions, i.e., compositions with alternating increases and decreases, starting with either an increase or a decrease.

Original entry on oeis.org

1, 1, 1, 3, 4, 7, 12, 19, 29, 48, 75, 118, 186, 293, 460, 725, 1139, 1789, 2814, 4422, 6949, 10924, 17168, 26979, 42404, 66644, 104737, 164610, 258707, 406588, 639009, 1004287, 1578363, 2480606, 3898599, 6127152, 9629623, 15134213, 23785388, 37381849, 58750468

Offset: 0

David W. Wilson

nonn

Original name: Wiggly sums: number of sums adding to n in which terms alternately increase and decrease or vice versa.

			From _Joerg Arndt_, Dec 28 2012: (Start)
There are a(7)=19 such compositions of 7:
[ 1] +  [ 1 2 1 2 1 ]
[ 2] +  [ 1 2 1 3 ]
[ 3] +  [ 1 3 1 2 ]
[ 4] +  [ 1 4 2 ]
[ 5] +  [ 1 5 1 ]
[ 6] +  [ 1 6 ]
[ 7] -  [ 2 1 3 1 ]
[ 8] -  [ 2 1 4 ]
[ 9] +  [ 2 3 2 ]
[10] +  [ 2 4 1 ]
[11] +  [ 2 5 ]
[12] -  [ 3 1 2 1 ]
[13] -  [ 3 1 3 ]
[14] +  [ 3 4 ]
[15] -  [ 4 1 2 ]
[16] -  [ 4 3 ]
[17] -  [ 5 2 ]
[18] -  [ 6 1 ]
[19] 0  [ 7 ]
For A025048(7)-1=10 of these the first two parts are increasing (marked by '+'),
and for A025049(7)-1=8 the first two parts are decreasing (marked by '-').
The composition into one part is counted by both A025048 and A025049.
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..3333
Edward A. Bender and E. Rodney Canfield, Locally Restricted Compositions III. Adjacent-Part Periodic Inequalities, Electronic Journal of Combinatorics 17 (2010), #R145.

Dominated by A003242 (anti-run compositions), complement A261983.
The ascending case is A025048.
The descending case is A025049.
The version allowing pairs (x,x) is A344604.
These compositions are ranked by A345167, permutations A349051.
The complement is counted by A345192, ranked by A345168.
The version for patterns is A345194 (with twins: A344605).
A001250 counts alternating permutations, complement A348615.
A011782 counts compositions.
A032020 counts strict compositions.
A106356 counts compositions by number of maximal anti-runs.
A114901 counts compositions where each part is adjacent to an equal part.
A274174 counts compositions with equal parts contiguous.
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
A345164 counts alternating permutations of prime indices.
A345165 counts partitions w/o alternating permutation, ranked by A345171.
A345170 counts partitions w/ alternating permutation, ranked by A345172.
Cf. A000070, A008965, A238279, A333755, A344606, A344614, A344653, A344740, A345163, A345166, A345169.

b:= proc(n, l, t) option remember; `if`(n=0, 1, add(
      b(n-j, j, 1-t), j=`if`(t=1, 1..min(l-1, n), l+1..n)))
    end:
a:= n-> 1+add(add(b(n-j, j, i), i=0..1), j=1..n-1):
seq(a(n), n=0..40);  # Alois P. Heinz, Jan 31 2024

wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],wigQ]],{n,0,15}] (* Gus Wiseman, Jun 17 2021 *)

D(n,f)={my(M=matrix(n,n,j,k,k>=j), s=M[,n]); for(b=1, n, f=!f; M=matrix(n,n,j,k,if(k1, M[j-k,k-1]), M[j-k,n]-M[j-k,k] ))); for(k=2, n, M[,k]+=M[,k-1]); s+=M[,n]); s~}
seq(n) = concat([1], D(n,0) + D(n,1) - vector(n,j,1)) \\ Andrew Howroyd, Jan 31 2024

a(n) = A025048(n) + A025049(n) - 1 = sum_k[A059881(n, k)] = sum_k[S(n, k) + T(n, k)] - 1 where if n>k>0 S(n, k) = sum_j[T(n - k, j)] over j>k and T(n, k) = sum_j[S(n - k, j)] over k>j (note reversal) and if n>0 S(n, n) = T(n, n) = 1; S(n, k) = A059882(n, k), T(n, k) = A059883(n, k). - Henry Bottomley, Feb 05 2001
a(n) ~ c * d^n, where d = 1.571630806607064114100138865739690782401305155950789062725..., c = 0.82222360450823867604750473815253345888526601460811483897... . - Vaclav Kotesovec, Sep 12 2014
a(n) = A344604(n) + 1 - n mod 2. - Gus Wiseman, Jun 17 2021

Better name using a comment of Franklin T. Adams-Watters by Peter Luschny, Oct 31 2021

A000629 Number of necklaces of partitions of n+1 labeled beads.

Original entry on oeis.org

1, 2, 6, 26, 150, 1082, 9366, 94586, 1091670, 14174522, 204495126, 3245265146, 56183135190, 1053716696762, 21282685940886, 460566381955706, 10631309363962710, 260741534058271802, 6771069326513690646, 185603174638656822266, 5355375592488768406230

Offset: 0

N. J. A. Sloane, Don Knuth, Nick Singer (nsinger(AT)eos.hitc.com)

Also the number of logically distinct strings of first order quantifiers in which n variables occur (C. S. Peirce, c. 1903). - Stephen Pollard (spollard(AT)truman.edu), Jun 07 2002
Stirling transform of A052849(n) = [2, 4, 12, 48, 240, ...] is a(n) = [2, 6, 26, 150, 1082, ...]. - Michael Somos, Mar 04 2004
Stirling transform of A000142(n-1) = [1, 1, 2, 6, 24, ...] is a(n-1) = [1, 2, 6, 26, ...]. - Michael Somos, Mar 04 2004
Stirling transform of (-1)^n * A024167(n-1) = [0, 1, -1, 5, -14, 94, ...] is a(n-2) = [0, 1, 2, 6, 26, ...]. - Michael Somos, Mar 04 2004
The asymptotic expansion of 2*log(n) - (2^1*log(1) + 2^2*log(2) + ... + 2^n*log(n))/2^n is (a(1)/1)/n + (a(2)/2)/n^2 + (a(3)/3)/n^3 + ... - Michael Somos, Aug 22 2004
This is the sequence of cumulants of the probability distribution of the number of tails before the first head in a sequence of fair coin tosses. - Michael Hardy (hardy(AT)math.umn.edu), May 01 2005
Appears to be row sums of A154921. - Mats Granvik, Jan 18 2009
This is the number of cyclically ordered partitions of n+1 labeled points. The ordered version is A000670. - Michael Somos, Jan 08 2011
A000670(n+1) = p(n+1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - Michael Somos, Apr 27 2012
Row sums of A154921 as conjectured above by Granvik. a(n) gives the number of outcomes of a race between n horses H1,...,Hn, where if a horse falls it is not ranked. For example, when n = 2 the 6 outcomes are a dead heat, H1 wins H2 second, H2 wins H1 second, H1 wins H2 falls, H2 wins H1 falls or both fall. - Peter Bala, May 15 2012
Also the number of disjoint areas of a Venn diagram for n multisets. - Aurelian Radoaca, Jun 27 2016
Also the number of ways of ordering n nonnegative integers, allowing for the possibility of ties, and also comparing the smallest integers with 0. Each comparison with 0 gives two possibilities, x > 0 or x=0. As such, without comparison with 0, we get A000670, the number of ways of ordering n nonnegative integers, allowing for the possibility of ties, or the number of ways n competitors can rank in a competition, allowing for the possibility of ties. For instance, for 2 nonnegative integers x,y, there are the following 6 ways of ordering them: x = y = 0, x = y > 0, x > y = 0, x > y > 0, y > x = 0, y > x > 0. - Aurelian Radoaca, Jul 09 2016
Also the number of ordered set partitions of subsets of {1,...,n}. Also the number of chains of distinct nonempty subsets of {1,...,n}. - Gus Wiseman, Feb 01 2019
Number of combinations of a Simplex lock having n buttons.
Row sums of the unsigned cumulant expansion polynomials A127671 and logarithmic polynomials A263634. - Tom Copeland, Jun 04 2021
Also the number of vertices in the axis-aligned polytope consisting of all vectors x in R^n where, for all k in {1,...,n}, the k-th smallest coordinate of x lies in the interval [0, k]. - Adam P. Goucher, Jan 18 2023
Number of idempotent Boolean relation matrices whose complement is also idempotent.  See Rosenblatt link. - Geoffrey Critzer, Feb 26 2023

			a(2)=6: the necklace representatives on 1,2,3 are ({123}), ({12},{3}), ({13},{2}), ({23},{1}), ({1},{2},{3}), ({1},{3},{2})
G.f. = 1 + 2*x + 6*x^2 + 26*x^3 + 150*x^4 + 1082*x^5 + 9366*x^6 + 94586*x^7 + ...
From _Gus Wiseman_, Feb 01 2019: (Start)
The a(3) = 26 ordered set partitions of subsets of {1,2,3} are:
  {}  {{1}}  {{2}}  {{3}}  {{12}}    {{13}}    {{23}}    {{123}}
                           {{1}{2}}  {{1}{3}}  {{2}{3}}  {{1}{23}}
                           {{2}{1}}  {{3}{1}}  {{3}{2}}  {{12}{3}}
                                                         {{13}{2}}
                                                         {{2}{13}}
                                                         {{23}{1}}
                                                         {{3}{12}}
                                                         {{1}{2}{3}}
                                                         {{1}{3}{2}}
                                                         {{2}{1}{3}}
                                                         {{2}{3}{1}}
                                                         {{3}{1}{2}}
                                                         {{3}{2}{1}}
(End)

R. Austin, R. K. Guy, and R. Nowakowski, unpublished notes, circa 1987.
N. G. de Bruijn, Asymptotic Methods in Analysis, Dover, 1981, p. 36.
Eric Hammer, The Calculations of Peirce's 4.453, Transactions of the Charles S. Peirce Society, Vol. 31 (1995), pp. 829-839.
D. E. Knuth, personal communication.
J. D. E. Konhauser et al., Which Way Did the Bicycle Go?, MAA 1996, p. 174.
Charles Sanders Peirce, Collected Papers, eds. C. Hartshorne and P. Weiss, Harvard University Press, Cambridge, Vol. 4, 1933, pp. 364-365. (CP 4.453 in the electronic edition of The Collected Papers of Charles Sanders Peirce.)
Dawidson Razafimahatolotra, Number of Preorders to Compute Probability of Conflict of an Unstable Effectivity Function, Preprint, Paris School of Economics, University of Paris I, Nov 23 2007.

Seiichi Manyama, Table of n, a(n) for n = 0..424 (terms 0..100 from T. D. Noe)
R. Austin, R. K. Guy, & R. Nowakowski, Unpublished notes, 1987
Paul Barry, Eulerian polynomials as moments, via exponential Riordan arrays (2011), arXiv preprint arXiv:1105.3043 [math.CO], 2011. J. Int. Seq. 14 (2011) # 11.9.5.
Paul Barry, Eulerian-Dowling Polynomials as Moments, Using Riordan Arrays, arXiv:1702.04007 [math.CO], 2017.
Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
Paul Barry, Series reversion with Jacobi and Thron continued fractions, arXiv:2107.14278 [math.NT], 2021.
Arthur T. Benjamin, Combinatorics and campus security, The UMAP Journal 17.2 (summer 1996), pp. 111-116.
Zhanar Berikkyzy, Pamela E. Harris, Anna Pun, Catherine Yan, and Chenchen Zhao, Combinatorial Identities for Vacillating Tableaux, arXiv:2308.14183 [math.CO], 2023. See pp. 27, 29.
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
Mircea I. Cirnu, Determinantal formulas for sum of generalized arithmetic-geometric series, Boletin de la Asociacion Matematica Venezolana, Vol. XVIII, No. 1 (2011), p. 13.
Colin Defant, Troupes, Cumulants, and Stack-Sorting, arXiv:2004.11367 [math.CO], 2020.
G. H. E. Duchamp, N. Hoang-Nghia, and A. Tanasa, A word Hopf algebra based on the selection/quotient principle, Séminaire Lotharingien de Combinatoire 68 (2013), Article B68c.
Thomas Fink, Recursively divisible numbers, arXiv:1912.07979 [math.NT], 2019.
Olivier Golinelli, Remote control system of a binary tree of switches - II. balancing for a perfect binary tree, arXiv:2405.16968 [cs.DM], 2024. See p. 17.
W. S. Gray and M. Thitsa, System Interconnections and Combinatorial Integer Sequences, in: System Theory (SSST), 2013 45th Southeastern Symposium on, Date of Conference: 11-11 Mar 2013, Digital Object Identifier: 10.1109/SSST.2013.6524939.
Robin Houston, Adam P. Goucher, and Nathaniel Johnston, A New Formula for the Determinant and Bounds on Its Tensor and Waring Ranks, arXiv:2301.06586 [math.CO], 2023.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 99
H. K. Kim, D. S. Krotov and J. Y. Lee, Matrices uniquely determined by their lonesums, Linear Algebra and its Applications, 438 (2013) no 7, 3107-3123.
Germain Kreweras, Une dualité élémentaire souvent utile dans les problèmes combinatoires, Mathématiques et Sciences Humaines 3 (1963): 31-41.
Qipeng Kuang, Václav Kůla, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations, arXiv:2508.11515 [cs.LO], 2025. See pp. 20-21.
Rajesh Kumar Mohapatra and Tzung-Pei Hong, On the Number of Finite Fuzzy Subsets with Analysis of Integer Sequences, Mathematics (2022) Vol. 10, No. 7, 1161.
Konstantin Nestmann and Carsten Timm, Time-convolutionless master equation: Perturbative expansions to arbitrary order and application to quantum dots, arXiv:1903.05132 [cond-mat.mes-hall], 2019.
Aurelian Radoaca, Properties of Multisets Compared to Sets
J. Randon-Furling and S. Redner, Residence Time Near an Absorbing Set, arXiv:1806.09028 [cond-mat.stat-mech], 2018.
D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.
John K. Sikora, On Calculating the Coefficients of a Polynomial Generated Sequence Using the Worpitzky Number Triangles, arXiv:1806.00887 [math.NT], 2018.
S. L. Snover and N. J. A. Sloane, Correspondence, 1991
J. F. Steffensen, On a class of polynomials and their application to actuarial problems, Skandinavisk Aktuarietidskrift, Vol. 11, pp. 75-97, 1928.
M. Thitsa and W. S. Gray, On the Radius of Convergence of Interconnected Analytic Nonlinear Input-Output Systems, SIAM Journal on Control and Optimization, Vol. 50, No. 5, pp. 2786-2813. - From _N. J. A. Sloane_, Dec 26 2012
Eric Weisstein's World of Mathematics, Geometric Distribution
Eric Weisstein's World of Mathematics, Stirling Number of the Second Kind
Herbert S. Wilf, The Redheffer matrix of a partially ordered set, The Electronic Journal of Combinatorics 11(2) (2004), #R10
Herbert S. Wilf, The Redheffer matrix of a partially ordered set, arXiv:math/0408263 [math.CO], 2004.

Same as A076726 except for a(0). Cf. A008965, A052861, A008277.
Binomial transform of A000670, also double of A000670. - Joe Keane (jgk(AT)jgk.org)
A002050(n) = a(n) - 1.
A000629, A000670, A002050, A052856, A076726 are all more-or-less the same sequence. - N. J. A. Sloane, Jul 04 2012
Row sums of A028246.
A diagonal of the triangular array in A241168.
Row sums of unsigned A127671 and A263634.

spec := [ B, {B=Cycle(Set(Z,card>=1))}, labeled ]; [seq(combstruct[count](spec, size=n), n=0..20)];
a:=n->add(Stirling2(n+1,k)*(k-1)!,k=1..n+1); # Mike Zabrocki, Feb 05 2005

a[ 0 ] = 1; a[ n_ ] := (a[ n ] = 1 + Sum[ Binomial[ n, k ] a[ n-k ], {k, 1, n} ])
Table[ PolyLog[n, 1/2], {n, 0, -18, -1}] (* Robert G. Wilson v, Aug 05 2010 *)
a[ n_] := If[ n<0, 0, PolyLog[ -n, 1/2]]; (* Michael Somos, Mar 07 2011 *)
Table[Sum[(-1)^(n-k) StirlingS2[n,k]k! 2^k,{k,0,n}],{n,0,20}] (* Harvey P. Dale, Oct 21 2011 *)
Join[{1}, Rest[t=30; Range[0, t]! CoefficientList[Series[2/(2 - Exp[x]), {x, 0, t}], x]]] (* Vincenzo Librandi, Jan 02 2016 *)

{a(n) = if( n<0, 0, n! * polcoeff(subst( (1 + y) / (1 - y), y, exp(x + x * O(x^n)) - 1), n))} /* Michael Somos, Mar 04 2004 */

{a(n)=polcoeff(sum(m=0, n, 2^m*m!*x^m/prod(k=1, m, 1+k*x+x*O(x^n))), n)} \\ Paul D. Hanna, Jul 20 2011

from math import comb
from functools import lru_cache
@lru_cache(maxsize=None)
def A000629(n): return 1+sum(comb(n,j)*A000629(j) for j in range(n)) if n else 1 # Chai Wah Wu, Sep 25 2023

a(n) = 2*A000670(n) - 0^n. - Michael Somos, Jan 08 2011
O.g.f.: Sum_{n>=0} 2^n*n!*x^n / Product_{k=0..n} (1+k*x). - Paul D. Hanna, Jul 20 2011
E.g.f.: exp(x) / (2 - exp(x)) = d/dx log(1 / (2 - exp(x))).
a(n) = Sum_{k>=1} k^n/2^k.
a(n) = 1 + Sum_{j=0..n-1} C(n, j)*a(j).
a(n) = round(n!/log(2)^(n+1)) (just for n <= 15). - Henry Bottomley, Jul 04 2000
a(n) is asymptotic to n!/log(2)^(n+1). - Benoit Cloitre, Oct 20 2002
a(n) = Sum_{k=0..n} (-1)^(n-k)*Stirling2(n, k)*k!*2^k. - Vladeta Jovovic, Sep 29 2003
a(n) = Sum_{k=1..n} A008292(n, k)*2^k; A008292: triangle of Eulerian numbers. - Philippe Deléham, Jun 05 2004
a(1) = 1, a(n) = 2*Sum_{k=1..n-1} k!*A008277(n-1, k) for n>1 or a(n) = Sum_{k=1..n} (k-1)!*A008277(n, k). - Mike Zabrocki, Feb 05 2005
a(n) = Sum_{k=0..n} Stirling2(n+1, k+1)*k!. - Paul Barry, Apr 20 2005
A000629 = binomial transform of this sequence. a(n) = sum of terms in n-th row of A028246. - Gary W. Adamson, May 30 2005
a(n) = 2*(-1)^n * n!*Laguerre(n,P((.),2)), umbrally, where P(j,t) are the polynomials in A131758. - Tom Copeland, Sep 28 2007
a(n) = 2^n*A(n,1/2); A(n,x) the Eulerian polynomials. - Peter Luschny, Aug 03 2010
a(n) = (-1)^n*b(n), where b(n) = -2*Sum_{k=0..n-1} binomial(n,k)*b(k), b(0)=1. - Vladimir Kruchinin, Jan 29 2011
Row sums of A028246. Let f(x) = x+x^2. Then a(n+1) = (f(x)*d/dx)^n f(x) evaluated at x = 1. - Peter Bala, Oct 06 2011
O.g.f.: 1+2*x/(U(0)-2*x) where U(k)=1+3*x+3*x*k-2*x*(k+2)*(1+x+x*k)/U(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 14 2011
E.g.f.: exp(x)/(2 - exp(x)) = 2/(2-Q(0))-1; Q(k)=1+x/(2*k+1-x*(2*k+1)/(x+(2*k+2)/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Nov 14 2011
G.f.: 1 / (1 - 2*x / (1 - 1*x / (1 - 4*x / (1 - 2*x / (1 - 6*x / ...))))). - Michael Somos, Apr 27 2012
PSUM transform of A162509. BINOMIAL transform is A007047. - Michael Somos, Apr 27 2012
G.f.: 1/G(0) where G(k) = 1 - x*(2*k+2)/( 1 - x*(k+1)/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Mar 23 2013
E.g.f.: 1/E(0) where E(k) = 1 - x/(k+1)/(1 - 1/(1 + 1/E(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Mar 27 2013
G.f.: T(0)/(1-2*x), where T(k) = 1 - 2*x^2*(k+1)^2/(2*x^2*(k+1)^2 - (1 - 2*x - 3*x*k)*(1 - 5*x - 3*x*k)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 29 2013
a(n) = log(2)*integral_{x>=0} (ceiling(x))^n * 2^(-x) dx. - Peter Bala, Feb 06 2015

a(19) from Michael Somos, Mar 07 2011

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

Original entry on oeis.org

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

A329739 Number of compositions of n whose run-lengths are all different.

Original entry on oeis.org

1, 1, 2, 2, 5, 8, 10, 20, 28, 41, 62, 102, 124, 208, 278, 426, 571, 872, 1158, 1718, 2306, 3304, 4402, 6286, 8446, 11725, 15644, 21642, 28636, 38956, 52296, 70106, 93224, 124758, 165266, 218916, 290583, 381706, 503174, 659160, 865020, 1124458, 1473912, 1907298

Offset: 0

Gus Wiseman, Nov 20 2019

nonn

A composition of n is a finite sequence of positive integers with sum n.

			The a(1) = 1 through a(7) = 20 compositions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)
       (11)  (111)  (22)    (113)    (33)      (115)
                    (112)   (122)    (114)     (133)
                    (211)   (221)    (222)     (223)
                    (1111)  (311)    (411)     (322)
                            (1112)   (1113)    (331)
                            (2111)   (3111)    (511)
                            (11111)  (11112)   (1114)
                                     (21111)   (1222)
                                     (111111)  (2221)
                                               (4111)
                                               (11113)
                                               (11122)
                                               (22111)
                                               (31111)
                                               (111112)
                                               (111211)
                                               (112111)
                                               (211111)
                                               (1111111)

The normal case is A329740.
The case of partitions is A098859.
Strict compositions are A032020.
Compositions with relatively prime run-lengths are A000740.
Compositions with distinct multiplicities are A242882.
Compositions with distinct differences are A325545.
Compositions with equal run-lengths are A329738.
Compositions with normal run-lengths are A329766.
Cf. A003242, A008965, A059966, A098504, A098859, A107429, A175342, A238130, A328592, A329745.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],UnsameQ@@Length/@Split[#]&]],{n,0,10}]

a(21)-a(26) from Giovanni Resta, Nov 22 2019

a(27)-a(43) from Alois P. Heinz, Jul 06 2020

A329738 Number of compositions of n whose run-lengths are all equal.

Original entry on oeis.org

1, 1, 2, 4, 6, 8, 19, 24, 45, 75, 133, 215, 401, 662, 1177, 2035, 3587, 6190, 10933, 18979, 33339, 58157, 101958, 178046, 312088, 545478, 955321, 1670994, 2925717, 5118560, 8960946, 15680074, 27447350, 48033502, 84076143, 147142496, 257546243, 450748484, 788937192

Offset: 0

Gus Wiseman, Nov 20 2019

nonn

A composition of n is a finite sequence of positive integers with sum n.

			The a(1) = 1 through a(6) = 19 compositions:
  (1)  (2)   (3)    (4)     (5)      (6)
       (11)  (12)   (13)    (14)     (15)
             (21)   (22)    (23)     (24)
             (111)  (31)    (32)     (33)
                    (121)   (41)     (42)
                    (1111)  (131)    (51)
                            (212)    (123)
                            (11111)  (132)
                                     (141)
                                     (213)
                                     (222)
                                     (231)
                                     (312)
                                     (321)
                                     (1122)
                                     (1212)
                                     (2121)
                                     (2211)
                                     (111111)

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

Compositions with relatively prime run-lengths are A000740.
Compositions with equal multiplicities are A098504.
Compositions with equal differences are A175342.
Compositions with distinct run-lengths are A329739.
Cf. A003242, A008965, A107429, A164707, A238130, A242882, A274174, A329745, A329766.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],SameQ@@Length/@Split[#]&]],{n,0,10}]

seq(n)={my(b=Vec(1/(1 - sum(k=1, n, x^k/(1+x^k) + O(x*x^n)))-1)); concat([1], vector(n, k, sumdiv(k, d, b[d])))} \\ Andrew Howroyd, Dec 30 2020

a(n) = Sum_{d|n} A003242(d).

a(n) = A329745(n) + A000005(n).

Showing 1-10 of 181 results. Next

cp's OEIS Frontend

A052825 A simple grammar: partial sums of A008965.

Views

Author

Keywords

Links

Programs

Maple

Mathematica

Sage

Formula

Extensions

A000740 Number of 2n-bead balanced binary necklaces of fundamental period 2n, equivalent to reversed complement; also Dirichlet convolution of b_n=2^(n-1) with mu(n); also number of components of Mandelbrot set corresponding to Julia sets with an attractive n-cycle.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A088218 Total number of leaves in all rooted ordered trees with n edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

Sage

Formula

A097805 Number of compositions of n with k parts, T(n, k) = binomial(n-1, k-1) for n, k >= 1 and T(n, 0) = 0^n, triangle read by rows for n >= 0 and 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Python

Sage

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica