A185100 -id:A185100 - cp's OEIS frontend

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

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

A175954 Unlabeled (cyclic) Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n unlabeled points equally spaced on a circle, up to rotations of the circle.

Original entry on oeis.org

1, 1, 2, 2, 4, 5, 12, 19, 46, 95, 230, 528, 1320, 3219, 8172, 20714, 53478, 138635, 363486, 957858, 2543476, 6788019, 18218772, 49120019, 133036406, 361736109, 987316658, 2703991820, 7429445752, 20473889133, 56579632732, 156766505691

Offset: 0

Max Alekseyev, Oct 29 2010

nonn

Unlabeled version of A001006.

The number of such chord configurations on 2n vertices with n chords is given by A002995(n+1).

Andrew Howroyd, Table of n, a(n) for n = 0..200
Andrew Howroyd, Chord Configuration Symmetries

Cf. A001006, A185100, A002426, A002995.

a1006[0] = 1; a1006[n_Integer] := a1006[n] = a1006[n-1] + Sum[a1006[k]* a1006[n -2-k], {k, 0, n-2}];
a142150[n_] := n*(1 + (-1)^n)/4;
a2426[n_] := Coefficient[(1 + x + x^2)^n, x, n];
a[0] = 1; a[n_] := (1/n)*(a1006[n]+a142150[n]*a1006[n/2-1] + Sum[EulerPhi[ n/d]*a2426[d], {d, Most @ Divisors[n]}]);
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Jul 02 2018, after Andrew Howroyd *)

For odd prime p, a(p) = (A001006(p) - 1)/p + 1.

a(n) = (1/n) * (A001006(n) + A142150(n) * A001006(n/2-1) + Sum{d|n, dA002426(d)). - Andrew Howroyd, Apr 01 2017

A303875 Number of noncrossing partitions of an n-set up to rotation and reflection with all blocks having a prime number of elements.

Original entry on oeis.org

1, 0, 1, 1, 1, 2, 3, 5, 7, 14, 26, 49, 107, 215, 502, 1112, 2619, 6220, 14807, 36396, 88397, 219920, 545196, 1364669, 3434436, 8658463, 21989434, 55893852, 142823174, 365766327, 939575265, 2420885031, 6250344302, 16183450744, 41981605437, 109155492638

Offset: 0

Andrew Howroyd, May 01 2018

nonn

The number of such noncrossing partitions counted distinctly is given by A210737.

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

Cf. A111275, A185100 (1 or 2), A210737, A303874, A303931.

\\ number of partitions with restricted block sizes
NCPartitionsModDihedral(v)={ my(n=#v);
my(p=serreverse( x/(1 + sum(k=1, #v, x^k*v[k])) + O(x^2*x^n) )/x);
my(vars=variables(p));
my(varpow(r,d)=substvec(r + O(x^(n\d+1)), vars, apply(t->t^d, vars)));
my(q=x*deriv(p)/p, h=varpow(p,2));
my(R=sum(i=0, (#v-1)\2, v[2*i+1]*x*(x^2*h)^i), Q=sum(i=1, #v\2, v[2*i]*(x^2*h)^i), T=sum(k=1, #v, my(t=v[k]); if(t, x^k*t*sumdiv(k, d, eulerphi(d) * varpow(p,d)^(k/d))/k)));
(T + 2 + intformal(sum(d=1, n, eulerphi(d)*varpow(q,d))/x) - p + (1 + Q + (1+R)^2*h/(1-Q))/2)/2 + O(x*x^n)
}
Vec(NCPartitionsModDihedral(vector(40,k,isprime(k))))

A378941 Number of Motzkin paths of length n up to reversal.

Original entry on oeis.org

1, 1, 2, 3, 7, 13, 32, 70, 179, 435, 1142, 2947, 7889, 21051, 57192, 155661, 427795, 1179451, 3271214, 9102665, 25434661, 71282431, 200406472, 564905068, 1596435581, 4521772933, 12835116530, 36504093693, 104012240063, 296871993373, 848694481664, 2429882584254, 6966789756243

Offset: 0

Andrew Howroyd, Dec 17 2024

nonn

A Motzkin path of length n is a path from (0,0) to (n,0) using only steps U = (1,1), H = (1,0) and D = (1,-1). This sequence considers a path and its reversal to be the same. The number of symmetric paths of length 2n (and also 2n+1) is given by A005773(n+1).

a(n) + 1 is an upper bound on the order of the linear recurrence of column n-1 of A287151. At least for columns up to 7, this bound gives the actual order of the recurrence. For example, a(5) = 13 and the order of the recurrence of column 4 (=A059524) is 14.

			The Motzkin paths for a(1)..a(5) are:
a(1) = 1: H;
a(2) = 2: HH, UD;
a(3) = 3: HHH, UHD, HUD=UDH;
a(4) = 7: HHHH, HUDH, UHHD, UUDD, UDUD, HHUD=UDHH, HUHD=UHDH.
a(5) = 13: HHHHH, HUHDH, UHHHD, UUHDD, UDHUD, HHHUD=UDHHH, HHUHD=UHDHH, HHUDH=HUDHH, HUHHD=UHHDH, HUUDD=UUDDH, HUDUD=UDUDH, UHUDD=UUHDD, UHDUD=UPUHD.

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

Cf. A001006, A005773, A007123 (similar for Dyck paths), A175954, A185100, A287151, A292357.

Vec(-3/(4*x)-(1+sqrt(1-2*x-3*x^2+O(x^40)))/(4*x^2)+(1+x)/(-1+3*x^2+sqrt(1-2*x^2-3*x^4+O(x^40)))) \\ Thomas Scheuerle, Dec 18 2024

a(n) = (A001006(n) + A005773(floor(1 + n/2))) / 2.

cp's OEIS Frontend

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

A175954 Unlabeled (cyclic) Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n unlabeled points equally spaced on a circle, up to rotations of the circle.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A303875 Number of noncrossing partitions of an n-set up to rotation and reflection with all blocks having a prime number of elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A378941 Number of Motzkin paths of length n up to reversal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula