A000259 - OEIS

%I M2943 N1185 #62 Oct 24 2024 12:33:55

%S 1,3,13,63,326,1761,9808,55895,324301,1908878,11369744,68395917,

%T 414927215,2535523154,15592255913,96419104103,599176447614,

%U 3739845108057,23435007764606,147374772979438,929790132901804,5883377105975922,37328490926964481,237427707464042693

%N Number of certain rooted planar maps.

%C 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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%H Michael De Vlieger, <a href="/A000259/b000259.txt">Table of n, a(n) for n = 1..1211</a>

%H D. Birmajer, J. Gil, and M. Weiner, <a href="https://arxiv.org/abs/1707.09918"> Bounce statistics for rational lattice paths</a>, arXiv:1707.09918 [math.CO], 2017.

%H W. G. Brown, <a href="http://dx.doi.org/10.4153/CJM-1963-056-7">Enumeration of non-separable planar maps</a>, Canad. J. Math., 15 (1963), 526-545.

%H W. G. Brown, <a href="/A000087/a000087.pdf">Enumeration of non-separable planar maps</a> [Annotated scanned copy]

%H Anthony G. Shannon, Hakan Akkuş, Yeşim Aküzüm, Ömür Deveci, and Engin Özkan, <a href="https://doi.org/10.7546/nntdm.2024.30.3.530-537">A partial recurrence Fibonacci link</a>, Notes Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 530-537. See Table 2, p. 534.

%F 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

%F a(n) ~ 3^(3*n + 1/2) / (5 * sqrt(Pi) * n^(3/2) * 2^(2*n - 1)). - _Vaclav Kotesovec_, Jul 06 2024

%e 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

%p 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

%p 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

%t 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_ *)

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

%o (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

%o (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

%o (Python)

%o from sympy import binomial, fibonacci

%o 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))

%o print([a(n) for n in range(1, 21)]) # _Indranil Ghosh_, Aug 05 2017

%Y Row sums of A046651.

%K nonn

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _Emeric Deutsch_, Mar 03 2004