%I M4229 #106 Sep 08 2022 08:44:34

%S 1,6,39,258,1719,11496,77052,517194,3475071,23366598,157206519,

%T 1058119992,7124428836,47983020624,323240752272,2177956129818,

%U 14677216121871,98923498131762,666819212874501,4495342330033938,30308036621747679,204356509814519712

%N a(n) = Sum_{k=0..n} binomial(3k,k)*binomial(3n-3k,n-k).

%C The right-hand sides of several of the "Ruehr identities". - _N. J. A. Sloane_, Feb 20 2020

%C Convolution of A005809 with itself. - _Emeric Deutsch_, May 22 2003

%D Allouche, J-P. "Two binomial identities of Ruehr Revisited." The American Mathematical Monthly 126.3 (2019): 217-225.

%D Alzer, Horst, and Helmut Prodinger. "On Ruehr's Identities." Ars Comb. 139 (2018): 247-254.

%D Bai, Mei, and Wenchang Chu. "Seven equivalent binomial sums." Discrete Mathematics 343.2 (2020): 111691.

%D M. Petkovsek et al., A=B, Peters, 1996, p. 165.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A006256/b006256.txt">Table of n, a(n) for n = 0..1000</a>

%H Jean-Paul Allouche, <a href="https://arxiv.org/abs/1706.08929">A generalization of an identity due to Kimura and Ruehr</a>, arXiv preprint arXiv:1706.08929 [math.NT], 2017.

%H Jean-Paul Allouche, <a href="https://arxiv.org/abs/1707.05751">Two exercises of Comtet and two identities of Ruehr</a>, arXiv preprint arXiv:1707.05751 [math.NT], 2017.

%H Rui Duarte and António Guedes de Oliveira, <a href="http://arxiv.org/abs/1302.2100">Short note on the convolution of binomial coefficients</a>, arXiv:1302.2100 [math.CO], 2013 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Duarte/duarte3.html">J. Int. Seq. 16 (2013) #13.7.6</a>.

%H Shalosh B. Ekhad, Doron Zeilberger, <a href="https://arxiv.org/abs/1903.09511">Some Remarks on a recent article by J.-P. Allouche</a>, arXiv:1903.09511 [math.CO], 2019.

%H N, Kimura and O. G. Ruehr, <a href="https://www.jstor.org/stable/2321581">Change of variable formula for definite integral. Problem E2765</a>, Am. Math. Mnthly, 87, 1980, 307-308.

%H S. Meehan, A. Tefera, M. Weselcouch, A. Zeleke, <a href="https://www.emis.de/journals/INTEGERS/papers/o10/o10.Abstract.html">Proofs of Ruehr's identities</a>, Integers 14 (2014) A10.

%H D. Merlini, R. Sprugnoli and M. C. Verri, <a href="https://doi.org/10.1006/jcta.2002.3273">The tennis ball problem</a>, J. Combin. Theory, A 99 (2002), 307-344 (Y_n for s=3).

%F a(n) = (3/4)*(27/4)^n*(1+c/sqrt(n)+o(n^(-1/2))) where c = (2/3)*sqrt(1/(3*Pi)) = 0.217156671956853298... More generally, a(n, m) = sum(k=0, n, C(m*k,k) *C(m*(n-k),n-k)) is asymptotic to (1/2)*m/(m-1)*(m^m/(m-1)^(m-1))^n. See A000302, A078995 for cases m=2 and 4. - _Benoit Cloitre_, Jan 26 2003, extended by _Vaclav Kotesovec_, Nov 06 2012

%F G.f.: 1/(1-3*z*g^2)^2, where g=g(z) is given by g=1+z*g^3, g(0)=1, i.e. (in Maple command) g := 2*sin(arcsin(3*sqrt(3*z)/2)/3)/sqrt(3*z). - _Emeric Deutsch_, May 22 2003

%F D-finite with recurrence: 6*(36*n^2-45*n+16)*a(n-1) - 81*(3*n-4)*(3*n-2)*a(n-2) - 8*n*(2*n-1)*a(n) = 0. - _Vaclav Kotesovec_, Oct 05 2012

%F From _Rui Duarte_ and António Guedes de Oliveira, Feb 17 2013: (Start)

%F a(n) = sum(k=0, n, C(3*k+l,k)*C(3*(n-k)-l,n-k)) for every real number l.

%F a(n) = sum(k=0, n, 2^(n-k)*C(3n+1,k)).

%F a(n) = sum(k=0, n, 3^(n-k)*c(2n+k,k)). (End)

%F From _Akalu Tefera_, Sean Meehan, Michael Weselcouch, and Aklilu Zeleke, May 11 2013: (Start)

%F a(n) = sum(k=0, 2n, (-3)^k*C(3n - k, n)).

%F a(n) = sum(k=0, 2n, (-4)^k*C(3n + 1, 2n - k)).

%F a(n) = sum(k=0, n, 3^k*C(3n - k, 2n)).

%F a(n) = sum(k=0, n, 2^k*C(3n + 1, n - k)). (End)

%F a(n) = C(3*n+1,n)*Hyper2F1(1,-n,2*n+2,-2). - _Peter Luschny_, May 19 2015

%p a:= proc(n) option remember; `if`(n<2, 5*n+1,

%p ((216*n^2-270*n+96) *a(n-1)

%p -81*(3*n-2)*(3*n-4) *a(n-2)) /(n*(16*n-8)))

%p end:

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Nov 07 2012

%t a[n_] := HypergeometricPFQ[{1/3, 2/3, 1/2-n, -n}, {1/2, 1/3-n, 2/3-n}, 1]*(3n)!/(n!*(2n)!); Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Jun 20 2012 *)

%t Table[Sum[Binomial[3k,k]Binomial[3n-3k,n-k],{k,0,n}],{n,0,30}] (* _Harvey P. Dale_, Oct 23 2013 *)

%o (Haskell)

%o a006256 n = a006256_list !! n

%o a006256_list = f (tail a005809_list) [1] where

%o f (x:xs) zs = (sum $ zipWith (*) zs a005809_list) : f xs (x : zs)

%o -- _Reinhard Zumkeller_, Sep 21 2014

%o (Sage)

%o a = lambda n: binomial(3*n+1,n)*hypergeometric([1,-n],[2*n+2],-2)

%o [simplify(a(n)) for n in range(20)] # _Peter Luschny_, May 19 2015

%o (PARI) a(n)=sum(k=0,n, binomial(3*k,k)*binomial(3*n-3*k,n-k)) \\ _Charles R Greathouse IV_, Feb 07 2017

%o (Magma) [&+[Binomial(3*k, k) *Binomial(3*n-3*k, n-k): k in [0..n]]:n in [0..22]]; // _Vincenzo Librandi_, Feb 21 2020

%Y Cf. A005809, A036829.

%K nonn,easy,nice

%O 0,2

%A _N. J. A. Sloane_, _Don Knuth_