A070031 -id:A070031 - cp's OEIS frontend

A228180 The number of single edges on the boundary of ordered trees with n edges.

0, 1, 2, 6, 19, 61, 199, 661, 2234, 7668, 26674, 93858, 333524, 1195288, 4315468, 15681838, 57312643, 210529213, 776872243, 2878482523, 10704933793, 39945106573, 149511432793, 561182969173, 2111812422871, 7965992783803, 30114859723751, 114079902339303, 432975153092011, 1646215731143667

Offset: 0

Louis Shapiro, Aug 20 2013

nonn

Apparently the partial sums of A070031. - R. J. Mathar, Aug 25 2013

			For n=3 the UUUDDD has 3 single edges while UUDDUD, UDUUDD and UUDUDD each have one single edge, i.e., an edge with no siblings.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, and Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8; preprint, 2014.
W. Kuszmaul, Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations, arXiv preprint arXiv:1509.08216 [cs.DM], 2015-2017.

Cf. A000108, A228178.

CoefficientList[Series[(x*(1-Sqrt[1-4*x])/(2*x) + 2*x^3*((1-Sqrt[1-4*x])/(2*x))^4)/(1-x), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 01 2014 *)

x = 'x + O('x^66);
C = serreverse( x/( 1/(1-x) ) ) / x; \\ Catalan A000108
gf = (x*C+2*x^3*C^4)/(1-x);
concat([0], Vec(gf) ) \\ Joerg Arndt, Aug 21 2013

G.f.: (x*C+2*x^3*C^4)/(1-x) where C is the g.f. for the Catalan numbers A000108.
Conjecture: 2*(n+1)*a(n) +(-13*n+5)*a(n-1) +(23*n-37)*a(n-2) +6*(-2*n+5)*a(n-3)=0. - R. J. Mathar, Aug 25 2013
a(n) ~ 5*4^n / (3*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Feb 01 2014

A306423 Number of coalescent histories for pseudocaterpillar gene trees G and caterpillar species trees S.

Original entry on oeis.org

3, 11, 37, 124, 420, 1441, 5005, 17576, 62322, 222870, 802978, 2912168, 10623470, 38956365, 143521725, 530985360, 1971965490, 7348812570, 27472909590, 103002205800, 387205269360, 1459146890058, 5511120747282, 20858962792624, 79103096214100

Offset: 4

Noah A Rosenberg, Feb 14 2019

nonn

Consider a binary, rooted, leaf-labeled caterpillar species tree G = (...((((A_1, A_2), A_3), A_4), A_5),..., A_n) and a binary, rooted, leaf-labeled pseudocaterpillar gene tree (...(((A_1, A_2), (A_3, A_4)), A_5),..., A_n). The pseudocaterpillar family of trees is defined for n>=5 leaves (Rosenberg 2007). Sequence a(n) gives the number of coalescent histories for (G,S).

A slightly different definition of pseudocaterpillar trees applies for n=4 and adds term a(4)=3 to a (see Table 4 of Alimpiev & Rosenberg 2021). - Noah A Rosenberg, Feb 10 2025

			For n=5, consider species tree ((((A_1, A_2), A_3), A_4), A_5) and gene tree ((((A_1, A_2), (A_3, A_4)), A_5). Label the nodes of the species tree 1, 2, 3, 4, from the cherry to the root, identifying each node with its immediate ancestral edge. Annotate the coalescent histories by vectors whose entries, in order, denote the locations of the coalescences of (A_1, A_2), (A_3, A_4), ((A_1, A_2), (A_3, A_4)), and ((((A_1, A_2), (A_3, A_4)), A_5). The a(5)=11 coalescent histories are (1,3,3,4), (1,3,4,4), (1,4,4,4), (2,3,3,4), (2,3,4,4), (2,4,4,4), (3,3,3,4), (3,3,4,4), (3,4,4,4), (4,3,4,4), and (4,4,4,4).

E. Alimpiev and N. A. Rosenberg, Enumeration of coalescent histories for caterpillar species trees and p-pseudocaterpillar gene trees, Adv. Appl. Math. 131 (2021), 102265.
N. A. Rosenberg and J. H. Degnan, Coalescent histories for discordant gene trees and species trees. Theor. Pop. Biol. 77 (2010), 145-151.

A000108 gives the number of coalescent histories for matching caterpillar gene trees and species trees. A070031 gives the number of coalescent histories for matching pseudocaterpillar gene trees and species trees.

List([5..30], n-> (19*n-40)*(n-3)*Binomial(2*n-2, n-1)/(4*n*(2*n-3)*(2*n-5))); # G. C. Greubel, Mar 07 2019

[(19*n-40)*(n-3)*Binomial(2*n-2, n-1)/(4*n*(2*n-3)*(2*n-5)): n in [5..30]]; // G. C. Greubel, Mar 07 2019

Table[(19n-40)(n-3) Binomial[2n-2, n-1]/(4n(2n-3)(2n-5)), {n, 5, 30}]

{a(n)=(19*n-40)*(n-3)*binomial(2*n-2, n-1)/(4*n*(2*n-3)*(2*n-5))};
for(n=5,30, print1(a(n), ", ")) \\ G. C. Greubel, Mar 07 2019

[(19*n-40)*(n-3)*binomial(2*n-2, n-1)/(4*n*(2*n-3)*(2*n-5)) for n in (5..30)] # G. C. Greubel, Mar 07 2019

a(n) = (19*n-40)*(n-3)*(2*n-2)!/(4*n!*(n-1)!*(2*n-3)*(2*n-5)).
a(n) = (19*n-40)*(n-3)*C(n-1)/((2*n-3)*(2*n-5)), where C(n) is the Catalan numbers A000108.
G.f.: ((2 - 7*x + x^2) +(-2 + 3*x + x^2)*sqrt(1-4*x))/2. - G. C. Greubel, Mar 07 2019
D-finite with recurrence: +2*n*a(n) +(-11*n+18)*a(n-1) +(11*n-38)*a(n-2) +2*(2*n-11)*a(n-3)=0. - R. J. Mathar, Jan 27 2020
a(n) ~ 19 * 2^(2*n - 6) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jun 15 2022

a(4)=3 prepended by Noah A Rosenberg, Feb 10 2025

A165996 Triangle read by rows: T(n,0) = (n+1)^2, T(n,k) = T(n,k-1) + T(n-1,k) for 0 < k < n, and T(n,n) = T(n,n-1).

Original entry on oeis.org

1, 4, 4, 9, 13, 13, 16, 29, 42, 42, 25, 54, 96, 138, 138, 36, 90, 186, 324, 462, 462, 49, 139, 325, 649, 1111, 1573, 1573, 64, 203, 528, 1177, 2288, 3861, 5434, 5434, 81, 284, 812, 1989, 4277, 8138, 13572, 19006, 19006, 100, 384, 1196, 3185, 7462, 15600

Offset: 0

Gerald McGarvey, Oct 03 2009

A070031 (main diagonal), A071736 (is 1, 3, then diagonal T(n, n-2))

s=10;M=matrix(s,s);for(n=1,s,M[n,1]=n^2); for(n=2,s,for(k=2,n,M[n,k]=M[n,k-1]+M[n-1,k])); for(n=1,s,for(k=1,n,print1(M[n,k],", ")))

A355044 Number of coalescent histories for matching gene trees and species trees with n leaves and a 5-leaf seed tree.

Original entry on oeis.org

10, 37, 130, 453, 1584, 5577, 19786, 70720, 254524, 921842, 3357908, 12294995, 45229500, 167093505, 619689690, 2306312580, 8611143420, 32246815350, 121085968380, 455817192090, 1719872196432, 6503354706762, 24640476660420, 93534587913648, 355675196682904

Offset: 5

Noah A Rosenberg, Jun 16 2022

nonn

a(n) is the number of coalescent histories for matching gene tree G and species tree S, where G and S are identically labeled and have shape (...((((A_1,A_2),A_3),(A_4,A_5)),.),.),...), with n leaves.

N. A. Rosenberg, Coalescent histories for caterpillar-like families, IEEE/ACM Trans. Comp. Biol. Bioinformat. 10 (2013), 1253-1262.

Cf. A000108, A070031 (for the same computation with a 4-leaf seed tree).

a(n) = ((23*n^2-131*n+180)/(4*(2n-3)*(2n-5)))*(2n-2)!/((n-1)!*n!).

a(n) = ((23*n^2-131*n+180)/(4*(2n-3)*(2n-5)))*A000108(n-1).

cp's OEIS Frontend

A228180 The number of single edges on the boundary of ordered trees with n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A306423 Number of coalescent histories for pseudocaterpillar gene trees G and caterpillar species trees S.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

Extensions

A165996 Triangle read by rows: T(n,0) = (n+1)^2, T(n,k) = T(n,k-1) + T(n-1,k) for 0 < k < n, and T(n,n) = T(n,n-1).

Views

Author

Keywords

Crossrefs

Programs

PARI

A355044 Number of coalescent histories for matching gene trees and species trees with n leaves and a 5-leaf seed tree.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula