A002003 a(n) = 2 * Sum_{k=0..n-1} binomial(n-1, k)*binomial(n+k, k).

0, 2, 8, 38, 192, 1002, 5336, 28814, 157184, 864146, 4780008, 26572086, 148321344, 830764794, 4666890936, 26283115038, 148348809216, 838944980514, 4752575891144, 26964373486406, 153196621856192, 871460014012682, 4962895187697048, 28292329581548718

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

a(n) is the number of order-preserving partial self maps of {1,...,n}. For example, a(2) = 8 because there are 8 order-preserving partial self maps of {1,2}: (1 2), (1 1), (2 2), (1 -), (2 -), (- 1), (- 2), (- -). Here for example (2 -) represents the partial map which maps 1 to 2 but does not include 2 in its domain. - James East, Oct 25 2005

From Peter Bala, Mar 02 2020: (Start)

For fixed m = 1,2,3,..., we conjecture that the sequence b(n) := a(m*n) satisfies a recurrence of the form P(2*m,n)*b(n+1) + P(2*m,-n)*b(n-1) = Q(2*m,n)*b(n), where the polynomials P(2*m,n) and Q(2*m,n) have degree 2*m. Conjecturally, the polynomial Q(2*m,n) is an even function of n; its 2*m zeros seem to belong to the interval [-1, 1] and 2*m - 2 of these zeros appear to lie close to the rational numbers of the form +-(2*k + 1)/(2*m), where 0 <= k <= m - 2. Cf. A103885. (End)

a(n), n>0, is the number of points at L1 distance = n from any given point in Z^n. The sequence is also the difference between the central diagonal (A001850) and +-1 diagonal (A002002) of the Delannoy number triangle (A008288). - Shel Kaphan, Feb 15 2023

Examples

			G.f. = 2*x + 8*x^2 + 38*x^3 + 192*x^4 + 1002*x^5 + 5336*x^6 + 28814*x^7 + ...
		

References

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

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..1000 (terms 0..200 from T. D. Noe)
• Peter Bala, A supercongruence for A002003
• J. Brzozowski, M. Szykula, Large Aperiodic Semigroups, arXiv preprint arXiv:1401.0157 [cs.FL], 2013-2014.
• Milan Janjić, On Restricted Ternary Words and Insets, arXiv:1905.04465 [math.CO], 2019.
• G. Rutledge and R. D. Douglass, Integral functions associated with certain binomial coefficient sums, Amer. Math. Monthly, 43 (1936), 27-32.

Crossrefs

Cf. A002002, A006318, A027307, A108424, A103885.

Programs

Maple

A064861 := proc(n,k) option remember; if n = 1 then 1; elif k = 0 then 0; else A064861(n,k-1)+(3/2-1/2*(-1)^(n+k))*A064861(n-1,k); fi; end; seq(A064861(i,i-1),i=1..40);

Mathematica

Flatten[{0,Table[SeriesCoefficient[((1+x)/Sqrt[1-6*x+x^2]-1)/2,{x,0,n}],{n,1,20}]}] (* Vaclav Kotesovec, Oct 04 2012 *)
a[ n_] := If[ n < 1, 0, Hypergeometric2F1[ n, -n, 1, -1]]; (* Michael Somos, Aug 24 2014 *)
Table[2*Sum[Binomial[n-1,k]Binomial[n+k,k],{k,0,n-1}],{n,0,30}] (* Harvey P. Dale, Sep 18 2024 *)

PARI

{a(n) = if( n<1, 0, polcoeff( ((1 - x^2) / (1 - x)^2 + x * O(x^n))^n, n))} /* Michael Somos, Sep 24 2003 */

Python

from math import comb
def A002003(n): return sum(comb(n,k)**2*k<Chai Wah Wu, Mar 22 2023

Formula

a(n) = 2*A047781(n).

From Vladeta Jovovic, Mar 28 2004: (Start)

G.f.: ((1+x)/sqrt(1-6*x+x^2)-1)/2.

E.g.f.: exp(3*x)*(2*BesselI(0, 2*sqrt(2)*x)+sqrt(2)*BesselI(1, 2*sqrt(2)*x)). (End)

a(n) = T(n, n-1), array T as in A064861.

a(n) = T(n, n-2), array T as in A049600.

a(n+1) = A110110(2n+1). - Tilman Neumann, Feb 05 2009

a(n) = 2 * JacobiP(n-1,0,1,3) = ((7*n+3)*LegendreP(n,3) - (n+1)*LegendreP(n+1,3)) /(2*n) for n > 0. - Mark van Hoeij, Jul 12 2010

Logarithmic derivative of A006318, the large Schroeder numbers. - Paul D. Hanna, Oct 25 2010

D-finite with recurrence: 4*(3*n^2-6*n+2)*a(n-1) - (n-2)*(2*n-1)*a(n-2) - n*(2*n-3)*a(n)=0. - Vaclav Kotesovec, Oct 04 2012

a(n) ~ (3+2*sqrt(2))^n/(2^(3/4)*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 04 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) = Hyper2F1([-n, n], [1], -1) for n > 0. - Peter Luschny, Aug 02 2014

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

From Peter Bala, Mar 13 2020: (Start)

a(n) = 2 * Sum_{k = 0..n-1} 2^k*C(n,k+1)*C(n-1,k).

a(n) = 2 * (-1)^(n+1) * Sum_{k = 0..n-1} (-2)^k*C(n+k,n-1)*C(n-1,k).

a(n) = Sum_{k = 0..n} C(n,k)*C(2*n-k-1,n-1).

Conjecture: a(n) = - [x^n] (1 - F(x))^n, where F(x) = 2*x + 6*x^2 + 34*x^3 + 238*x^4 + ... is the o.g.f. of A108424. Equivalently, a(n) = -[x^n](G(x))^(-n), where G(x) = 1 + 2*x + 10*x^2 + 66*x^3 + 498*x^4 + ... is the o.g.f. of A027307.

a(p) == 2 ( mod p^3 ) for prime p >= 5. (End)

a(n) = Sum_{k = 1..n} C(n, k) * C(n-1, k-1) * 2^k. - Michael Somos, May 23 2021

a(n) = A001850(n) - A002002(n), for n > 0. - Shel Kaphan, Feb 15 2023

Extensions

More terms from Barbara Haas Margolius (b.margolius(AT)csuohio.edu), Oct 10 2001