A047781 a(n) = Sum_{k=0..n-1} binomial(n-1,k)*binomial(n+k,k). Also a(n) = T(n,n), array T as in A049600.

0, 1, 4, 19, 96, 501, 2668, 14407, 78592, 432073, 2390004, 13286043, 74160672, 415382397, 2333445468, 13141557519, 74174404608, 419472490257, 2376287945572, 13482186743203, 76598310928096, 435730007006341, 2481447593848524, 14146164790774359

Offset

0,3

Comments

Also main diagonal of array: m(i,1)=1, m(1,j)=j, m(i,j)=m(i,j-1)+m(i-1,j-1)+m(i-1,j): 1 2 3 4 ... / 1 4 9 16 ... / 1 6 19 44 ... / 1 8 33 96 ... /. - Benoit Cloitre, Aug 05 2002

This array is now listed as A142978, where some conjectural congruences for the present sequence are given. - Peter Bala, Nov 13 2008

Convolution of central Delannoy numbers A001850 and little Schroeder numbers A001003. Hankel transform is 2^C(n+1,2)*A007052(n). - Paul Barry, Oct 07 2009

Define a finite triangle T(r,c) with T(r,0) = binomial(n,r) for 0 <= r <= n and the other terms recursively with T(r,c) = T(r-1,c-1) + 2*T(r,c-1). The sum of the last terms in the rows is Sum_{r=0..n} T(r,r) = a(n+1). Example: For n=4 the triangle has the rows 1; 4 9; 6 16 41; 4 14 44 129; 1 6 26 96 321 having sum of last terms 1 + 9 + 41 + 129 + 321 = 501 = a(5). - J. M. Bergot, Feb 15 2013

a(n) = A049600(2*n,n), when A049600 is seen as a triangle read by rows. - Reinhard Zumkeller, Apr 15 2014

a(n-1) for n > 1 is the number of assembly trees with the connected gluing rule for cycle graphs with n vertices. - Nick Mayers, Aug 16 2018

Links

Seiichi Manyama, Table of n, a(n) for n = 0..1000 (terms 0..200 from T. D. Noe)

A. Bacher, Directed and multi-directed animals on the square lattice with next nearest neighbor edges, arXiv preprint arXiv:1301.1365 [math.CO], 2013. See D(t). - From N. J. A. Sloane, Feb 14 2013

C. Banderier and P. Hitczenko, Enumeration and asymptotics of restricted compositions having the same number of parts, Disc. Appl. Math. 160 (18) (2012) 2542-2554. Table 2.

M. Bona and A. Vince, The Number of Ways to Assemble a Graph, arXiv preprint arXiv:1204.3842 [math.CO], 2012.

F. D. Cunden, F. Mezzadri, N. Simm and P. Vivo, Correlators for the Wigner-Smith time-delay matrix of chaotic cavities, arXiv:1601.06690 [math-ph], 2016.

A. Dougherty, N. Mayers, and R. Short, How to Build a Graph in n Days: Some Variants on Graph Assembly, arXiv preprint arXiv:1807.08079 [math.CO], 2018.

Steffen Eger, On the Number of Many-to-Many Alignments of N Sequences, arXiv:1511.00622 [math.CO], 2015.

Steffen Eger, The Combinatorics of Weighted Vector Compositions, arXiv:1704.04964 [math.CO], 2017.

Milan Janjic, Two Enumerative Functions

G. Rutledge and R. D. Douglass, Integral functions associated with certain binomial coefficient sums, Amer. Math. Monthly, 43 (1936), 27-32.

Formula

D-finite with recurrence n*(2*n-3)*a(n) - (12*n^2-24*n+8)*a(n-1) + (2*n-1)*(n-2)*a(n-2) = 0. - Vladeta Jovovic, Aug 29 2004

a(n+1) = Sum_{k=0..n} binomial(n, k)*binomial(n+1, k+1)*2^k. - Paul Barry, Sep 20 2004

a(n) = Sum_{k=0..n} T(n, k), array T as in A008288.

If shifted one place left, the third binomial transform of A098660. - Paul Barry, Sep 20 2004

G.f.: ((1+x)/sqrt(1-6x+x^2)-1)/4. - Paul Barry, Sep 20 2004, simplified by M. F. Hasler, Oct 09 2012

E.g.f. for sequence shifted left: Sum_{n>=0} a(n+1)*x^n/n! = exp(3*x)*(BesselI(0, 2*sqrt(2)*x)+BesselI(1, 2*sqrt(2)*x)/sqrt(2)). - Paul Barry, Sep 20 2004

a(n) = Sum_{k=0..n-1} C(n,k)*C(n-1,k)*2^(n-k-1); a(n+1) = 2^n*Hypergeometric2F1(-n,-n-1;1;1/2). - Paul Barry, Feb 08 2011

a(n) ~ 2^(1/4)*(3+2*sqrt(2))^n/(4*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 08 2012

Recurrence (an alternative): n*a(n) = (6-n)*a(n-6) + 2*(5*n-27)*a(n-5) + (84-15*n)*a(n-4) + 52*(3-n)*a(n-3) + 3*(2-5*n)*a(n-2) + 2*(5*n-3)*a(n-1), n >= 7. - Fung Lam, Feb 05 2014

a(n) = A241023(n) / 4. - Reinhard Zumkeller, Apr 15 2014

a(n) = Hyper2F1([-n, n], [1], -1)/2 for n > 0. - Peter Luschny, Aug 02 2014

n^2*a(n) = Sum_{k=0..n-1} (2*k^2+2*k+1)*binomial(n-1,k)*binomial(n+k,k). By the Zeilberger algorithm, both sides of the equality satisfy the same recurrence. - Zhi-Wei Sun, Aug 30 2014

a(n) = [x^n] (1/2) * ((1+x)/(1-x))^n for n > 0. - Seiichi Manyama, Jun 07 2018

Maple

a := proc(n) local k; add(binomial(n-1, k)*binomial(n+k, k), k=0..n-1); end;

Mathematica

Table[SeriesCoefficient[x*((1+x)-Sqrt[1-6*x+x^2])/(4*x*Sqrt[1-6*x+x^2]), {x, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Oct 08 2012 *)
a[n_] := Hypergeometric2F1[1-n, n+1, 1, -1]; a[0] = 0; Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Feb 26 2013 *)
a[n_] := Sum[ Binomial[n - 1, k] Binomial[n + k, k], {k, 0, n - 1}]; Array[a, 25] (* Robert G. Wilson v, Aug 08 2018 *)

Prog

(Maxima) makelist(if n=0 then 0 else sum(binomial(n-1, k)*binomial(n+k, k), k, 0, n-1), n, 0, 22); \\ Bruno Berselli, May 19 2011
(Magma) [n eq 0 select 0 else &+[Binomial(n-1, k)*Binomial(n+k, k): k in [0..n-1]]: n in [0..22]];  // Bruno Berselli, May 19 2011
(PARI) A047781(n)=polcoeff((1+x)/sqrt(1+(O(x^n)-6)*x+x^2), n)\4  \\ M. F. Hasler, Oct 09 2012
(Haskell)
a047781 n = a049600 (2 * n) n  -- Reinhard Zumkeller, Apr 15 2014
(Python)
from sympy import binomial
def a(n):
    return sum(binomial(n - 1, k) * binomial(n + k, k) for k in range(n))
print([a(n) for n in range(51)]) # Indranil Ghosh, Apr 18 2017
(Python)
from math import comb
def A047781(n): return sum(comb(n, k)**2*k<<k-1 for k in range(1, n+1))//n if n else 0 # Chai Wah Wu, Mar 22 2023

Crossrefs

Cf. A002003. Column 1 of A296129.

Sequence in context: A278678 A020060 A122394 * A089354 A217217 A083315

Adjacent sequences: A047778 A047779 A047780 * A047782 A047783 A047784

Keyword

nonn

Author

N. J. A. Sloane

Status

approved