A000259 Number of certain rooted planar maps.

1, 3, 13, 63, 326, 1761, 9808, 55895, 324301, 1908878, 11369744, 68395917, 414927215, 2535523154, 15592255913, 96419104103, 599176447614, 3739845108057, 23435007764606, 147374772979438, 929790132901804, 5883377105975922, 37328490926964481, 237427707464042693

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

a(n) is also the number of North-East lattice paths from (0,0) to (2n,n) that begin with a North step, end with an East step, and do not bounce off the line y =1/2 x. Similarly, also the number of paths that begin with an East step, end with a North step, and do not bounce off the line y=1/2 x. - Michael D. Weiner, Aug 03 2017

Examples

			For n = 2 the a(2) = 3 is counting the following three paths EEEENN, EEENEN, ENEEEN. The path EENEEN is excluded as it bounces off the line y = (1/2) x at the point (2, 1). - _Michael D. Weiner_, Aug 03 2017
		

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

• Michael De Vlieger, Table of n, a(n) for n = 1..1211
• D. Birmajer, J. Gil, and M. Weiner, Bounce statistics for rational lattice paths, arXiv:1707.09918 [math.CO], 2017.
• W. G. Brown, Enumeration of non-separable planar maps, Canad. J. Math., 15 (1963), 526-545.
• W. G. Brown, Enumeration of non-separable planar maps [Annotated scanned copy]
• Anthony G. Shannon, Hakan Akkuş, Yeşim Aküzüm, Ömür Deveci, and Engin Özkan, A partial recurrence Fibonacci link, Notes Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 530-537. See Table 2, p. 534.

Crossrefs

Row sums of A046651.

Programs

Magma

[&+[(-1)^(k-1)*Binomial(3*n, n-k)*k/n*Fibonacci(k - 2):k in [0..n]]: n in [1..30]]; // Vincenzo Librandi, Aug 05 2017

Maple

with(linalg): T := proc(n,k) if k<=n then k*add((2*j-k)*(j-1)!*(3*n-j-k-1)!/(j-k)!/(j-k)!/(2*k-j)!/(n-j)!,j=k..min(n,2*k))/(2*n-k)! else 0 fi end: A := matrix(30,30,T): seq(add(A[i,j],j=1..i),i=1..30); # Emeric Deutsch, Mar 03 2004
R := RootOf(x-t*(t-1)^2, t); ogf := series(1/((1-R-R^2)*(R-1)^2), x=0, 30); # Mark van Hoeij, Nov 08 2011

Mathematica

R = Root[#^3-2#^2+#-x&, 1]; CoefficientList[1/((1-R-R^2)*(R-1)^2) + O[x]^30, x] (* Jean-François Alcover, Feb 06 2016, after Mark van Hoeij *)
Table[Sum[(-1)^(k - 1)*Binomial[3 n, n - k]*k/n*Fibonacci[k - 2], {k, n}], {n, 21}] (* Michael De Vlieger, Aug 04 2017 *)

PARI

a(n) = sum(k = 1, n, (-1)^(k-1)*binomial(3*n,n-k)*k/n*fibonacci(k-2)); \\ Michel Marcus, Aug 04 2017

Python

from sympy import binomial, fibonacci
def a(n): return sum((-1)**(k - 1)*binomial(3*n, n - k)*k//n*fibonacci(k - 2) for k in range(1, n + 1))
print([a(n) for n in range(1, 21)]) # Indranil Ghosh, Aug 05 2017

Formula

a(n) = Sum_{k = 1..n} (-1)^(k-1)*C(3n, n-k)*k/n*F(k-2) where F(k) is the k-th Fibonacci number (A000045) and F(-1) = 1. - Michael D. Weiner, Aug 03 2017

a(n) ~ 3^(3*n + 1/2) / (5 * sqrt(Pi) * n^(3/2) * 2^(2*n - 1)). - Vaclav Kotesovec, Jul 06 2024

Extensions

More terms from Emeric Deutsch, Mar 03 2004