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

Author

N. J. A. Sloane

Keywords

• nonn

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.

Crossrefs

Cf. A002003. Column 1 of A296129.

Programs

Haskell

a047781 n = a049600 (2 * n) n  -- Reinhard Zumkeller, Apr 15 2014

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

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

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

PARI

A047781(n)=polcoeff((1+x)/sqrt(1+(O(x^n)-6)*x+x^2),n)\4  \\ M. F. Hasler, Oct 09 2012

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<Chai Wah Wu, Mar 22 2023

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