A003239 -id:A003239 - cp's OEIS frontend

A106520 a(n) = A068875(n-1) - A003239(n).

1, 0, 0, 0, 2, 4, 18, 48, 156, 472, 1526, 4852, 16000, 52940, 178276, 605520, 2079862, 7201084, 25138878, 88358520, 312576996, 1112087012, 3977502766, 14294093652, 51596165872, 186997738504, 680272334202, 2483340387644, 9094756956908

Offset: 1

F. Chapoton, May 30 2005

nonn

This is the multiplicity of the trivial module in a sequence of modules of dimension (2*n-2)!/n! over the symmetric groups S_n, induced from modules of dimension (2*n-2)!/(n!*(n-1)!) (Catalan) over the cyclic groups C_n.

G. C. Greubel, Table of n, a(n) for n = 1..1000
F. Chapoton, On some anticyclic operads, Algebraic and Geometric Topology 5 (2005), paper no. 4, pages 53-69.

Cf. A000010, A000108, A001761.

A106520:= func< n | 2*Catalan(n-1) - (1/(2*n))*(&+[Round(Gamma(2*n/d +1)/Gamma(n/d +1)^2)*EulerPhi(d): d in Divisors(n)]) >;
[A106520(n): n in [1..40]]; // G. C. Greubel, Aug 06 2021

with(numtheory);
a:= proc(n) (2/n)*binomial(2*n-2, n-1) - (1/(2*n))*add(phi(d)*binomial(2*n/d, n/d), d = divisors(n)) end:
seq(a(n), n = 1..40);

a[n_]:= 2/n*Binomial[2*n-2, n-1] - 1/(2*n)*DivisorSum[n, EulerPhi[#]* Binomial[2*n/#, n/#]&]; Table[a[n], {n, 40}] (* Jean-François Alcover, Feb 20 2017 *)

a(n) = (2/n) * binomial(2*n-2, n-1) - 1/(2*n) * sumdiv(n, d, eulerphi(d) * binomial(2*n/d, n/d)); \\ Michel Marcus, Aug 08 2021

def a(n): return 2*catalan_number(n-1) - (1/(2*n))*sum(euler_phi(n/d)*binomial(2*d, d) for d in divisors(n))
[a(n) for n in (1..40)] # G. C. Greubel, Aug 06 2021

a(n) = (2/n) * binomial(2*n-2, n-1) - 1/(2*n) * Sum_{d divides n} phi(d) * binomial(2*n/d, n/d).

a(n) = 2*A000108(n-1) - (1/(2*n))*Sum_{d divides n} (n/d + 1)*A000108(n/d) * A000010(d). - G. C. Greubel, Aug 06 2021

Terms a(1) to a(4) prepended by G. C. Greubel, Aug 06 2021

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.

Original entry on oeis.org

1, 1, 3, 6, 15, 27, 63, 120, 252, 495, 1023, 2010, 4095, 8127, 16365, 32640, 65535, 130788, 262143, 523770, 1048509, 2096127, 4194303, 8386440, 16777200, 33550335, 67108608, 134209530, 268435455, 536854005, 1073741823, 2147450880

Offset: 1

N. J. A. Sloane

Also number of compositions of n into relatively prime parts (that is, the gcd of all the parts is 1). Also number of subsets of {1,2,..,n} containing n and consisting of relatively prime numbers. - Vladeta Jovovic, Aug 13 2003
Also number of perfect parity patterns that have exactly n columns (see A118141). - Don Knuth, May 11 2006
a(n) is odd if and only if n is squarefree (Tim Keller). - Emeric Deutsch, Apr 27 2007
a(n) is a multiple of 3 for all n>=3 (see Problem 11161 link). - Emeric Deutsch, Aug 13 2008
Row sums of triangle A143424. - Gary W. Adamson, Aug 14 2008
a(n) is the number of monic irreducible polynomials with nonzero constant coefficient in GF(2)[x] of degree n. - Michel Marcus, Oct 30 2016
a(n) is the number of aperiodic compositions of n, the number of compositions of n with relatively prime parts, and the number of compositions of n with relatively prime run-lengths. - Gus Wiseman, Dec 21 2017

			For n=4, there are 6 compositions of n into coprime parts: <3,1>, <2,1,1>, <1,3>, <1,2,1>, <1,1,2>, and <1,1,1,1>.
From _Gus Wiseman_, Dec 19 2017: (Start)
The a(6) = 27 aperiodic compositions are:
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1122), (1131), (1221), (1311), (2112), (2211), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (24), (42), (51),
  (6).
The a(6) = 27 compositions into relatively prime parts are:
  (111111),
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1122), (1131), (1212), (1221), (1311), (2112), (2121), (2211), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (51).
The a(6) = 27 compositions with relatively prime run-lengths are:
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1131), (1212), (1221), (1311), (2112), (2121), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (24), (42), (51),
  (6).
(End)

H. O. Peitgen and P. H. Richter, The Beauty of Fractals, Springer-Verlag; contribution by A. Douady, p. 165.
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).

Seiichi Manyama, Table of n, a(n) for n = 1..3322 (terms 1..300 from T. D. Noe)
Hunki Baek, Sejeong Bang, Dongseok Kim, and Jaeun Lee, A bijection between aperiodic palindromes and connected circulant graphs, arXiv:1412.2426 [math.CO], 2014. See Table 2.
Donald Knuth, Robin Chapman and Reiner Martin, Problem 11243, Perfect Parity Patterns, Am. Math. Monthly 115 (7) (2008) p 668, function c(n).
Emeric Deutsch and Lafayette College Problem Group, Problem 11161: Compositions without Common Factors, American Mathematical Monthly, vol. 114, No. 4, 2007, p. 363.
H. W. Gould, Binomial coefficients, the bracket function and compositions with relatively prime summands, Fib. Quart. 2(4) (1964), 241-260.
J. E. Iglesias, A formula for the number of closest packings of equal spheres having a given repeat period, Z. Krist. 155 (1981) 121-127, Table 2.
Wolfdieter Lang, Cantor's List of Real Algebraic Numbers of Heights 1 to 7, arXiv:2307.10645 [math.NT], 2023.
Nicolae Mihalache and Francois Vigneron, Factorization of the quadratic Misiurewicz-Thurston polynomials, arXiv:2506.17662 [math.DS], 2025. See p. 8.
Robert Munafo, Enumeration of Period-N Mu-Atoms
Jeffrey Shallit and N. J. A. Sloane, Correspondence 1974-1975
François Vigneron and Nicolae Mihalache, How to split a tera-polynomial, arXiv:2402.06083 [math.NA], 2024.
Index entries for sequences related to Lyndon words

Cf. A000837, A003239, A008683, A008965, A022553, A034738, A035928, A038199, A051168, A054525, A056267, A059966, A143424, A167606, A178472, A216954, A228369, A294859, A296302.
Equals A027375/2.
See A056278 for a variant.
First differences of A085945.
Column k=2 of A143325.
Row sums of A101391.

with(numtheory): a[1]:=1: a[2]:=1: for n from 3 to 32 do div:=divisors(n): a[n]:=2^(n-1)-sum(a[n/div[j]],j=2..tau(n)) od: seq(a[n],n=1..32); # Emeric Deutsch, Apr 27 2007
with(numtheory); A000740:=n-> add(mobius(n/d)*2^(d-1), d in divisors(n)); # N. J. A. Sloane, Oct 18 2012

a[n_] := Sum[ MoebiusMu[n/d]*2^(d - 1), {d, Divisors[n]}]; Table[a[n], {n, 1, 32}] (* Jean-François Alcover, Feb 03 2012, after PARI *)

a(n) = sumdiv(n,d,moebius(n/d)*2^(d-1))

from sympy import mobius, divisors
def a(n): return sum([mobius(n // d) * 2**(d - 1) for d in divisors(n)])
[a(n) for n in range(1, 101)]  # Indranil Ghosh, Jun 28 2017

a(n) = Sum_{d|n} mu(n/d)*2^(d-1), Mobius transform of A011782. Furthermore, Sum_{d|n} a(d) = 2^(n-1).
a(n) = A027375(n)/2 = A038199(n)/2.
a(n) = Sum_{k=0..n} A051168(n,k)*k. - Max Alekseyev, Apr 09 2013
Recurrence relation: a(n) = 2^(n-1) - Sum_{d|n,d>1} a(n/d). (Lafayette College Problem Group; see the Maple program and Iglesias eq (6)). - Emeric Deutsch, Apr 27 2007
G.f.: Sum_{k>=1} mu(k)*x^k/(1 - 2*x^k). - Ilya Gutkovskiy, Oct 24 2018
G.f. satisfies Sum_{n>=1} A( (x/(1 + 2*x))^n ) = x. - Paul D. Hanna, Apr 02 2025

Connection with Mandelbrot set discovered by Warren D. Smith and proved by Robert Munafo, Feb 06 2000

Ambiguous term a(0) removed by Max Alekseyev, Jan 02 2012

A047996 Triangle read by rows: T(n,k) is the (n,k)-th circular binomial coefficient, where 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 4, 3, 1, 1, 1, 1, 3, 5, 5, 3, 1, 1, 1, 1, 4, 7, 10, 7, 4, 1, 1, 1, 1, 4, 10, 14, 14, 10, 4, 1, 1, 1, 1, 5, 12, 22, 26, 22, 12, 5, 1, 1, 1, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 1, 1, 6, 19, 43, 66, 80, 66, 43, 19, 6, 1, 1, 1, 1, 6, 22

Offset: 0

N. J. A. Sloane

Equivalently, T(n,k) = number of necklaces with k black beads and n-k white beads (binary necklaces of weight k).
The same sequence arises if we take the table U(n,k) = number of necklaces with n black beads and k white beads and read it by antidiagonals (cf. A241926). - Franklin T. Adams-Watters, May 02 2014
U(n,k) is also equal to the number of ways to express 0 as a sum of k elements in Z/nZ. - Jens Voß, Franklin T. Adams-Watters, N. J. A. Sloane, Apr 30 2014 - May 05 2014. See link ("A Note on Modular Partitions and Necklaces") for proof.
The generating function for column k is given by the substitution x_j -> x^j/(1-x^j) in the cycle index of the Symmetric Group of order k. - R. J. Mathar, Nov 15 2018
From Petros Hadjicostas, Jul 12 2019: (Start)
Regarding the comments above by Voss, Adams-Watters, and Sloane, note that Fredman (1975) proved that the number S(n, k, v) of vectors (a_0, ..., a_{n-1}) of nonnegative integer components that satisfy a_0 + ... + a_{n-1} = k and Sum_{i=0..n-1} i*a_i = v (mod n) is given by S(n, k, v) = (1/(n + k)) * Sum_{d | gcd(n, k)} A054535(d, v) * binomial((n + k)/d, k/d) = S(k, n, v).
This result was also proved by Elashvili et al. (1999), who also proved that S(n, k, v) = Sum_{d | gcd(n, k, v)} S(n/d, k/d, 1). Here, S(n, k, 0) = A241926(n, k) = U(n, k) = T(n + k, k) (where T(n, k) is the current array). Also, S(n, k, 1) = A245558(n, k). See also Panyushev (2011) for more general results and for generating functions.
Finally, note that A054535(d, v) = c_d(v) = Sum_{s | gcd(d,v)} s*Moebius(d/s). These are the Ramanujan sums, which equal also the von Sterneck function c_d(v) = phi(d) * Moebius(d/gcd(d, v))/phi(d/gcd(d, v)). We have A054535(d, v) = A054534(v, d).
It would be interesting to see whether there is a proof of the results by Fredman (1975), Elashvili et al. (1999), and Panyushev (2011) for a general v using Molien series as it is done by Sloane (2014) for the case v = 0 (in which case, A054535(d, 0) = phi(d)). (Even though the columns of array A054535(d, v) start at v = 1, we may start the array at column v = 0 as well.)
(End)
U(n, k) is the number of equivalence classes of k-tuples of residues modulo n, identifying those that differ componentwise by a constant and those that differ by a permutation. - Álvar Ibeas, Sep 21 2021

			Triangle starts:
[ 0]  1,
[ 1]  1,  1,
[ 2]  1,  1,  1,
[ 3]  1,  1,  1,  1,
[ 4]  1,  1,  2,  1,  1,
[ 5]  1,  1,  2,  2,  1,  1,
[ 6]  1,  1,  3,  4,  3,  1,  1,
[ 7]  1,  1,  3,  5,  5,  3,  1,  1,
[ 8]  1,  1,  4,  7, 10,  7,  4,  1,  1,
[ 9]  1,  1,  4, 10, 14, 14, 10,  4,  1,  1,
[10]  1,  1,  5, 12, 22, 26, 22, 12,  5,  1, 1,
[11]  1,  1,  5, 15, 30, 42, 42, 30, 15,  5, 1, 1,
[12]  1,  1,  6, 19, 43, 66, 80, 66, 43, 19, 6, 1, 1, ...

N. G. de Bruijn, Polya's theory of counting, in: Applied Combinatorial Mathematics (E. F. Beckenbach, ed.), John Wiley and Sons, New York, 1964, pp. 144-184 (implies g.f. for this triangle).
Richard Stanley, Enumerative Combinatorics, 2nd. ed., Vol 1, Chapter I, Problem 105, pp. 122 and 168, discusses the number of subsets of Z/nZ that add to 0. - N. J. A. Sloane, May 06 2014
J. Voß, Posting to Sequence Fans Mailing List, April 30, 2014.
H. S. Wilf, personal communication to N. J. A. Sloane, Nov., 1990.
See A000031 for many additional references and links.

Seiichi Manyama, Rows n=0..139 of triangle, flattened (Rows 0..50 from T. D. Noe)
Ethan Akin and Morton Davis, Bulgarian solitaire, Am. Math. Monthly 92 (4) (1985), 237-250.
J. Brandt, Cycles of partitions, Proc. Am. Math. Soc. 85 (3) (1982), 483-486, Theorem 5.
Paul Drube and Puttipong Pongtanapaisan, Annular Non-Crossing Matchings, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.
A. Elashvili and M. Jibladze, Hermite reciprocity for the regular representations of cyclic groups, Indag. Math. (N.S.) 9 (1998), no. 2, 233-238. MR1691428 (2000c:13006)
A. Elashvili, M. Jibladze, and D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), no. 2, 173--188. MR1719140 (2000j:05009). See p. 174. - _N. J. A. Sloane_, Aug 06 2014
M. L. Fredman, A symmetry relationship for a class of partitions, J. Combinatorial Theory Ser. A 18 (1975), 199-202.
Harold Fredricksen, An algorithm for generating necklaces of beads in two colors, Discrete Mathematics, Volume 61, Issues 2-3, September 1986, 181-188.
D. E. Knuth, Computer science and its relation to mathematics, Amer. Math. Monthly, 81 (1974), 323-343.
D. E. Knuth, H. Wilf, C. L. Mallows, and D. Klarner, Correspondence, 1994
Petr Lisonek, Computer-assisted Studies in Algebraic Combinatorics, Thesis, University of Linz (Austria) Sep. 1994, pp. 72-73.
D. I. Panyushev, Fredman's reciprocity, invariants of abelian groups, and the permanent of the Cayley table, J. Algebraic Combin. 33 (2011), 111-125.
Mónica A. Reyes, Cristina Dalfó, Miguel Àngel Fiol, and Arnau Messegué, A general method to find the spectrum and eigenspaces of the k-token of a cycle, and 2-token through continuous fractions, arXiv:2403.20148 [math.CO], 2024. See p. 5.
Frank Ruskey, Generate Necklaces, Lyndon words, and relatives, The Combinatorial Object Server.
Frank Ruskey and Joe Sawada, An Efficient Algorithm for Generating Necklaces with Fixed Density, SIAM J. Computing, 29 (1999) 671-684.
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
N. J. A. Sloane, A Note on Modular Partitions and Necklaces, 2014.
Pantelimon Stănică and Subhamoy Maitra, Rotation symmetric boolean functions - count and cryptographic properties, Disc. Appl. Math. 156 (2008) 1567-1580, g_{n,w} Theorem 9.
Wikipedia, Necklaces Animation [Broken link?]
Wolfram Research, Necklaces Applet.
Index entries for sequences related to necklaces

Row sums: A000031. Columns 0-12: A000012, A000012, A004526, A007997(n+5), A008610, A008646, A032191-A032197.
Cf. A051168, A052307, A052311-A052313.
See A037306 and A241926 for essentially identical triangles.
See A245558, A245559 for a closely related array.

A047996 := proc(n,k) local C,d; if k= 0 then return 1; end if; C := 0 ; for d in numtheory[divisors](igcd(n,k)) do C := C+numtheory[phi](d)*binomial(n/d,k/d) ; end do: C/n ; end proc:
seq(seq(A047996(n,k),k=0..n),n=0..10) ; # R. J. Mathar, Apr 14 2011

t[n_, k_] := Total[EulerPhi[#]*Binomial[n/#, k/#] & /@ Divisors[GCD[n, k]]]/n; t[0, 0] = 1; Flatten[Table[t[n, k], {n, 0, 13}, {k, 0, n}]] (* Jean-François Alcover, Jul 19 2011, after given formula *)

p(n) = if(n<=0, n==0, 1/n * sum(i=0,n-1, (x^(n/gcd(i,n))+1)^gcd(i,n) ));
for (n=0,17, print(Vec(p(n)))); /* print triangle */
/* Joerg Arndt, Sep 28 2012 */

T(n,k) = if(n<=0, n==0, 1/n * sumdiv(gcd(n,k), d, eulerphi(d)*binomial(n/d,k/d) ) );
/* print triangle: */
{ for (n=0, 17, for (k=0, n, print1(T(n,k),", "); ); print(); ); }
/* Joerg Arndt, Oct 21 2012 */

T(n, k) = (1/n) * Sum_{d | (n, k)} phi(d)*binomial(n/d, k/d).
T(2*n,n) = A003239(n); T(2*n+1,n) = A000108(n). - Philippe Deléham, Jul 25 2006
G.f. for row n (n>=1):  (1/n) * Sum_{i=0..n-1} ( x^(n/gcd(i,n)) + 1 )^gcd(i,n). - Joerg Arndt, Sep 28 2012
G.f.: Sum_{n, k >= 0} T(n, k)*x^n*y^k = 1 - Sum_{s>=1} (phi(s)/s)*log(1-x^s*(1+y^s)). - Petros Hadjicostas, Oct 26 2017
Product_{d >= 1} (1 - x^d - y^d) = Product_{i,j >= 0} (1 - x^i*y^j)^T(i+j, j), where not both i and j are zero. (It follows from Somos' infinite product for array A051168.) - Petros Hadjicostas, Jul 12 2019

Name edited by Petros Hadjicostas, Nov 16 2017

A022553 Number of binary Lyndon words containing n letters of each type; periodic binary sequences of period 2n with n zeros and n ones in each period.

Original entry on oeis.org

1, 1, 1, 3, 8, 25, 75, 245, 800, 2700, 9225, 32065, 112632, 400023, 1432613, 5170575, 18783360, 68635477, 252085716, 930138521, 3446158600, 12815663595, 47820414961, 178987624513, 671825020128, 2528212128750, 9536894664375, 36054433807398, 136583760011496

Offset: 0

David Broadhurst

Also number of asymmetric rooted plane trees with n+1 nodes. - Christian G. Bower
Conjecturally, number of irreducible alternating Euler sums of depth n and weight 3n.
a(n+1) is inverse Euler transform of A000108. Inverse Witt transform of A006177.
Dimension of the degree n part of the primitive Lie algebra of the Hopf algebra CQSym (Catalan Quasi-Symmetric functions). - Jean-Yves Thibon (jyt(AT)univ-mlv.fr), Oct 22 2006
For n>0, 2*a(n) is divisible by n (cf. A268619), 12*a(n) is divisible by n^2 (cf. A268592). - Max Alekseyev, Feb 09 2016

			a(3)=3 counts 6-periodic 000111, 001011 and 001101. a(4)=8 counts 00001111, 00010111, 00011011, 00011101, 00100111, 00101011, 00101101, and 00110101. - _R. J. Mathar_, Oct 20 2021

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 336 (4.4.64)

Alois P. Heinz, Table of n, a(n) for n = 0..1000
M. J. H. Al-Kaabi, Monomial Bases for Free Post-Lie Algebras, IOP Conf. Ser.: Mater. Sci. Eng. (2020) Vol. 871, 012048.
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 pp. 3, 6.
David J. Broadhurst, On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory, arXiv:hep-th/9604128, 1996.
Gilbert Labelle and Pierre Leroux, Enumeration of (uni- or bicolored) plane trees according to their degree distribution, Disc. Math. 157 (1996) 227-240, Eq. (1.20).
Hans Munthe-Kaas and Alexander Lundervold, On post-Lie algebras, Lie-Butcher series and moving frames, arXiv preprint arXiv:1203.4738 [math.NA], 2012. - From _N. J. A. Sloane_, Sep 20 2012
Jean-Christophe Novelli and Jean-Yves Thibon, Hopf algebras and dendriform structures arising from parking functions, arXiv:math/0511200 [math.CO], 2005.
Tilman Piesk, List of 2n-bead balanced binary Lyndon words for n=1...8
Yash Puri and Thomas Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
Index entries for sequences related to rooted trees
Index entries for sequences related to Lyndon words

Cf. A003239, A005354, A000740, A007727, A086655, A289978 (multiset trans.), A001037 (binary Lyndon wds.), A074655 (3 letters), A074656 (4 letters).

A diagonal of the square array described in A051168.

with(numtheory):
a:= n-> `if`(n=0, 1,
        add(mobius(n/d)*binomial(2*d, d), d=divisors(n))/(2*n)):
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 21 2011

a[n_] := Sum[MoebiusMu[n/d]*Binomial[2d, d], {d, Divisors[n]}]/(2n); a[0] = 1; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 02 2015 *)

a(n)=if(n<1,n==0,sumdiv(n,d,moebius(n/d)*binomial(2*d,d))/2/n)

from sympy import mobius, binomial, divisors
def a(n):
    return 1 if n == 0 else sum(mobius(n//d)*binomial(2*d, d) for d in divisors(n))//(2*n)
print([a(n) for n in range(31)]) # Indranil Ghosh, Aug 05 2017

def a(n):
    return 1 if n ==0 else sum(moebius(n//d)*binomial(2*d, d) for d in divisors(n))//(2*n)
# F. Chapoton, Apr 23 2020

a(n) = A060165(n)/2 = A007727(n)/(2*n) = A045630(n)/n.
Product_n (1-x^n)^a(n) = 2/(1+sqrt(1-4*x));  a(n) = 1/(2*n) * Sum_{d|n} mu(n/d)*C(2*d,d). Also Moebius transform of A003239. - Christian G. Bower
a(n) ~ 2^(2*n-1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 11 2014
G.f.: 1 + Sum_{k>=1} mu(k)*log((1 - sqrt(1 - 4*x^k))/(2*x^k))/k. - Ilya Gutkovskiy, May 18 2019

A002995 Number of unlabeled planar trees (also called plane trees) with n nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 6, 14, 34, 95, 280, 854, 2694, 8714, 28640, 95640, 323396, 1105335, 3813798, 13269146, 46509358, 164107650, 582538732, 2079165208, 7457847082, 26873059986, 97239032056, 353218528324, 1287658723550, 4709785569184

Offset: 0

N. J. A. Sloane

Noncrossing handshakes of 2(n-1) people (each using only one hand) on round table, up to rotations - Antti Karttunen, Sep 03 2000
Equivalently, the number of noncrossing partitions up to rotation composed of n-1 blocks of size 2. - Andrew Howroyd, May 04 2018
a(n), n>2, is also the number of oriented cacti on n-1 unlabeled nodes with all cutpoints of separation degree 2, i.e. ones shared only by two (cyclic) blocks. These are digraphs (without loops) that have a unique Eulerian tour. Such digraphs with labeled nodes are enumerated by A102693. - Valery A. Liskovets, Oct 19 2005
Labeled plane trees are counted by A006963. - David Callan, Aug 19 2014
This sequence is similar to A000055 but those trees are not embedded in a plane. - Michael Somos, Aug 19 2014

			G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 14*x^7 + 34*x^8 + 95*x^9 + ...
a(7) = 14 = 11 + 3 because there are 11 trees with 7 nodes but three of them can be embedded in a plane in two ways. These three trees have degree sequences 4221111, 3321111, 3222111, where there are two trees with each degree sequence but in the first, the two nodes of degree two are adjacent, in the second, the two nodes of degree three are adjacent, and in the third, the node of degree three is adjacent to two nodes of degree two. - _Michael Somos_, Aug 19 2014

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 304.
A. Errera, De quelques problèmes d'analysis situs, Comptes Rend. Congr. Nat. Sci. Bruxelles, (1930), 106-110.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 67, (3.3.26).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=0..200
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, pp. 285 (4.1.26), 291 (4.1.48)
CombOS - Combinatorial Object Server, Generate free plane trees
R. Cori and M. Marcus, Counting non-isomorphic chord diagrams, Theor. Comp. Sci. 204 (1998) 55-75, Corollary 5.2.
Paul Drube and Puttipong Pongtanapaisan, Annular Non-Crossing Matchings, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.
A. Errera, Reviews of two articles on Analysis Situs, from Fortschritte [Annotated scanned copy]
D. Feldman, Counting plane trees, Unpublished manuscript, 1992. (Annotated scanned copy)
Bernold Fiedler, Scalar polynomial vector fields in real and complex time, arXiv:2410.05043 [math.DS], 2024. See pp. 21, 50.
Bernold Fiedler, Real-time blow-up and connection graphs of rational vector fields on the Riemann sphere, arXiv:2504.20503 [math.DS], 2025. See p. 23.
F. Harary and R. W. Robinson, The number of achiral trees, J. Reine Angew. Math., 278 (1975), 322-335.
F. Harary and R. W. Robinson, The number of achiral trees, J. Reine Angew. Math., 278 (1975), 322-335. (Annotated scanned copy)
G. Labelle, Sur la symétrie et l'asymétrie des structures combinatoires, Theor. Comput. Sci. 117, No. 1-2, 3-22 (1993).
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
Torsten Mütze, Proof of the middle levels conjecture, arXiv preprint arXiv:1404.4442 [math.CO], 2014.
Torsten Mütze, A book proof of the middle levels theorem, arXiv:2306.13019 [math.CO], 2023.
Torsten Mütze and Franziska Weber, Construction of 2-factors in the middle layer of the discrete cube, arXiv preprint arXiv:1111.2413 [math.CO], 2011.
Torsten Mütze and F. Weber, Construction of 2-factors in the middle layer of the discrete cube, Journal of Combinatorial Theory, Series A, 119(8) (2012), 1832-1855.
J. Sawada, Generating rooted and free plane trees, ACM Transactions on Algorithms, Vol. 2 No. 1 (2006), 1-13.
Seunghyun Seo and Heesung Shin, Two involutions on vertices of ordered trees, FPSAC'02 (2002). (see p_n).
Alexander Stoimenow, On the number of chord diagrams, Discr. Math. 218 (2000), 209-233. See Table 1.
D. W. Walkup, The number of plane trees, Mathematika, vol. 19, No. 2 (1972), 200-204.
Index entries for sequences related to trees

Column k=2 of A303694 and A303864.

Cf. A000055, A000108, A002996, A003239, A005354, A057502, A061417, A064640.

with (powseries): with (combstruct): n := 27: Order := n+2: sys := {C = Cycle(B), B = Union(Z,Prod(B,B))}: G003239 := (convert(gfseries(sys,unlabeled,x) [C(x)], polynom)) / x: G000108 := convert(taylor((1-sqrt(1-4*x)) / (2*x),x),polynom): G002995 := 1 + G003239 + (eval(G000108,x=x^2) - G000108^2)/2: A002995 := 1,1,1,seq(coeff(G002995,x^i),i=1..n); # Ulrich Schimke, Apr 05 2002
with(combinat): with(numtheory): m := 2: for p from 2 to 28 do s1 := 0: s2 := 0: for d from 1 to p do if p mod d = 0 then s1 := s1+phi(p/d)*binomial(m*d, d) fi: od: for d from 1 to p-1 do if gcd(m, p-1) mod d = 0 then s2 := s2+phi(d)*binomial((p*m)/d, (p-1)/d) fi: od: printf(`%d, `, (s1+s2)/(m*p)-binomial(m*p, p)/(p*(m-1)+1)) od : # Zerinvary Lajos, Dec 01 2006

a[0] = a[1] = 1; a[n_] := (1/(2*(n-1)))*Sum[ EulerPhi[(n-1)/d]*Binomial[2*d, d], {d, Divisors[n-1]}] - CatalanNumber[n-1]/2 + If[ EvenQ[n], CatalanNumber[n/2-1]/2, 0]; Table[ a[n], {n, 0, 29}] (* Jean-François Alcover, Mar 07 2012, from formula *)

catalan(n) = binomial(2*n, n)/(n+1);
a(n) = if (n<2, 1, n--; sumdiv(n, d, eulerphi(n/d)*binomial(2*d, d))/(2*n) - catalan(n)/2 + if ((n-1) % 2, 0, catalan((n-1)/2)/2)); \\ Michel Marcus, Jan 23 2016

G.f.: 1+B(x)+(C(x^2)-C(x)^2)/2 where B is g.f. of A003239 and C is g.f. of A000108(n-1).

a(n) = 1/(2*(n-1))*sum{d|(n-1)}(phi((n-1)/d)*binomial(2d, d)) - A000108(n-1)/2 + (if n is even) A000108(n/2-1)/2.

More terms, formula from Christian G. Bower, Dec 15 1999

Name corrected ("labeled" --> "unlabeled") by David Callan, Aug 19 2014

A057509 Permutation of natural numbers: rotations of the bottom branches of the rooted plane trees encoded by A014486.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 5, 7, 8, 9, 11, 14, 16, 19, 10, 15, 12, 17, 18, 13, 20, 21, 22, 23, 25, 28, 30, 33, 37, 39, 42, 44, 47, 51, 53, 56, 60, 24, 29, 38, 43, 52, 26, 40, 31, 45, 46, 32, 48, 49, 50, 27, 41, 34, 54, 55, 35, 57, 58, 59, 36, 61, 62, 63, 64, 65, 67, 70, 72, 75, 79, 81

Offset: 0

Antti Karttunen, Sep 03 2000

nonn

The number of objects (rooted planar trees, mountain ranges, parenthesizations) fixed by this permutation can be computed with procedure fixedcount, which gives A034731.

Index entries for sequences that are permutations of the natural numbers
A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)

Inverse of A057510 and the car/cdr-flipped conjugate of A069775 and also composition of A069770 & A057501, i.e. A057509(n) = A057163(A069775(A057163(n))) = A057501(A069770(n)).

Cycle counts given by A003239. Cf. also A057511.

map(CatalanRankGlobal,map(RotateBottomBranchesL, A014486));
RotateBottomBranchesL := n -> pars2binexp(rotateL(binexp2pars(n)));
rotateL := proc(a) if 0 = nops(a) then (a) else [op(cdr(a)), a[1]]; fi; end;
fixedcount := proc(n) local d,z; z := 0; for d in divisors(n) do z := z+C(d-1); od; RETURN(z); end;

A057510 Permutation of natural numbers: rotations of the bottom branches of the rooted plane trees encoded by A014486. (to opposite direction of A057509).

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 5, 7, 8, 9, 14, 10, 16, 19, 11, 15, 12, 17, 18, 13, 20, 21, 22, 23, 37, 24, 42, 51, 25, 38, 26, 44, 47, 27, 53, 56, 60, 28, 39, 29, 43, 52, 30, 40, 31, 45, 46, 32, 48, 49, 50, 33, 41, 34, 54, 55, 35, 57, 58, 59, 36, 61, 62, 63, 64, 65, 107, 66, 121, 149, 67

Offset: 0

Antti Karttunen, Sep 03 2000

nonn

Index entries for sequences that are permutations of the natural numbers
A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)

Inverse of A057509 and the car/cdr-flipped conjugate of A069776 and also composition of A057502 & A069770, i.e. A057510(n) = A057163(A069776(A057163(n))) = A069770(A057502(n)).

Cycle counts given by A003239. Cf. also A057512, A057513.

# reverse given in A057508, for CountCycles, see A057502, for other procedures, follow A057501.
map(CatalanRankGlobal,map(RotateBottomBranchesR, A014486));
RotateBottomBranchesR := n -> pars2binexp(rotateR(binexp2pars(n)));
rotateR := a -> reverse(rotateL(reverse(a)));
RotBBPermutationCycleCounts := proc(upto_n) local u,n,a,r,b; a := []; for n from 0 to upto_n do b := []; u := (binomial(2*n,n)/(n+1)); for r from 0 to u-1 do b := [op(b),1+CatalanRank(n,RotateBottomBranchesL(CatalanUnrank(n,r)))]; od; a := [op(a),CountCycles(b)]; od; RETURN(a); end;
A003239 := RotBBPermutationCycleCounts(some_value); (e.g. 9. Cf. A057502, A057162)

A208183 Number of distinct k-colored necklaces with n beads per color; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 6, 16, 4, 1, 1, 1, 24, 318, 188, 10, 1, 1, 1, 120, 11352, 30804, 2896, 26, 1, 1, 1, 720, 623760, 11211216, 3941598, 50452, 80, 1, 1, 1, 5040, 48648960, 7623616080, 15277017432, 586637256, 953056, 246, 1, 1

Offset: 0

Alois P. Heinz, Feb 24 2012

From Vaclav Kotesovec, Aug 23 2015: (Start)
Column k > 1 is asymptotic to k^(k*n-1/2) / ((2*Pi)^((k-1)/2) * n^((k+1)/2)).
Row r > 0 is asymptotic to (r*n)! / (r*n*(r!)^n). (End)

			A(1,4) =  6: {0123, 0132, 0213, 0231, 0312, 0321}.
A(3,2) =  4: {000111, 001011, 010011, 010101}.
A(4,2) = 10: {00001111, 00010111, 00100111, 01000111, 00011011, 00110011, 00101011, 01010011, 01001011, 01010101}.
Square array A(n,k) begins:
  1, 1,  1,     1,         1,              1, ...
  1, 1,  1,     2,         6,             24, ...
  1, 1,  2,    16,       318,          11352, ...
  1, 1,  4,   188,     30804,       11211216, ...
  1, 1, 10,  2896,   3941598,    15277017432, ...
  1, 1, 26, 50452, 586637256, 24934429725024, ...

Alois P. Heinz, Antidiagonals n = 0..35, flattened

Rows n=0-8 give: A000012, A104150, A137729, A208184, A208185, A208186, A208187, A208188, A208189.
Columns k=0+1, 2-8 give: A000012, A003239, A118644, A207816, A208190, A208191, A208192, A208193.
Main diagonal gives A252765.
Cf. A000010, A000142.

with(numtheory):
A:= (n, k)-> `if`(n=0 or k=0, 1,
              add(phi(n/d) *(k*d)!/(d!^k *k*n), d=divisors(n))):
seq(seq(A(n, d-n), n=0..d), d=0..10);

A[n_, k_] :=  If[n == 0 || k == 0, 1, Sum[EulerPhi[n/d]*(k*d)!/(d!^k*k*n), {d, Divisors[n]}]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 27 2013, translated from Maple *)

A(n,k) = Sum_{d|n} phi(n/d)*(k*d)!/(d!^k*k*n) if n,k>0; A(n,k) = 1 else.

A(n,k) = Sum_{i=1..n} (k*gcd(n,i))!/(gcd(n,i)!^k*k*n) = Sum_{i=1..n} (k*n/gcd(n,i))!/((n/gcd(n,i))!^k*k*n)*phi(gcd(n,i))/phi(n/gcd(n,i)) for n,k >= 1, where phi = A000010. - Richard L. Ollerton, May 19 2021

A241926 Table read by antidiagonals: T(n,k) (n >= 1, k >= 1) is the number of necklaces with n black beads and k white beads.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 3, 4, 3, 1, 1, 3, 5, 5, 3, 1, 1, 4, 7, 10, 7, 4, 1, 1, 4, 10, 14, 14, 10, 4, 1, 1, 5, 12, 22, 26, 22, 12, 5, 1, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 6, 19, 43, 66, 80, 66, 43, 19, 6, 1, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1

Offset: 1

Franklin T. Adams-Watters, May 02 2014

Turning over the necklace is not allowed (the group is cyclic not dihedral). T(n,k) = T(k,n) follows immediately from the formula. - N. J. A. Sloane, May 03 2014

T(n, k) is the number of equivalence classes of k-tuples of residues modulo n, identifying those that differ componentwise by a constant and those that differ by a permutation. - Álvar Ibeas, Sep 21 2021

			The table starts:
  1, 1,  1,  1,  1,  1,   1,   1,   1,   1,   1,    1, ...
  1, 2,  2,  3,  3,  4,   4,   5,   5,   6,   6,    7, ...
  1, 2,  4,  5,  7, 10,  12,  15,  19,  22,  26,   31, ...
  1, 3,  5, 10, 14, 22,  30,  43,  55,  73,  91,  116, ...
  1, 3,  7, 14, 26, 42,  66,  99, 143, 201, 273,  364, ...
  1, 4, 10, 22, 42, 80, 132, 217, 335, 504, 728, 1038, ...
  ...

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Paul Drube and Puttipong Pongtanapaisan, Annular Non-Crossing Matchings, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.
A. Elashvili and M. Jibladze, Hermite reciprocity for the regular representations of cyclic groups, Indag. Math. (N.S.) 9 (1998), no. 2, 233--238. MR1691428 (2000c:13006)
A. Elashvili, M. Jibladze and D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), no. 2, 173--188. MR1719140 (2000j:05009). See p. 174. - _N. J. A. Sloane_, Aug 06 2014
N. J. A. Sloane, A Note on Modular Partitions and Necklaces

Same as A047996 with first row and main diagonal removed.
A037306 is yet another version.
Cf. A003239 (main diagonal).
See A245558, A245559 for a closely related array.

# Maple program for the table - N. J. A. Sloane, May 03 2014:
with(numtheory);
T:=proc(n,k) local d, s, g, t0;
t0:=0; s:=n+k; g:=gcd(n,k);
for d from 1 to s do
   if (g mod d) = 0 then t0:=t0+phi(d)*binomial(s/d,k/d); fi;
od: t0/s; end;
r:=n->[seq(T(n,k),k=1..12)];
[seq(r(n),n=1..12)];

T[n_, k_] := DivisorSum[GCD[n, k], EulerPhi[#] Binomial[(n+k)/#, n/#]& ]/ (n+k); Table[T[n-k+1, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Dec 02 2015 *)

T(n,k) = sumdiv(gcd(n,k),d,eulerphi(d)*binomial((n+k)\d,n\d))/(n+k)

T(n,k) = (Sum_{d | gcd(n,k)} phi(d)*binomial((n+k)/d, n/d))/(n+k). [Corrected by N. J. A. Sloane, May 03 2014]

Edited by N. J. A. Sloane, May 03 2014

Elashvili et al. references supplied by Vladimir Popov, May 17 2014

A005648 Number of 2n-bead black-white reversible necklaces with n black beads.

Original entry on oeis.org

1, 1, 2, 3, 8, 16, 50, 133, 440, 1387, 4752, 16159, 56822, 200474, 718146, 2587018, 9398520, 34324174, 126068558, 465093571, 1723176308, 6407924300, 23910576230, 89494164973, 335913918902, 1264107416466

Offset: 0

N. J. A. Sloane

a(n) is the coefficient of c_1^n*c_2^n in the cycle index polynomial for the dihedral group D_{2*n} evaluated with the figure counting polynomial c = c_1 + c_2, n>=1, abbreviated as Z(D_{2*n},c). See, e.g., the Harary-Palmer reference (given under A212355), p. 42, Theorem (PET), and the example for all 6 two-colored 4-bracelets (called there necklaces) on p. 44, Figure 2.4.2. - Wolfdieter Lang, Jun 05 2012

			a(2) = 2: BBWW, BWBW.
a(3) = 3: BBBWWW, BBWBWW, BWBWBW.
a(4) = 8: BBBBWWWW, BBBWBWWW, BBBWWBWW, BBWWBBWW, BBWBWBWW, BBWBWWBW, BBWBBWWW, BWBWBWBW.

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

G. C. Greubel, Table of n, a(n) for n = 0..1665 (terms 0..200 from Andrew Howroyd)
Marcia Ascher, Mu torere: an analysis of a Maori game, Math. Mag. 60 (1987), no. 2, 90-100.
R. K. Guy & N. J. A. Sloane, Correspondence, 1985
Paul Melotti, Sanjay Ramassamy, Paul Thévenin, Points and lines configurations for perpendicular bisectors of convex cyclic polygons, arXiv:2003.11006 [math.CO], 2020.
E. M. Palmer and R. W. Robinson, Enumeration of self-dual configurations Pacific J. Math., 110 (1984), 203-221.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Index entries for sequences related to bracelets

Cf. A000984, A003239.

f[k_Integer, n_] := (Plus @@ (EulerPhi[ # ]Binomial[n/#, k/# ] & /@ Divisors[GCD[n, k]])/n + Binomial[(n - If[OddQ@n, 1, If[OddQ@k, 2, 0]])/2, (k - If[OddQ@k, 1, 0])/2])/2 (* Robert A. Russell, Sep 27 2004 *)
Table[ f[n, 2n], {n, 27}] (* Robert G. Wilson v, Mar 29 2006 *)
a[0] = 1; a[n_] := 1/2*(Binomial[2*Quotient[n, 2], Quotient[n, 2]] + DivisorSum[n, EulerPhi[#]*Binomial[2*n/#, n/#]&]/(2*n)); Array[a, 26, 0] (* Jean-François Alcover, Nov 05 2017, translated from PARI *)

a(n) = 1/2*( binomial(2*(n\2), n\2) + if(n<1, n >= 0, sumdiv(n, k, eulerphi(k)*binomial(2*n/k, n/k))/(2*n) ));

a(n) = ( Sum_{d|n} phi(n/d)*C(2*d, d) )/(4*n) + C(2*k, k)/2, where k = floor(n/2). - Michael Somos

a(n) = (A003239(n) + C(2*k, k))/2, where k = [ n/2 ]. - R. J. Fletcher, (yylee(AT)mail.ncku.edu.tw)

Sequence extended and description corrected by Christian G. Bower

Example n=8 (word no. 6) corrected by Wolfdieter Lang, Jun 05 2012

cp's OEIS Frontend

A106520 a(n) = A068875(n-1) - A003239(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

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

A047996 Triangle read by rows: T(n,k) is the (n,k)-th circular binomial coefficient, where 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A022553 Number of binary Lyndon words containing n letters of each type; periodic binary sequences of period 2n with n zeros and n ones in each period.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Sage

Formula

A002995 Number of unlabeled planar trees (also called plane trees) with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A057509 Permutation of natural numbers: rotations of the bottom branches of the rooted plane trees encoded by A014486.