A006256 a(n) = Sum_{k=0..n} binomial(3k,k)*binomial(3n-3k,n-k). (Formerly M4229)

1, 6, 39, 258, 1719, 11496, 77052, 517194, 3475071, 23366598, 157206519, 1058119992, 7124428836, 47983020624, 323240752272, 2177956129818, 14677216121871, 98923498131762, 666819212874501, 4495342330033938, 30308036621747679, 204356509814519712

Offset

0,2

Comments

The right-hand sides of several of the "Ruehr identities". - N. J. A. Sloane, Feb 20 2020

Convolution of A005809 with itself. - Emeric Deutsch, May 22 2003

References

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

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

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

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

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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Jean-Paul Allouche, A generalization of an identity due to Kimura and Ruehr, arXiv preprint arXiv:1706.08929 [math.NT], 2017.

Jean-Paul Allouche, Two exercises of Comtet and two identities of Ruehr, arXiv preprint arXiv:1707.05751 [math.NT], 2017.

Rui Duarte and António Guedes de Oliveira, Short note on the convolution of binomial coefficients, arXiv:1302.2100 [math.CO], 2013 and J. Int. Seq. 16 (2013) #13.7.6.

Shalosh B. Ekhad, Doron Zeilberger, Some Remarks on a recent article by J.-P. Allouche, arXiv:1903.09511 [math.CO], 2019.

N, Kimura and O. G. Ruehr, Change of variable formula for definite integral. Problem E2765, Am. Math. Mnthly, 87, 1980, 307-308.

S. Meehan, A. Tefera, M. Weselcouch, A. Zeleke, Proofs of Ruehr's identities, Integers 14 (2014) A10.

D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344 (Y_n for s=3).

Formula

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

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

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

From Rui Duarte and António Guedes de Oliveira, Feb 17 2013: (Start)

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

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

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

From Akalu Tefera, Sean Meehan, Michael Weselcouch, and Aklilu Zeleke, May 11 2013: (Start)

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

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

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

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

a(n) = C(3*n+1,n)*Hyper2F1(1,-n,2*n+2,-2). - Peter Luschny, May 19 2015

Maple

a:= proc(n) option remember; `if`(n<2, 5*n+1,
      ((216*n^2-270*n+96) *a(n-1)
      -81*(3*n-2)*(3*n-4) *a(n-2)) /(n*(16*n-8)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 07 2012

Mathematica

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 *)
Table[Sum[Binomial[3k, k]Binomial[3n-3k, n-k], {k, 0, n}], {n, 0, 30}] (* Harvey P. Dale, Oct 23 2013 *)

Prog

(Haskell)
a006256 n = a006256_list !! n
a006256_list = f (tail a005809_list) [1] where
   f (x:xs) zs = (sum $ zipWith (*) zs a005809_list) : f xs (x : zs)
-- Reinhard Zumkeller, Sep 21 2014
(Sage)
a = lambda n: binomial(3*n+1, n)*hypergeometric([1, -n], [2*n+2], -2)
[simplify(a(n)) for n in range(20)] # Peter Luschny, May 19 2015
(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
(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

Crossrefs

Cf. A005809, A036829.

Sequence in context: A305289 A090018 A238809 * A052392 A370376 A357206

Adjacent sequences: A006253 A006254 A006255 * A006257 A006258 A006259

Keyword

nonn,easy,nice

Author

N. J. A. Sloane, Don Knuth

Status

approved