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

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

Author

Mathilde Bouvel, Oct 21 2021

Keywords

• nonn

Links

• 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.

Crossrefs

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

Programs

Mathematica

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 *)

PARI

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

Formula

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