A126217 -id:A126217 - cp's OEIS frontend

A132889 Sum of the lengths of the longest increasing subsequence over all 321-avoiding permutations of [n].

1, 3, 11, 39, 144, 530, 1987, 7455, 28268, 107334, 410354, 1570954, 6042984, 23273172, 89948835, 348000975, 1350028020, 5241881150, 20396787070, 79426533758, 309829067496, 1209384071532, 4727454837846, 18490127530394

Offset: 1

Emeric Deutsch, Sep 07 2007

nonn

Apparently: Summed over all Dyck (n+1)-paths, the number of ascents of length 1 to the right of the midpoint (ordinate x=n+1). - David Scambler, Aug 08 2012

			a(3)=11 because in the 321-avoiding permutations of 123, namely 123,132,312,213 and 231, the lengths of the longest increasing subsequences are 3,2,2,2 and 2, respectively.

G. C. Greubel, Table of n, a(n) for n = 1..1000
E. Deutsch, A. J. Hildebrand and H. S. Wilf, Longest increasing subsequences in pattern-restricted permutations, The Electronic Journal of Combinatorics, 9(2), 2003, #R12.

Cf. A126217.

a:=proc(n) options operator, arrow: (sum(k*(2*k-n+1)^2*binomial(n+1, n-k)^2,k =floor((1/2)*n+1/2)..n))/(n+1)^2 end proc: seq(a(n),n=1..25);

Table[Sum[k*(2*k-n+1)^2*Binomial[n+1,n-k]^2, {k,Floor[(n+1)/2],n}]/(n+1)^2,{n,1,20}] (* Vaclav Kotesovec, Mar 20 2014 *)

for(n=1,25, print1(sum(k=floor((n+1)/2),n, k*(2*k-n+1)^2 * binomial(n+1,n-k)^2/(n+1)^2), ", ")) \\ G. C. Greubel, May 25 2017

a(n) = Sum_{k=floor((n+1)/2)..n} k*(2*k-n+1)^2*binomial(n+1,n-k)^2 / (n+1)^2.
a(n) = Sum_{k=1..n} k*A126217(n,k).
D-finite Recurrence: n^2*(n+1)*(4*n^3 - 13*n^2 - 3*n + 24)*a(n) = 2*n*(8*n^5 - 14*n^4 - 67*n^3 + 152*n^2 - 67*n + 12)*a(n-1) + 8*(8*n^6 - 66*n^5 + 156*n^4 + 6*n^3 - 461*n^2 + 543*n - 180)*a(n-2) - 32*(n-3)*(n-2)*(2*n - 5)*(4*n^3 - n^2 - 17*n + 12)*a(n-3). - Vaclav Kotesovec, Mar 20 2014
a(n) ~ 2^(2*n-1)/sqrt(Pi*n) * (1 + 2/sqrt(Pi*n)). - Vaclav Kotesovec, Mar 20 2014

A116364 Row squared sums of Catalan triangle A033184.

Original entry on oeis.org

1, 2, 9, 60, 490, 4534, 45689, 489920, 5508000, 64276492, 773029466, 9531003552, 119990158054, 1537695160070, 20009930706137, 263883333450760, 3521003563829212, 47470845904561648, 645960472314074400

Offset: 0

Paul D. Hanna, Feb 04 2006

nonn

Number of 321-avoiding permutations in which the length of the longest increasing subsequence is n. Example: a(2)=9 because we have 12, 132, 312, 213, 231, 3142, 3412, 2143 and 2413. Column sums of triangle in A126217 (n >= 1). - Emeric Deutsch, Sep 07 2007

			The dot product of Catalan row 4 with itself equals
  a(4) = [14,14,9,4,1]*[14,14,9,4,1] = 490
which is equivalent to obtaining the final term in these repeated partial sums of Catalan row 4:
  14,   14,    9,    4,    1
     28,   37,   41,   42
        65,  106,  148
          171,  319
             490

G. C. Greubel, Table of n, a(n) for n = 0..830

Cf. A033184, A116363.

Cf. A126217.

List([0..30], n-> Sum([0..n], j-> (Binomial(2*n-j+1, n-j)* (j+1)/(2*n-j+1))^2 )); # G. C. Greubel, May 12 2019

[(&+[(Binomial(2*n-j+1, n-j)*(j+1)/(2*n-j+1))^2: j in [0..n]]): n in [0..30]]; // G. C. Greubel, May 12 2019

a:=proc(k) options operator, arrow: sum((2*k-n+1)^2*binomial(n+1,k+1)^2/(n+1)^2,n=k..2*k) end proc: 1,seq(a(k),k=1..17); # Emeric Deutsch, Sep 07 2007

Table[Sum[(Binomial[2*n-j+1, n-j]*(j+1)/(2*n-j+1))^2, {j, 0, n}], {n, 0, 30}] (* G. C. Greubel, May 12 2019 *)

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

[sum(( binomial(2*n-j+1, n-j)*(j+1)/(2*n-j+1) )^2 for j in (0..n)) for n in (0..30)] # G. C. Greubel, May 12 2019

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

cp's OEIS Frontend

A132889 Sum of the lengths of the longest increasing subsequence over all 321-avoiding permutations of [n].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula