|
%I #41 Nov 04 2021 09:07:28
%S 1,1,3,12,52,240,1160,5795,29681,155025,822563,4421458,24025518,
%T 131759106,728330062,4053823980,22699853940,127790656040,722835069984,
%U 4106096464006,23414579166050,133984343279790,769124367124594,4427878983496972,25559244203741228
%N Number of interval posets of permutations with n minimal elements.
%H M. Bouvel, L. Cioni and B. Izart, <a href="https://arxiv.org/abs/2110.10000">The interval posets of permutations seen from the decomposition tree perspective</a>, arXiv:2110.10000 [math.CO], 2021.
%H B. E. Tenner, <a href="https://arxiv.org/abs/2007.06142">Interval posets for permutations</a>, arXiv:2007.06142 [math.CO], 2020-2021.
%F 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).
%F 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).
%F 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).
%F 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
%t 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 *)
%o (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
%Y For interval posets which are in addition trees, see A054515.
%K nonn
%O 1,3
%A _Mathilde Bouvel_, Oct 21 2021
|
