|
%I #28 Nov 06 2023 08:34:33
%S 1,2,6,24,115,618,3591,22088,141903,943590,6452490,45159480,322305165,
%T 2339100078,17223121350,128428689888,968383277791,7374380672718,
%U 56655414930642,438741242896680,3422125459579869,26866961380274598,212191772351034249,1685036376746788392
%N a(n) = Sum_{k=0..n} A000108(k)*A001263(n+1,k+1), where A000108 is the Catalan numbers and A001263 is the Narayana triangle.
%C a(n) is the number of permutations of length n+1 avoiding the partially ordered pattern (POP) {1>2>3>4} of length 5. That is, the number of length n+1 permutations having no subsequences of length 5 in which the element in position 1 is larger than the element in position 2, which in turn is larger than the element in position 3, and that element is larger than the element in position 4. - _Sergey Kitaev_, Dec 13 2020
%H Vincenzo Librandi, <a href="/A128088/b128088.txt">Table of n, a(n) for n = 0..200</a>
%H Alice L. L. Gao and Sergey Kitaev, <a href="https://arxiv.org/abs/1903.08946">On partially ordered patterns of length 4 and 5 in permutations</a>, arXiv:1903.08946 [math.CO], 2019.
%H Alice L. L. Gao and Sergey Kitaev, <a href="https://doi.org/10.37236/8605">On partially ordered patterns of length 4 and 5 in permutations</a>, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
%F a(n) = (n+1)*A005802(n), where A005802(n) = number of permutations in S_n with longest increasing subsequence of length <= 3.
%F a(n) = Sum_{k=0..n} C(2k,k)*C(n,k)*C(n+1,k)/(k+1)^2.
%F Recurrence: (n+2)^2*a(n) = (n+1)*(7*n+2)*a(n-1) + 3*(n-2)*(7*n-4)*a(n-2) - 27*(n-2)*(n-1)*a(n-3) . - _Vaclav Kotesovec_, Oct 20 2012
%F a(n) ~ 3^(2*n+9/2)/(16*Pi*n^3). - _Vaclav Kotesovec_, Oct 20 2012
%F a(n) = hypergeom([1/2, -n - 1, -n], [2, 2], 4). - _Vaclav Kotesovec_, May 14 2016
%e Illustrate a(n) = Sum_{k=0..n} A000108(k)*A001263(n+1,k+1) by:
%e a(2) = 1*(1) + 1*(3) + 2*(1) = 6;
%e a(3) = 1*(1) + 1*(6) + 2*(6) + 5*(1) = 24;
%e a(4) = 1*(1) + 1*(10)+ 2*(20)+ 5*(10)+ 14*(1) = 115.
%e The Narayana triangle A001263(n+1,k+1) = C(n,k)*C(n+1,k)/(k+1) begins:
%e 1;
%e 1, 1;
%e 1, 3, 1;
%e 1, 6, 6, 1;
%e 1, 10, 20, 10, 1;
%e 1, 15, 50, 50, 15, 1; ...
%p a := n -> hypergeom([1/2, -n - 1, -n], [2, 2], 4):
%p seq(simplify(a(n)), n = 0..23); # _Peter Luschny_, Nov 06 2023
%t Table[Sum[Binomial[2*k,k]*Binomial[n,k]*Binomial[n+1,k]/(k+1)^2,{k,0,n}],{n,0,20}] (* _Vaclav Kotesovec_, Oct 20 2012 *)
%t Table[HypergeometricPFQ[{1/2, -1 - n, -n}, {2, 2}, 4], {n, 0, 20}] (* _Vaclav Kotesovec_, May 14 2016 *)
%o (PARI) {a(n)=sum(k=0,n,binomial(2*k,k)*binomial(n,k)*binomial(n+1,k)/(k+1)^2)}
%Y Cf. A005802, A000108, A001263, A259833.
%K nonn
%O 0,2
%A _Paul D. Hanna_, Feb 23 2007
|
