Martin Klazar - cp's OEIS frontend

A081054 Crossing matchings: linear chord diagrams with 2n nodes and n arcs in which each arc crosses another arc.

1, 0, 1, 4, 31, 288, 3272, 43580, 666143, 11491696, 220875237, 4681264432, 108475235444, 2728591657920, 74051386322580, 2156865088819692, 67113404608820943, 2221948578439255200, 77990056655776149179

Offset: 0

Martin Klazar, Apr 15 2003

			The 4 crossing matchings on nodes 1, 2, ..., 6 are {13, 25, 46}, {14, 25, 36}, {15, 24, 36} and {14, 26, 35}.

Olivia Beckwith, Victor Luo, Stephen J. Miller, Karen Shen, Nicholas Triantafillou, Distribution of Eigenvalues of Weighted, Structured Matrix Ensembles, arXiv:1112.3719 [math.PR], 2011-2012.
Olivia Beckwith, Victor Luo, Stephen J. Miller, Karen Shen, Nicholas Triantafillou, Distribution of Eigenvalues of Weighted, Structured Matrix Ensembles, Electronic Journal of Combinatorial Number Theory, Volume 15 (2015) #A21.
M. Klazar, Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings, Advances in Appl. Math., Vol. 30 (2003), pp. 126-136.
Alexander Stoimenow, On enumeration of chord diagrams and asymptotics of Vassiliev invariants, Dissertation, Mathematik und Informatik, University of Berlin, 1998; see chapter 3.

Cf. A000699, A004300.

a[n_] := a[n]=Module[{x, y, z, i}, y=Sum[a[i]x^i, {i, 0, n-1}]+z*x^n+O[x]^(n+1); Solve[D[y, x]==(-1+y-x^2y^3)/(2x^2y(1+x*y)), z][[1, 1, 2]]]

The g.f. (a formal power series) F = 1 + x^2 + 4*x^3 + ... satisfies the differential equation F' = (-x^2*F^3 + F - 1)/(2*x^3*F^2 + 2*x^2*F).

a(n) is asymptotic to (2n)!/(e 2^n n!). In other words, the probability that a random matching is a crossing matching is asymptotic to 1/e; see Lemma 3.12 of Stoimenow reference. - Benoit Cloitre, Apr 18 2003; corrected by Dean Hickerson, Apr 21 2003

A008910 Join 2n points on a line with n arcs above the line; form graph with the arcs as nodes, joining 2 nodes when the arcs cross. a(n) is the number of cases in which the graph is symmetric about middle and has no isolated nodes.

Original entry on oeis.org

0, 1, 2, 9, 26, 122, 466, 2299, 10316, 54179

Offset: 1

klazar(AT)kam.mff.cuni.cz (Martin Klazar)

nonn

A007860 Maximal matchings in rooted plane trees on n nodes.

Original entry on oeis.org

1, 1, 4, 12, 44, 175, 718, 3052, 13308, 59139, 266974, 1220879, 5643562, 26327769, 123793450, 586078393, 2791408028, 13365916545, 64302770488, 310672722803, 1506737267266, 7332920012492, 35800278685252, 175286440178448, 860517328379634, 4234766396436095

Offset: 1

Martin Klazar (klazar(AT)kam.mff.cuni.cz)

nonn

M. Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
Index entries for sequences related to rooted trees

G.f. f(x) satisfies f(x)^7 - (6+x) * f(x)^6 + (15+6*x) * f(x)^5 + (x^2-15*x-20) * f(x)^4 - (2*x^2-20*x-15) * f(x)^3 - (15*x+6) * f(x)^2 + (2*x^2+6*x+1) * f(x) + x^4 - x^2 - x = 0 [from Klazar]. - Sean A. Irvine, Feb 07 2018

a(1) corrected and more terms from Sean A. Irvine, Feb 07 2018

A007859 Number of matchings in rooted plane trees on n nodes.

Original entry on oeis.org

0, 1, 4, 18, 84, 405, 2002, 10101, 51844, 269994, 1423784, 7590044, 40846390, 221650195, 1211606190

Offset: 1

Martin Klazar

M. Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
Index entries for sequences related to rooted trees

A007855 Infima closed sets in rooted plane trees on n nodes.

Original entry on oeis.org

1, 3, 13, 63, 326, 1769, 9964, 57843, 344203, 2090470, 12912988, 80899801, 512896540, 3284651548, 21217493460, 138080484819, 904454380446, 5958186674879, 39448465279220, 262359379484522, 1751912981641794, 11741044418866476

Offset: 1

Martin Klazar

nonn

M. Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
Index entries for sequences related to rooted trees

my(x='x+O('x^30)); Vec((1/4) * (1+sqrt(1-4*x)) * (1-sqrt(3-2/sqrt(1-4*x)))) \\ Michel Marcus, Apr 05 2019

G.f.: (1/4) * (1 + sqrt(1-4*x)) * (1 - sqrt(3 - 2 / sqrt(1-4*x))) [from Klazar]. - Sean A. Irvine, Feb 06 2018

More terms from Sean A. Irvine, Feb 06 2018

A007856 Subtrees in rooted plane trees on n nodes.

Original entry on oeis.org

1, 3, 12, 52, 236, 1109, 5366, 26639, 135300, 701269, 3700400, 19834973, 107784622, 592705377, 3292970302, 18458954896, 104276682820, 593056996445, 3392898090908, 19512100041995, 112729617387020, 653965783541960, 3807766434556940

Offset: 1

Martin Klazar

nonn

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
G.-S. Cheon, H. Kim, L. W. Shapiro, Mutation effects in ordered trees, arXiv preprint arXiv:1410.1249 [math.CO], 2014.
M. Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
Index entries for sequences related to rooted trees

Rest[CoefficientList[Series[(1/8) (1 + 1/Sqrt[1 - 4  x]) (1 + Sqrt[1 - 4  x] - Sqrt[2]  Sqrt[1 - 10  x + Sqrt[1 - 4  x]]), {x, 0, 33}], x]] (* Vincenzo Librandi, Feb 07 2018 *)
A007856[n_] := ((n-1)/2) CatalanNumber[n-1](1 - Hypergeometric2F1[-1/2, - n, n-1, -4]); Table[A007856[n], {n, 1, 23}] (* Peter Luschny, Aug 04 2019 *)

G.f.: (1/8) * (1 + 1/sqrt(1-4*x)) * (1 + sqrt(1-4*x) - sqrt(2) * sqrt(1 - 10*x + sqrt(1-4*x))), see Klazar's paper. - Sean A. Irvine, Feb 06 2018

a(n) = ((n - 1)/2)*CatalanNumber(n-1)*(1 - hypergeom([-1/2, -n], [n - 1], -4)). - Peter Luschny, Aug 04 2019

More terms from Sean A. Irvine, Feb 06 2018

A007853 Number of maximal antichains in rooted plane trees on n nodes.

Original entry on oeis.org

1, 2, 5, 15, 50, 178, 663, 2553, 10086, 40669, 166752, 693331, 2917088, 12398545, 53164201, 229729439, 999460624, 4374546305, 19250233408, 85120272755, 378021050306, 1685406494673, 7541226435054, 33852474532769, 152415463629568, 688099122024944

Offset: 1

Martin Klazar

nonn

Also the number of initial subtrees (emanating from the root) of rooted plane trees on n vertices, where we require that an initial subtree contains either all or none of the branchings under any given node. The leaves of such a subtree comprise the roots of a corresponding antichain cover. Also, in the (non-commutative) multicategory of free pure multifunctions with one atom, a(n) is the number of composable pairs whose composite has n positions. - Gus Wiseman, Aug 13 2018

The g.f. is denoted by y_2 in Bacher 2004 Proposition 7.5 on page 20. - Michael Somos, Nov 07 2019

			G.f. = x + 2*x^2 + 5*x^3 + 15*x^4 + 50*x^5 + 178*x^6 + 663*x^7 + 2553*x^8 + ... - _Michael Somos_, Nov 07 2019

R. Bacher, On generating series of complementary plane trees arXiv:math/0409050 [math.CO], 2004.
M. Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
Index entries for sequences related to rooted trees

Cf. A000081, A000108, A001003, A001006, A126120, A213705, A317713, A318046, A318048, A318049.

ie[t_]:=If[Length[t]==0,1,1+Product[ie[b],{b,t}]];
allplane[n_]:=If[n==1,{{}},Join@@Function[c,Tuples[allplane/@c]]/@Join@@Permutations/@IntegerPartitions[n-1]];
Table[Sum[ie[t],{t,allplane[n]}],{n,9}] (* Gus Wiseman, Aug 13 2018 *)

a(n):=1/(n+1)*binomial(2*n,n)+sum((k+2)/(n+1)*binomial(2*n-k-1,n-k-1)*(sum(((binomial(2*i,i))*(binomial(k+i,3*i)))/(i+1),i,0,floor(k/2))),k,0,n-1); /* Vladimir Kruchinin, Apr 05 2019 */

{a(n) = my(A); if( n<0, 0, A = sqrt(1 - 4*x + x * O(x^n)); polcoeff( (3 - 2*x - A - sqrt(2 - 16*x + 4*x^2 + (2 + 4*x) * A)) / 4, n))}; /* Michael Somos, Nov 07 2019 */

G.f.: (1/4) * (3 - 2*x - sqrt(1-4*x) - sqrt(2) * sqrt((1+2*x) * sqrt(1-4*x) + 1 - 8*x + 2*x^2)) [from Klazar]. - Sean A. Irvine, Feb 06 2018
a(n) = (1/(n+1))*C(2*n,n) + Sum_{k=0..n-1} ((k+2)/(n+1))*C(2*n-k-1,n-k-1)*Sum_{i=0..floor(k/2)} C(2*i,i)*C(k+i,3*i)/(i+1). - Vladimir Kruchinin, Apr 05 2019
Given the g.f. A(x) and the g.f. of A213705 B(x), then -x = A(-B(x)). - Michael Somos, Nov 07 2019

More terms from Sean A. Irvine, Feb 06 2018

A008909 Join 2n points on a line with n arcs above the line; form graph with the arcs as nodes, joining 2 nodes when the arcs cross. a(n) is the number of cases in which the graph is a path.

Original entry on oeis.org

1, 1, 3, 8, 21, 56, 153, 428, 1222, 3549, 10454, 31159, 93801, 284788, 871007, 2681018, 8298932, 25817395, 80674901, 253106836, 796968055, 2517706036, 7977573202, 25347126629, 80738862084, 257778971503, 824798533932, 2644335308021, 8493626448823

Offset: 1

Martin Klazar

nonn

a(n+1) is the number of (finite) positive integer sequences b(1),...,b(k) with b(1) + Sum_{i=1..k-1} (1+max{b(i+1)-b(i), 0}) <= n. - Klaus Strassburger. [E.g., a(4)=8 since the integer sequences are 1; 2; 3; 1,1; 1,2; 2,1; 2,2; 1,1,1.]

G.f. (conjecture): 1 - G(0)/(1-x), where G(k)= 1 - 1/(1 - x/(1 - x/(1 - x/(1 - x/(x - 1/G(k+1)))))); (continued fraction). - Sergei N. Gladkovskii, Jul 12 2013

G.f. (conjecture): (2*x^3-x^2+2*x-1+sqrt(x^4+2*x^2-4*x+1))/(2*x^2-2*x). - Michael D. Weiner, Dec 17 2019

More terms from Klaus Strassburger (strass(AT)ddfi.uni-duesseldorf.de), Sep 24 2001

More terms from Sean A. Irvine, Apr 10 2018

A007857 Number of independent sets in rooted plane trees on n nodes.

Original entry on oeis.org

1, 2, 8, 37, 184, 959, 5172, 28641, 162008, 932503, 5445934, 32197334, 192357788, 1159603592, 7045356104, 43098733353, 265240985112, 1641100253735, 10202295895890, 63696629668980, 399216722146770, 2510833297584165

Offset: 1

Martin Klazar

nonn

Equals the main diagonal of square array A130523. - Paul D. Hanna, Jun 06 2007
From Petros Hadjicostas, Aug 06 2020: (Start)
To prove R. J. Mathar's conjecture, let b(n) = A007226(n-1) = (2*/n)*binomial(3*(n-1), n-1) and c(n) = A000108(n-1) = binomial(2*(n-1), n-1)/n. Since a(n) = b(n) - c(n), it is enough to prove that each of the sequences (b(n): n >= 1) and (c(n): n >= 1) satisfies the same recurrence as (a(n): n >= 1).
For simplicity, denote the recurrence by f(n,0)*a(n) + f(n,1)*a(n-1) + f(n,2)*a(n-2) + f(n,3)*a(n-3) = 0. Let g(n) = 2*n*(2*n - 3)/(3*(3*n - 4)*(3*n - 5)) and h(n) = n/(2*(2*n - 3)). Then we can easily show that b(n-i) = b(n)* Product_{j=0..i-1} g(n-j) and c(n-i) = c(n)*Product_{j=0..i-1} h(n-j) for i >= 1.
Using a CAS (e.g. PARI), one can show that f(n,0) + f(n,1)*g(n) + f(n,2)*g(n)*g(n-1) + f(n,3)*g(n)*g(n-1)*g(n-2) = 0. Multiplying both sides by b(n), we get f(n,0)*b(n) + f(n,1)*b(n-1) + f(n,2)*b(n-2) + f(n,3)*b(n-3) = 0.
Again, using a CAS, one can show that f(n,0) + f(n,1)*h(n) + f(n,2)*h(n)*h(n-1) + f(n,3)*h(n)*h(n-1)*h(n-2) = 0. Multiplying both sides by c(n), we get f(n,0)*c(n) + f(n,1)*c(n-1) + f(n,2)*c(n-2) + f(n,3)*c(n-3) = 0. (End)

M. Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics, 18(2) (1997), 195-210.
M. Klazar, Addendum Twelve Countings with Rooted Plane Trees, European Journal of Combinatorics, 18(6) (1997), 739-740.
Index entries for sequences related to rooted trees

Cf. A000108, A001764, A007226, A130523.

{a(n)=my(A000108, A001764); A000108=Ser(vector(n+1, r, binomial(2*r-2, r-1)/r)); A001764=Ser(vector(n+1, r, binomial(3*r-3, r-1)/(2*r-1))); polcoeff(x/(1-x*A000108*A001764-x*A001764^2 +x*O(x^n)), n)} \\ Paul D. Hanna, Jun 06 2007

a(n+1) = (2/(n+1))*C(3*n, n) - (1/(n+1))*C(2*n, n) = A007226(n) - A000108(n). - Paul Barry, Nov 05 2006
G.f.: A(x) = x/(1 - x*C(x)*F(x) - x*F(x)^2), where C(x) is g.f. of the Catalan numbers (A000108) (i.e., C(x) = 1 + x*C(x)^2) and F(x) is the g.f. of ternary numbers (A001764) (i.e., F(x) = 1 + x*F(x)^3). - Paul D. Hanna, Jun 06 2007
Conjecture: 2*n*(n - 1)*(2*n - 3)*(44*n - 69)*a(n) + (n - 1)*(176*n^3 - 9591*n^2 + 38703*n - 40640)*a(n-1) + (-17479*n^4 + 218005*n^3 - 959616*n^2 + 1797890*n - 1221920)*a(n-2) + 6*(3*n - 10)*(2*n - 7)*(3*n - 11)*(517*n - 1198)*a(n-3) = 0 for n >= 4. - R. J. Mathar, Nov 26 2012

More terms from Paul Barry, Nov 05 2006

A007858 G.f. is 1 - 1/f(x), where f(x) = 1+x+3x^2+9x^3+32*x^4+... is 1/x times g.f. for A063020.

Original entry on oeis.org

1, 2, 4, 13, 44, 164, 636, 2559, 10556, 44440, 190112, 824135, 3612244, 15981632, 71277736, 320121747, 1446537564, 6571858168, 30000766128, 137544893940, 633051803120, 2923867281660, 13547594977500, 62955434735505, 293336372858724, 1370149533359784, 6414423856436816

Offset: 1

Martin Klazar, Mar 15 1996

nonn

Number of maximal independent sets in rooted plane trees on n nodes. - Olivier Gérard, Jul 05 2001

G. C. Greubel, Table of n, a(n) for n = 1..1000
Martin Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
A. Mironov and A. Morozov, Algebra of quantum C-polynomials, arXiv:2009.11641 [hep-th], 2020.
Index entries for sequences related to rooted trees

Cf. A000108.

series(1-x/RootOf(Z-_Z^2-_Z^3+_Z^4-x), x=0,20); # _Mark van Hoeij, May 28 2013

Rest[CoefficientList[1-x/InverseSeries[Series[x-x^2-x^3+x^4, {x, 0, 20}], x],x]] (* Vaclav Kotesovec, Nov 14 2014 *)
Table[Sum[Binomial[n + k, k]/(n + k)*Sum[(Binomial[j, n - k - j + 1]*Binomial[k, j]*(-1)^(n + k - j + 1)), {j, 0, k}], {k, 1, n}] + CatalanNumber[n], {n, 0, 50}] (* G. C. Greubel, Feb 15 2017 *)

a(n):=sum(binomial(n+k,k)/(n+k)*sum(binomial(j,n-k-j+1)*binomial(k,j)*(-1)^(n+k-j+1),j,0,k),k,1,n)+1/(n+1)*binomial(2*n,n); /* Vladimir Kruchinin, Nov 13 2014 */

my(x='x+O('x^66)); Vec(1-x/serreverse(x-x^2-x^3+x^4)) \\ Joerg Arndt, May 28 2013

a(n+1) = Sum_{k = 1..n} ( binomial(n+k,k)/(n+k)*Sum_{j = 0..k} ( binomial(j,n-k-j+1)*binomial(k,j)*(-1)^(n+k-j+1) ) ) + C(n), where C(n) is a Catalan number. - Vladimir Kruchinin, Nov 13 2014
Recurrence: 16*(n-1)*n*(2*n-3)*(17*n^2 - 81*n + 96)*a(n) = (n-1)*(1819*n^4 - 14124*n^3 + 40377*n^2 - 50320*n + 23040)*a(n-1) + 8*(2*n-5)*(4*n-11)*(4*n-9)*(17*n^2 - 47*n + 32)*a(n-2). - Vaclav Kotesovec, Nov 14 2014
Asymptotics (Klazar, 1997): a(n) ~ sqrt(5731-4635/sqrt(17)) * ((107+51*sqrt(17))/64)^n / (256 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Nov 14 2014

cp's OEIS Frontend

User: Martin Klazar

A081054 Crossing matchings: linear chord diagrams with 2n nodes and n arcs in which each arc crosses another arc.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A008910 Join 2n points on a line with n arcs above the line; form graph with the arcs as nodes, joining 2 nodes when the arcs cross. a(n) is the number of cases in which the graph is symmetric about middle and has no isolated nodes.

Views

Author

Keywords

A007860 Maximal matchings in rooted plane trees on n nodes.

Views

Author

Keywords

Links

Formula

Extensions

A007859 Number of matchings in rooted plane trees on n nodes.

Views

Author

Keywords

Links

A007855 Infima closed sets in rooted plane trees on n nodes.

Views

Author

Keywords

Links

Programs

PARI

Formula

Extensions

A007856 Subtrees in rooted plane trees on n nodes.

Views

Author

Keywords

Links

Programs

Mathematica

Formula

Extensions

A007853 Number of maximal antichains in rooted plane trees on n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

Extensions

A008909 Join 2n points on a line with n arcs above the line; form graph with the arcs as nodes, joining 2 nodes when the arcs cross. a(n) is the number of cases in which the graph is a path.

Views

Author

Keywords

Comments

Formula

Extensions

A007857 Number of independent sets in rooted plane trees on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A007858 G.f. is 1 - 1/f(x), where f(x) = 1+x+3*x^2+9*x^3+32*x^4+... is 1/x times g.f. for A063020.

Views

A007858 G.f. is 1 - 1/f(x), where f(x) = 1+x+3x^2+9x^3+32*x^4+... is 1/x times g.f. for A063020.