A116364 Row squared sums of Catalan triangle A033184.

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

Offset

0,2

Comments

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

Links

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

Formula

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

Example

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

Maple

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

Mathematica

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

Prog

(PARI) a(n)=sum(k=0, n, ((k+1)*binomial(2*n-k+1, n-k)/(2*n-k+1))^2)
(Magma) [(&+[(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
(Sage) [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
(GAP) 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

Crossrefs

Cf. A033184, A116363.

Cf. A126217.

Sequence in context: A366240 A363390 A205570 * A354314 A354496 A357683

Adjacent sequences: A116361 A116362 A116363 * A116365 A116366 A116367

Keyword

nonn

Author

Paul D. Hanna, Feb 04 2006

Status

approved