login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 2
1, 2, 6, 24, 115, 618, 3591, 22088, 141903, 943590, 6452490, 45159480, 322305165, 2339100078, 17223121350, 128428689888, 968383277791, 7374380672718, 56655414930642, 438741242896680, 3422125459579869, 26866961380274598, 212191772351034249, 1685036376746788392 (list; graph; refs; listen; history; text; internal format)
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, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.

Alice L. L. Gao, 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

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

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 A211321 A242820

Adjacent sequences:  A128085 A128086 A128087 * A128089 A128090 A128091

KEYWORD

nonn

AUTHOR

Paul D. Hanna, Feb 23 2007

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 19 21:04 EDT 2021. Contains 345147 sequences. (Running on oeis4.)