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

1, 2, 6, 24, 115, 618, 3591, 22088, 141903, 943590, 6452490, 45159480, 322305165, 2339100078, 17223121350, 128428689888, 968383277791, 7374380672718, 56655414930642, 438741242896680, 3422125459579869, 26866961380274598, 212191772351034249, 1685036376746788392

Offset: 0

Author

Paul D. Hanna, Feb 23 2007

Keywords

• nonn

Comments

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

Examples

			Illustrate a(n) = Sum_{k=0..n} A000108(k)*A001263(n+1,k+1) by:
a(2) = 1*(1) + 1*(3) + 2*(1) = 6;
a(3) = 1*(1) + 1*(6) + 2*(6) + 5*(1) = 24;
a(4) = 1*(1) + 1*(10)+ 2*(20)+ 5*(10)+ 14*(1) = 115.
The Narayana triangle A001263(n+1,k+1) = C(n,k)*C(n+1,k)/(k+1) begins:
1;
1, 1;
1, 3, 1;
1, 6, 6, 1;
1, 10, 20, 10, 1;
1, 15, 50, 50, 15, 1; ...
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
• Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.

Crossrefs

Cf. A005802, A000108, A001263, A259833.

Programs

Maple

a := n -> hypergeom([1/2, -n - 1, -n], [2, 2], 4):
seq(simplify(a(n)), n = 0..23);  # Peter Luschny, Nov 06 2023

Mathematica

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 *)
Table[HypergeometricPFQ[{1/2, -1 - n, -n}, {2, 2}, 4], {n, 0, 20}] (* Vaclav Kotesovec, May 14 2016 *)

PARI

{a(n)=sum(k=0,n,binomial(2*k,k)*binomial(n,k)*binomial(n+1,k)/(k+1)^2)}

Formula

a(n) = (n+1)*A005802(n), where A005802(n) = number of permutations in S_n with longest increasing subsequence of length <= 3.

a(n) = Sum_{k=0..n} C(2k,k)*C(n,k)*C(n+1,k)/(k+1)^2.

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

a(n) ~ 3^(2*n+9/2)/(16*Pi*n^3). - Vaclav Kotesovec, Oct 20 2012

a(n) = hypergeom([1/2, -n - 1, -n], [2, 2], 4). - Vaclav Kotesovec, May 14 2016