A006079 -id:A006079 - cp's OEIS frontend

A007123 Number of connected unit interval graphs with n nodes; also number of bracelets (turnover necklaces) with n black beads and n-1 white beads.

1, 1, 2, 4, 10, 26, 76, 232, 750, 2494, 8524, 29624, 104468, 372308, 1338936, 4850640, 17685270, 64834550, 238843660, 883677784, 3282152588, 12233309868, 45741634536, 171530482864, 644953425740, 2430975800876, 9183681736376, 34766785487152, 131873995933480

Offset: 1

N. J. A. Sloane

Also number of rooted planar general trees (of n vertices or n-1 edges) up to reflection. - Antti Karttunen, Aug 09 2002 (For the correspondence with bracelets, start by considering Raney's lemma as explained by Graham, Knuth & Patashnik.)
Number of connected lattice path matroids on n elements up to isomorphism.
a(n) = number of noncrossing set partitions of [n] up to reflection (i<->n+1-i). Example: a(4) counts 123, 1-23, 13-2, 1-2-3 but not 12-3 because it is the reflection of 1-23. - David Callan, Oct 08 2005
From Vladimir Shevelev, Apr 23 2011: (Start)
Also number of non-equivalent necklaces of n beads, each of which is painted by one of 2*n-1 colors.
The sequence solves the so-called Reis problem about convex k-gons in case N=2*n-1, k=n. H. Gupta (1979) gave a full solution; I gave a short proof of Gupta's result and showed an equivalence of this problem and each of the following problems: the problem of enumerating the bracelets of n beads of 2 colors, k of them black, and the problem of enumerating the necklaces of k beads, each painted by one of n colors.
a(n) is an essentially unimprovable upper estimate for the number of distinct values of the permanent in (0,1)-circulants of order 2*n-1 with n 1's in every row. (End)
The number of Dyck paths of semilength n-1 up to reversal; that is, the number of Dyck paths of semilength n-1, treating as identical a path and that path when traveled in reverse order. - Noah A Rosenberg, Jan 28 2019

			x + x^2 + 2*x^3 + 4*x^4 + 10*x^5 + 26*x^6 + 76*x^7 + 232*x^8 + 750*x^9 + ...

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.7.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 345 & 346.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1980.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..1670 (first 190 terms from R. W. Robinson)
J. E. Bonin, A. de Mier, and M. Noy, Lattice path matroids: enumerative aspects and Tutte polynomials, arXiv:math/0211188 [math.CO], 2002.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs., Vol. 3 (2000), #00.1.5.
Hansraj Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 964-999.
Z. M. Himwich and N. A. Rosenberg, Roadblocked monotonic paths and the enumeration of coalescent histories for non-matching caterpillar gene trees and species trees, arXiv:1901.04465 [qbio.PE], 2019; Adv. Appl. Math. 113 (2020), 101939. (cf. Table 1)
Claudio Procesi, Some special bases of the 2-swap algebras, arXiv:2406.18687 [math.QA], 2024. See p. 3.
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]
Vladimir Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
Vladimir Shevelev, Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha,beta,gamma), arXiv:1104.4051 [math.CO], 2011. (Cf. Section 5).
Index entries for sequences related to bracelets

Cf. A000108, A002420, A007595, A063886, A073201.
Occurs as row 164 in A073201.
Next-to-center columns of triangle A052307.
Equal to A001405 plus A006079.

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 - 1], {n, 10}]
(* Comment from Wouter Meeussen, Feb 02 2013, added by N. J. A. Sloane, Feb 02 2013: To get lists of the necklaces in Mathematica, use (if n=4, say):
<

{a(n) = if( n<1, 0, (2 * binomial(n-1, (n-1)\2) + binomial(2*n, n) / (2*n - 1)) / 4)} /* Michael Somos, Apr 16 2012 */

from sympy import catalan, binomial, floor
def a(n): return 1 if n==1 else (catalan(n - 1) + binomial(n - 1, floor((n - 1)/2)))/2 # Indranil Ghosh, Jun 03 2017

a(n+1) = (Catalan(n) + binomial(n, floor(n/2)))/2 = (A000108(n) + A001405(n))/2. - Antti Karttunen, Aug 09 2002
G.f.: (1 + 2*x - sqrt(1 - 4*x)*sqrt(1 - 4*x^2))/(4*sqrt(1 - 4*x^2)).
G.f.: (sqrt((1 + 2*x) / (1 - 2*x)) - sqrt(1 - 4*x)) / 4. - Michael Somos, Apr 16 2012
a(n) = (A063886(n) - A002420(n)) / 4. - Michael Somos, Apr 16 2012
D-finite with recurrence n*(n-1)*(n-4)*a(n) - 4*(n-1)*(n^2-5*n+5)*a(n-1) - 4*(n-2)*(n^2-7*n+11)*a(n-2) + 8*(2*n-7)*(n-2)*(n-3)*a(n-3)=0. - R. J. Mathar, Aug 22 2018

Extended by Christian G. Bower

Edited by Jon E. Schoenfield, Feb 14 2015

A006082 Number of labeled projective plane trees (or "flat" trees) with n nodes.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 12, 27, 65, 175, 490, 1473, 4588, 14782, 48678, 163414, 555885, 1913334, 6646728, 23278989, 82100014, 291361744, 1039758962, 3729276257, 13437206032, 48620868106, 176611864312, 643834562075, 2354902813742, 8640039835974, 31791594259244

Offset: 1

N. J. A. Sloane

nonn

Also, the number of noncrossing partitions up to rotation and reflection composed of n-1 blocks of size 2. - Andrew Howroyd, May 03 2018

R. W. Robinson, personal communication.
R. W. Robinson, Efficiency of power series operations for graph counting, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1982.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..500
David Feldman, Counting plane trees, Unpublished manuscript, 1992. (Annotated scanned copy)
Richard Kapolnai, Gabor Domokos, and Timea Szabo, Generating spherical multiquadrangulations by restricted vertex splittings and the reducibility of equilibrium classes, Periodica Polytechnica Electrical Engineering, 56(1):11-10, 2012. Also arXiv:1206.1698 [cs.DM], 2012. See row 2 of Table 1.
T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360. [The sequence is mentioned on page 355, but because of a miscalculation it is given, incorrectly, as 1, 1, 1, 2, 3, 6, 12, 25. Thanks to _David Broadhurst_ for this information. - _N. J. A. Sloane_, Apr 06 2022]
Feng Rong, A note on the topological classification of complex polynomial differential equations with only centre singularities, Journal of Difference Equations and Applications, Volume 18, Issue 11, 2012. - From _N. J. A. Sloane_, Dec 27 2012
P. K. Stockmeyer, The charm bracelet problem and its applications, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.
P. J. Stockmeyer, The charm bracelet problem and its applications, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974. [Scanned annotated and corrected copy]
Index entries for sequences related to trees

Column k=2 of A302828 and A303929.
Cf. A006079, A006080, A006081.
Cf. A002995 (noncrossing partitions into pairs up to rotations only), A126120, A001405, A185100.

u[n_, k_, r_] := (r*Binomial[k*n + r, n]/(k*n + r));
e[n_, k_] := Sum[ u[j, k, 1 + (n - 2*j)*k/2], {j, 0, n/2}]
c[n_, k_] := If[n == 0, 1, (DivisorSum[n, EulerPhi[n/#]*Binomial[k*#, #]&] + DivisorSum[GCD[n-1, k], EulerPhi[#]*Binomial[n*k/#, (n-1)/#]&])/(k*n) - Binomial[k*n, n]/(n*(k - 1) + 1)];
T[n_, k_] := (1/2)*(c[n, k] + If[n == 0, 1, If[OddQ[k], If[OddQ[n], 2*u[ Quotient[n, 2], k, (k + 1)/2], u[n/2, k, 1] + u[n/2 - 1, k, k]], e[n, k] + If[OddQ[n], u[Quotient[n, 2], k, k/2]]]/2]) /. Null -> 0;
a[n_] := T[n, 2];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jun 14 2018, after Andrew Howroyd and A303929 *)

\\ from David Broadhurst, Apr 06 2022, added by N. J. A. Sloane, Apr 06 2022
{A006082(n)=my(c(n)=binomial(2*n,n));
if(n<2,1,n--;(c(n)+if(n%2,2*n*(n+2),(n+1)^2)*c(n\2)
+(n+1)*sumdiv(n,d,if(d>2,eulerphi(d)*c(n/d))))/(4*n*(n+1)));}

a(n) = A006080(n) - A006081(n) + A126120(n-2). [Stockmeyer] [Corrected by Andrey Zabolotskiy, Apr 06 2021]
a(n) = (2 * A002995(n) + A126120(n-2) + A001405(n-1)) / 4 for n > 1. - Andrey Zabolotskiy, May 24 2018
There is a compact formula from David Broadhurst - see the Pari code - N. J. A. Sloane, Apr 06 2022.
a(n) ~ 2^(2*n-4) / (sqrt(Pi) * n^(5/2)). - Vaclav Kotesovec, Jun 01 2022

a(25) and a(26) from Robert W. Robinson, Oct 17 2006

a(27) and beyond from Andrew Howroyd, May 03 2018

A006080 Number of rooted projective plane trees with n nodes.

Original entry on oeis.org

1, 1, 2, 4, 9, 21, 56, 155, 469, 1480, 4882, 16545, 57384, 202060, 720526, 2593494, 9408469, 34350507, 126109784, 465200333, 1723346074, 6408356210, 23911272090, 89495909409, 335916761128, 1264114452996, 4768464309416, 18027250459483, 68291947831046, 259200707489634

Offset: 1

N. J. A. Sloane

Number of rooted planar trees that can be turned over.

Also bracelets (or necklaces) with n-1 black beads and n-1 white beads such that the beads switch colors when bracelet is turned over.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
P. K. Stockmeyer, The charm bracelet problem and its applications, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.

T. D. Noe, Table of n, a(n) for n=1..200
P. J. Stockmeyer, The charm bracelet problem and its applications, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974. [Scanned annotated and corrected copy]
Index entries for sequences related to trees
Index entries for sequences related to rooted trees
Index entries for sequences related to bracelets

Cf. A006079, A006081, A006082.

a[n_] := Sum[ EulerPhi[(n-1)/k]*(Binomial[2*k, k]/(2*(n-1))), {k, Divisors[n-1]}]/2 + 2^(n-3); a[1] = 1; Table[a[n], {n, 1, 27}] (* From Jean-François Alcover, Apr 11 2012, from formula *)

C(n, k)=binomial(n, k);
A003239(n) = if(n<=0, n==0, sumdiv(n, d, eulerphi(n/d) * C(2*d, d)) / (2*n) );
a(n) = if ( n<=1, 1, A003239(n)/2 + 2^(n-2) );
/* Joerg Arndt, Jan 25 2013 */

from sympy import binomial as C, totient, divisors
def a003239(n): return 1 if n<2 else sum([totient(n//d)*C(2*d, d) for d in divisors(n)])/(2*n)
def a(n): return 1 if n<2 else a003239(n)/2 + 2**(n - 2) # Indranil Ghosh, Apr 24 2017

Stockmeyer gives g.f.

a(n) = A003239(n)/2 + 2^(n-2). (n>=2) (corrected, Joerg Arndt, Jan 25 2013)

More terms, formula and additional comments from Christian G. Bower, Dec 13 2001

A306292 Number of asymmetric Dyck paths of semilength n.

Original entry on oeis.org

0, 0, 2, 8, 32, 112, 394, 1360, 4736, 16544, 58324, 207088, 741184, 2671008, 9688410, 35344800, 129620480, 477590080, 1767170812, 6563935664, 24465914304, 91481858208, 343058261572, 1289901443168

Offset: 1

Noah A Rosenberg, Feb 04 2019

nonn

An asymmetric Dyck path is a path that generates a distinct Dyck path when traversed in opposite order.

			For n=3, the a(2)=2 asymmetric Dyck paths are UUDDUD and UDUUDD.

J. Bonin, A. de Mier, and M. Noy, Lattice path matroids: enumerative aspects and Tutte polynomials, J Comb Theory Ser A 104 (2003), 63-94.
L.-H. Deng, E. Y. P. Deng, and L. W. Shapiro, The Riordan group and symmetric lattice paths, arXiv:0906.1844 [math.CO] (2009).
Zoe M. Himwich and Noah A. Rosenberg, Roadblocked monotonic paths and the enumeration of coalescent histories for non-matching caterpillar gene trees and species trees, arXiv:1901.04465 [qbio.PE], 2019; Adv. Appl. Math. 113 (2020), 101939.

Equals twice A006079. Also A000108 minus A001405.

Table[Binomial[2 n, n]/(n + 1) - Binomial[n, Floor[n/2]], {n, 0, 30}]

a(n) = binomial(2*n, n)/(n+1) - binomial(n, n\2); \\ Michel Marcus, Jan 22 2020

a(n) = (2n)! / (n! (n+1))! - n! / ( (floor(n/2))! (ceiling(n/2))! ).

cp's OEIS Frontend

A007123 Number of connected unit interval graphs with n nodes; also number of bracelets (turnover necklaces) with n black beads and n-1 white beads.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A006082 Number of labeled projective plane trees (or "flat" trees) with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A006080 Number of rooted projective plane trees with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A306292 Number of asymmetric Dyck paths of semilength n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula