Mathilde Bouvel - cp's OEIS frontend

A373456 Number of tree interval posets of permutations of size n, considered up to isomorphism.

1, 1, 1, 3, 6, 14, 32, 79, 192, 488, 1244, 3240, 8497, 22561, 60309, 162541, 440598, 1201377, 3291426, 9058464, 25027797, 69401101, 193071153, 538724060, 1507288378, 4227824974, 11886150870, 33488522111, 94539554742, 267383598840, 757539956852, 2149698586706, 6109515731611

Offset: 1

Mathilde Bouvel, Jun 06 2024

nonn

See Remark 24 in [Bouvel-Cioni-Izart].

Bridget E. Tenner. Interval Posets of Permutations. Order, 39(3):523-536, 2022.

Mathilde Bouvel, Lapo Cioni, and Benjamin Izart, The interval posets of permutations seen from the decomposition tree perspective, arXiv:2110.10000 [math.CO], 2021-2024.
Bridget E. Tenner, Interval Posets for Permutations, arXiv:2007.06142 [math.CO], 2020-2021.

For the same posets but not considered up to isomorphism, see A054515.

For interval posets that are not necessarily trees, see A373455 (for posets also considered up to isomorphism) and A348479 (otherwise).

Asymptotic behavior of a(n) is c*n^(-3/2)*r^n with c approximately 0.2597 and r approximately 2.9784. See M. Bouvel, L. Cioni, B. Izart (Remark 24).

A373455 Number of interval posets of permutations of size n, considered up to isomorphism.

Original entry on oeis.org

1, 1, 2, 6, 15, 43, 124, 379, 1172, 3730, 12023, 39388, 130377, 436066, 1470271, 4994083, 17069343, 58669677, 202648664, 703064353, 2448871526, 8560428736, 30021944259, 105602286616, 372469127865, 1317027839250, 4667702488376, 16578315095909

Offset: 1

Mathilde Bouvel, Jun 06 2024

nonn

See Remark 21 in [Bouvel-Cioni-Izart].

Bridget E. Tenner. Interval Posets of Permutations. Order, 39(3):523-536, 2022.

Mathilde Bouvel, Lapo Cioni, and Benjamin Izart, The interval posets of permutations seen from the decomposition tree perspective, arXiv:2110.10000 [math.CO], 2021-2024.
Bridget E. Tenner, Interval Posets for Permutations, arXiv:2007.06142 [math.CO], 2020-2021.

For the same posets but not considered up to isomorphism, see A348479.

For the same posets which are in addition trees, see A373456.

Asymptotic behavior of a(n) is c*n^(-3/2)*r^n with c approximately 0.1964 and r approximately 3.7545. See M. Bouvel, L. Cioni, B. Izart (Remark 21).

A348479 Number of interval posets of permutations with n minimal elements.

Original entry on oeis.org

1, 1, 3, 12, 52, 240, 1160, 5795, 29681, 155025, 822563, 4421458, 24025518, 131759106, 728330062, 4053823980, 22699853940, 127790656040, 722835069984, 4106096464006, 23414579166050, 133984343279790, 769124367124594, 4427878983496972, 25559244203741228

Offset: 1

Mathilde Bouvel, Oct 21 2021

nonn

Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, Interval Posets and Polygon Dissections, arXiv:2406.16392 [cs.DM], 2024. See p. 2.
Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, Geometric view of interval poset permutations, arXiv:2411.13193 [math.CO], 2024. See pp. 2, 6.
Mathilde Bouvel, Lapo Cioni, and Benjamin Izart, The interval posets of permutations seen from the decomposition tree perspective, arXiv:2110.10000 [math.CO], 2021.
Bridget Eileen Tenner, Interval posets for permutations, arXiv:2007.06142 [math.CO], 2020-2021.

For interval posets which are in addition trees, see A054515.

Join[{1},Table[Sum[Sum[Binomial[n+i-1,i]Binomial[i,k]Binomial[n-2k-2,i-1],{k,0,Min[i,(n-i-1)/2]}],{i,n-1}]/n,{n,2,25}]] (* Stefano Spezia, Oct 23 2021 *)

a(n) = if (n==1, 1, (1/n) * sum(i=1, n-1, sum(k=0, min(i,(n-i-1)/2), binomial(n+i-1,i)* binomial(i,k)*binomial(n-2*k-2,i-1)))); \\ Michel Marcus, Oct 21 2021

a(n) = (1/n) * Sum_{i=1..(n-1)} Sum_{k=0..Min(i,(n-i-1)/2)} binomial(n+i-1,i)* binomial(i,k)*binomial(n-2k-2,i-1) if n>1. Proved in M. Bouvel, L. Cioni, B. Izart (Theorem 18).
G.f. A(z) = Sum_{n>=0} a(n)*z^n satisfies the equation A(z) = z + (A(z)^2 + A(z)^4)/(1-A(z)). Proved in M. Bouvel, L. Cioni, B. Izart (Equation (1) page 14).
Asymptotic behavior of a(n) is c*n^(-3/2)*r^n with c approximately 0.0622 and r approximately 6.1403. Proved in M. Bouvel, L. Cioni, B. Izart (Theorem 19).
D-finite with recurrence 177*n*(n-1)*(n-2) *(1884*n-6797)*a(n) -(n-1) *(n-2) *(2079652*n^2-10492117*n+10802220) *a(n-1) +6*(n-2) *(98404*n^3-611787*n^2+893503*n+124240) *a(n-2) +2*(-1206916*n^4+13262653*n^3-52943063*n^2+90096428*n-54243072) *a(n-3) +(-16564*n^4+1171171*n^3-12487565*n^2+47878166*n-62441016) *a(n-4) +3 *(3*n-14) *(n-5) *(388*n-1861) *(3*n-16)*a(n-5)=0. - R. J. Mathar, Nov 04 2021

A333005 Number of unrooted level-2 phylogenetic networks with n+1 labeled leaves, when multiple (i.e., parallel) edges are not allowed.

Original entry on oeis.org

1, 6, 135, 5052, 264270, 17765100, 1459311840, 141655066560, 15864853936680, 2013630348265200, 285637924882787400, 44782566595855149600, 7689608275439667376800, 1435181273959520911824000, 289287240571642427530416000, 62630090604946453360419648000

Offset: 1

Mathilde Bouvel, Mar 13 2020

nonn

			a(3) = 135 is the number of unrooted level-2 phylogenetic networks with 4 labeled leaves.

Mathilde Bouvel, Philippe Gambette and Marefatollah Mansouri, Maple worksheet
Mathilde Bouvel, Philippe Gambette and Marefatollah Mansouri, Counting Phylogenetic Networks of level 1 and 2, Version 3, arXiv:1909.10460 [math.CO], 2019.
Sean A. Irvine, Java program (github)

Cf. A328121, A328122, A328123, A328126, A333006.

# (See Links)
# second Maple program:
f:= z-> 1/(1-(3*z^5-16*z^4+32*z^3-30*z^2+12*z)/(4*(1-z)^4)):
a:= n-> n!*coeff(series(RootOf(U=z*f(U), U), z, n+1), z, n):
seq(a(n), n=1..23);  # Alois P. Heinz, Apr 01 2020

nmax = 16;
Module[{U, f, z},
   U[_] = 0;
   f[z_] := 1/(1 - (3*z^5 - 16*z^4 + 32*z^3 - 30*z^2 + 12*z)/(4*(1 - z)^4));
   Do[U[z_] = z*f[U[z]] + O[z]^(nmax+1) // Normal, {nmax}];
   Rest[CoefficientList[U[z], z]*Range[0, nmax]!]] (* Jean-François Alcover, Jan 31 2025 *)

E.g.f. satisfies U(z) = z*f(U(z)) where f(z) = 1 / (1 - (3*z^5-16*z^4+32*z^3-30*z^2+12*z)/(4*(1-z)^4)) [from Bouvel, Gambette, and Mansouri]. - Sean A. Irvine, Apr 01 2020

A333006 Number of rooted level-2 phylogenetic networks with n labeled leaves, when multiple (i.e., parallel) edges are not allowed.

Original entry on oeis.org

1, 18, 1143, 120078, 17643570, 3332111850, 769027554540, 209740414484160, 66001012966991340, 23537700706536311400, 9381525451337593738800, 4132780832455382525556600, 1993954501042287608709284400, 1045675186072945581517653088800

Offset: 1

Mathilde Bouvel, Mar 13 2020

nonn

			a(3) = 1143 is the number of rooted level-2 phylogenetic networks with 3 labeled leaves.

Mathilde Bouvel, Philippe Gambette and Marefatollah Mansouri, Maple worksheet
Mathilde Bouvel, Philippe Gambette and Marefatollah Mansouri, Counting Phylogenetic Networks of level 1 and 2, Version 3, arXiv:1909.10460 [math.CO], 2019.

Cf. A328121, A328122, A328123, A328126, A333005.

# (See Links)
# second Maple program:
f:= z-> 1/(1-(36*z-102*z^2+159*z^3-148*z^4+81*z^5-24*z^6+3*z^7)
         /(4*(1-z)^6)):
a:= n-> n!*coeff(series(RootOf(L=z*f(L), L), z, n+1), z, n):
seq(a(n), n=1..17);  # Alois P. Heinz, Apr 01 2020

E.g.f. satisfies L(z) = z*f(L(z)) where f(z) = 1 / (1 - (36*z-102*z^2+159*z^3-148*z^4+81*z^5-24*z^6+3*z^7)/(4*(1-z)^6)) [from Bouvel, Gambette, and Mansouri]. - Sean A. Irvine, Apr 01 2020

A328126 Number of rooted level-2 phylogenetic networks with n labeled leaves, when multiple (i.e. parallel) edges are allowed.

Original entry on oeis.org

1, 24, 1935, 259098, 48547410, 11693494530, 3442245242940, 1197493950509640, 480665307600153900, 218657025956206794600, 111169169621733787779600, 62469471023839610046855000, 38446561750101105716524609200, 25719207873623040944564642044800, 18581469164514130166868945471102000

Offset: 1

Mathilde Bouvel, Oct 04 2019

nonn

			a(3) = 1935 is the number of rooted level-2 phylogenetic networks with 3 labeled leaves.

Mathilde Bouvel, Philippe Gambette and Marefatollah Mansouri, Maple worksheet
Mathilde Bouvel, Philippe Gambette and Marefatollah Mansouri, Counting Phylogenetic Networks of level 1 and 2, Version 2, arXiv:1909.10460 [math.CO], 2019.

Cf. A328121, A328122, A328123.

Maple
```
# see links section
```

Bouvel, Gambette and Mansouri provide (among other results) a closed formula for a(n), an equation for the associated exponential generating function, and an asymptotic estimate of a(n). See their Section 7.

Name clarified by Mathilde Bouvel, Feb 03 2020

A328123 Number of unrooted level-2 phylogenetic networks with (n+1) labeled leaves, when multiple (i.e. parallel) edges are allowed.

Original entry on oeis.org

1, 9, 282, 14697, 1071750, 100467405, 11509922970, 1558302613245, 243426592473750, 43095781327975425, 8527098853816839450, 1864790504534293823025, 446647359698685492697350, 116281255808439040209815925, 32694665144001284972518220250

Offset: 1

Mathilde Bouvel, Oct 04 2019

nonn

			a(3) = 282 is the number of unrooted level-2 phylogenetic networks with 4 labeled leaves.

Mathilde Bouvel, Philippe Gambette and Marefatollah Mansouri, Maple worksheet
Mathilde Bouvel, Philippe Gambette and Marefatollah Mansouri, Counting Phylogenetic Networks of level 1 and 2, Version 2, arXiv:1909.10460 [math.CO], 2019.

Cf. A328121, A328122, A328126.

Maple
```
# see links section
```

Bouvel, Gambette and Mansouri provide (among other results) a closed formula for a(n), an equation for the associated exponential generating function, and an asymptotic estimate of a(n). See their Section 6.

Name clarified by Mathilde Bouvel, Feb 03 2020

A328122 Number of rooted level-1 phylogenetic networks with n labeled leaves.

Original entry on oeis.org

1, 3, 36, 723, 20280, 730755, 32171580, 1673573895, 100442870640, 6831585584775, 519288366989700, 43626178967384475, 4014060030471090600, 401443860155706643275, 43359414126089609047500, 5030039291029886037279375, 623762332206315636458124000, 82340968923184527676400655375, 11528273478697179256689693556500

Offset: 1

Mathilde Bouvel, Oct 04 2019

nonn

			a(4) = 723 is the number of rooted level-1 phylogenetic networks with 4 labeled leaves.

François Bienvenu, Jean-Jil Duchamps, Michael Fuchs, and Tsan-Cheng Yu, The B_2 index of galled trees, arXiv:2407.19454 [q-bio.PE], 2024. See p. 5.
Mathilde Bouvel, Philippe Gambette and Marefatollah Mansouri, Maple worksheet
Mathilde Bouvel, Philippe Gambette and Marefatollah Mansouri, Counting Phylogenetic Networks of level 1 and 2, arXiv:1909.10460 [math.CO], 2019.

Cf. A328121, A328123, A328126.

Maple
```
# see links section
```

Bouvel, Gambette and Mansouri provide (among other results) a closed formula for a(n), an equation and a closed form for the associated exponential generating function, and an asymptotic estimate of a(n). See their Section 5.

A328121 Number of unrooted level-1 phylogenetic networks (also called galled trees) with (n+1) labeled leaves.

Original entry on oeis.org

1, 2, 15, 192, 3450, 79740, 2252880, 75227040, 2898481320, 126570502800, 6177380517000, 333231084648000, 19687828831070400, 1264341183311606400, 87691200344603856000, 6532556443068591936000, 520205544912884502672000, 44098092640676115673632000, 3964782594938523231457584000

Offset: 1

Mathilde Bouvel, Oct 04 2019

nonn

			a(4) = 192 is the number of unrooted level-1 phylogenetic networks with 5 labeled leaves

Mathilde Bouvel, Philippe Gambette and Marefatollah Mansouri, Maple worksheet
Mathilde Bouvel, Philippe Gambette and Marefatollah Mansouri, Counting Phylogenetic Networks of level 1 and 2, arXiv:1909.10460 [math.CO], 2019.
Charles Semple and Mike Steel, Unicyclic networks: compatibility and enumeration, Transactions on Computational Biology and Bioinformatics (3:1 pp.398--401), 2006.

Cf. A328122, A328123, A328126, A333005, A333006.

Maple
```
# see links section
```

Semple and Steele provide a summation formula for a(n) (see their Theorem 4).

Bouvel, Gambette and Mansouri provide (among other additional results) an equation for the associated exponential generating function, and an asymptotic estimate of a(n). See their Section 4.

A281784 Number of permutations of size n avoiding the three vincular patterns 2-41-3, 3-14-2 and 3-41-2.

Original entry on oeis.org

1, 2, 6, 21, 82, 346, 1547, 7236, 35090, 175268, 897273, 4690392, 24961300, 134917123, 739213795, 4099067786, 22973964976, 129998127216, 741951610676, 4267733183951, 24722711348105, 144147076572858, 845460619537567, 4986014094568416, 29553202933497989, 175988793822561947, 1052569034807964425, 6320797287983675428, 38100643422386086309, 230476496238489596293, 1398812189780917895946, 8516159717810715750712, 51999675864641162206960, 318388601290603235387353, 1954555567303560704554767, 12028490623505389875097231, 74197729371621673254309374, 458706129189543207063584184, 2841808950641424998337843123

Offset: 1

Mathilde Bouvel, Mar 01 2017

a(n) is the number of permutations of size n that are both Baxter and twisted Baxter.

a(n) is also the number of excursions in the positive quarter-plane, using n steps, and with step (multi-)set {(-1,0),(0,-1),(1,-1),(1,0),(0,1),(0,0),(0,0)}.

			For n=4, there are a(4)=21 permutations that avoid 2-41-3, 3-14-2 and 3-41-2 (all permutations of size 4 except 2413, 3142 and 3412).

Vaclav Kotesovec, Table of n, a(n) for n = 1..1000
A. Bostan, K. Raschel, B. Salvy, Non D-finite excursions in the quarter plane, J. Comb. Theory A, 121:45-63, 2014.
Mathilde Bouvel, Veronica Guerrini, Andrew Rechnitzer and Simone Rinaldi, Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence. Arxiv preprint, 2017.
Arturo Merino and Torsten Mütze, Combinatorial generation via permutation languages. III. Rectangulations, arXiv:2103.09333 [math.CO], 2021.

Baxter and twisted Baxter permutations are both enumerated by the Baxter numbers A001181.

S:=x*y*z:
s[1]:=1:
for en from 2 to 200 do
x*y/(1-y)*(subs(y=1,S))-x/(1-y)*S+x*z*S+x*y*z/(1-z)*(subs(z=1,S))-x*y*z/(1-z)*S;
S:=normal(%):
s[en]:=subs(x=1,z=1,y=1,S);
od:
# Veronica Guerrini, Mar 01 2017

The generating function for a(n) is A(x;1,1) where A(x;y,z) satisfies A(x;y,z) = x*y*z + (x/(1-y))*(y*A(x;1,z) - A(x;y,z)) + x*z*A(x;y,z) + (x*y*z/(1-z))*(A(x;y,1) - A(x;y,z)).

Consequently, neither A(x;1,1) nor A(x;y,z) are D-finite (see preprint of Bouvel et al.).

cp's OEIS Frontend

User: Mathilde Bouvel

A373456 Number of tree interval posets of permutations of size n, considered up to isomorphism.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A373455 Number of interval posets of permutations of size n, considered up to isomorphism.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A348479 Number of interval posets of permutations with n minimal elements.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A333005 Number of unrooted level-2 phylogenetic networks with n+1 labeled leaves, when multiple (i.e., parallel) edges are not allowed.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A333006 Number of rooted level-2 phylogenetic networks with n labeled leaves, when multiple (i.e., parallel) edges are not allowed.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A328126 Number of rooted level-2 phylogenetic networks with n labeled leaves, when multiple (i.e. parallel) edges are allowed.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A328123 Number of unrooted level-2 phylogenetic networks with (n+1) labeled leaves, when multiple (i.e. parallel) edges are allowed.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A328122 Number of rooted level-1 phylogenetic networks with n labeled leaves.

Views

Author

Keywords

Examples

Links

Crossrefs