A086618 a(n) = Sum{k=0..n} binomial(n,k)^2*C(k), where C() = A000108() are the Catalan numbers.

1, 2, 7, 33, 183, 1118, 7281, 49626, 349999, 2535078, 18758265, 141254655, 1079364105, 8350678170, 65298467487, 515349097713, 4100346740511, 32858696386766, 265001681344569

Offset: 0

Author

Paul D. Hanna, Jul 24 2003

Keywords

• nonn

Comments

Main diagonal of square table A086617 of coefficients, T(n,k), of x^n*y^k in f(x,y) that satisfies f(x,y) = 1/[(1-x)(1-y)] + xy*f(x,y)^2.

a(n) is the number of permutations of length 2n which are invariant under the reverse-complement map and have no decreasing subsequences of length 4. - Eric S. Egge, Oct 21 2008

In 2012, Zhi-Wei Sun proved that for any odd prime p we have the congruence a(1) + ... + a(p-1) == 0 (mod p^2). - Zhi-Wei Sun, Aug 22 2013

Examples

			a(5) = 1118 = 1*1^2 + 1*5^2 + 2*10^2 + 5*10^2 + 14*5^2 + 42*1^2.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• D. Daly and L. Pudwell, Pattern avoidance in rook monoids, 2013.
• T. Denton, Algebraic and Affine Pattern Avoidance, arXiv preprint arXiv:1303.3767 [math.CO], 2013.
• Z.-W. Sun, Congruences for Franel numbers, arXiv preprint arXiv:1112.1034 [math.NT], 2011. See (1.22).
• Z.-W. Sun, On sums of Apery polynomials and related congruences, J. Number Theory 132(2012), 2673-2699.

Crossrefs

Cf. A086617 (table), A086615 (antidiagonal sums), A003046 (determinants).

Cf. A000108.

Cf. A228456.

Programs

Mathematica

Flatten[{1,RecurrenceTable[{(n+3)^2*(4*n+7)*a[n+2]==2*(20*n^3+117*n^2+220*n+135)*a[n+1]-9*(n+1)^2*(4*n+11)*a[n],a[1]==2,a[2]==7},a,{n,1,20}]}] (* Vaclav Kotesovec, Sep 11 2012 *)
Table[HypergeometricPFQ[{1/2, -n, -n}, {1, 2}, 4], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 03 2016 *)

PARI

a(n)=sum(k=0,n-1,binomial(n-1,k)^2*binomial(2*k,k)/(k+1)) \\ Charles R Greathouse IV, Sep 12 2012

PARI

a(n)=sum(k=0,n-1,(4*k+3)*sum(i=0,k,binomial(k,i)^2*binomial(2*i,i)))/3/n^2 \\ Charles R Greathouse IV, Sep 12 2012

Formula

Recurrence: (n+3)^2*(4*n+7)*a(n+2) = 2*(20*n^3+117*n^2+220*n+135)*a(n+1) - 9*(n+1)^2*(4*n+11)*a(n). - Vaclav Kotesovec, Sep 11 2012

a(n) ~ 3^(5/2)/(8*Pi) * 9^n/n^2. - Vaclav Kotesovec, Oct 06 2012

G.f.: (1-(1-9*x)^(1/3)*hypergeom([1/3,1/3],[1],-27*x*(1-x)^2/(1-9*x)^2))/(6*x). - Mark van Hoeij, May 02 2013

a(n) = hypergeom([1/2,-n,-n], [1,2], 4). - Vladimir Reshetnikov, Oct 03 2016

D-finite with recurrence (n+1)^2*a(n) +(-19*n^2+8*n+6)*a(n-1) +9*(11*n^2-30*n+21)*a(n-2) -81*(n-2)^2*a(n-3)=0. - R. J. Mathar, Aug 01 2022

Extensions

Edited by N. J. A. Sloane, Sep 14 2012. The formula in the new definition was first sent in by Michael Somos, Feb 19 2004

Minor edits Vaclav Kotesovec, Mar 31 2014