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,2

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

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.

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

Example

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

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

Prog

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

Crossrefs

Cf. A005802, A000108, A001263, A259833.

Sequence in context: A174072 A224255 A326348 * A069657 A369766 A211321

Adjacent sequences: A128085 A128086 A128087 * A128089 A128090 A128091

Keyword

nonn

Author

Paul D. Hanna, Feb 23 2007

Status

approved