A005317 a(n) = (2^n + C(2*n,n))/2.

1, 2, 5, 14, 43, 142, 494, 1780, 6563, 24566, 92890, 353740, 1354126, 5204396, 20066492, 77575144, 300572963, 1166868646, 4537698722, 17672894044, 68923788698, 269129985796, 1052051579012, 4116719558104, 16123810230158, 63205319996092, 247959300028484

Offset: 0

Author

N. J. A. Sloane and Peter Fishburn

Keywords

• nonn
• easy

Comments

Hankel transform is A008619. - Paul Barry, Nov 13 2007

a(n) is the number of lattice paths from (0,0) to (n,n) using E(1,0) and N(0,1) as steps that horizontally cross the diagonal y = x with even many times. For example, a(2) = 5 because there are 6 paths in total and only one of them horizontally crosses the diagonal with odd many times, namely, NEEN. - Ran Pan, Feb 01 2016

References

• 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..1664 (first 179 terms from Vincenzo Librandi)
• Jelena Đokic, A short note on the order of the double reduced 2-factor transfer digraph for rectangular grid graphs, arXiv:2308.04155 [math.CO], 2023.
• Jelena Đokić, Olga Bodroža-Pantić, and Ksenija Doroslovački, A spanning union of cycles in rectangular grid graphs, thick grid cylinders and Moebius strips, Transactions on Combinatorics (2023) Art. 27132.
• T. Kløve, Generating functions for the number of permutations with limited displacement, Electron. J. Combin., 16 (2009), #R104. - From _N. J. A. Sloane_, May 04 2011.
• Peter Fishburn, Letter to N. J. A. Sloane, Mar 1987
• Mircea Merca, A Note on Cosine Power Sums J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.
• Ran Pan and Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.
• Simon Plouffe, Approximations of generating functions and a few conjectures, arXiv:0911.4975 [math.NT], 2009.

Crossrefs

Cf. A008619, A108958.

Programs

Magma

[(2^n+Binomial(2*n,n))/2: n in [0..26]];  // Bruno Berselli, Jun 20 2011

Maple

f := n->(2^n+binomial(2*n,n))/2;

Mathematica

Table[(2^n + Binomial[2 n, n])/2, {n, 0, 26}] (* Michael De Vlieger, Feb 01 2016 *)

Maxima

makelist(sum((-1)^k*binomial(2*n,n-2*k),k,0,floor(n/2)),n,0,26); /* Bruno Berselli, Jun 20 2011 */

PARI

a(n)=(2^n+binomial(2*n,n))/2 \\ Charles R Greathouse IV, Dec 20 2011

Formula

From Simon Plouffe, Feb 18 2011: (Start)

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

Recurrence: 0 = (-24-28*n-8*n^2)*a(n+1) + (18+22*n+6*n^2)*a(n+2) + (-3-4*n-n^2)*a(n+3), a(0)=1, a(1)=2, a(2)=5. (End)

a(n) = Sum_{k=0..floor(n/2)} (-1)^k*C(2*n, n-2*k), n > 0. - Mircea Merca, Jun 20 2011

E.g.f.: exp(2*x)*(1+BesselI(0,2*x))/2 = G(0)/2; G(k) = 1 + (k)!/(P-2*x*(2*k+1)*(P^2)/(2*x*(2*k+1)*P+(k+1)^2*k!/G(k+1))), where P:=((2*k)!)/(2^k)/((k)!) (continued fraction). - Sergei N. Gladkovskii, Dec 20 2011

a(n) = Sum_{r=0..n} k*(k+1)/2 where k=C(n,r). - J. M. Bergot, Sep 04 2013

a(n) = binomial(2*n,n) - A108958(n). - Ran Pan, Feb 01 2016

a(n) ~ 2^(2*n-1)/sqrt(n*Pi). - Stefano Spezia, Apr 17 2024