|
|
A000259
|
|
Number of certain rooted planar maps.
(Formerly M2943 N1185)
|
|
2
|
|
|
1, 3, 13, 63, 326, 1761, 9808, 55895, 324301, 1908878, 11369744, 68395917, 414927215, 2535523154, 15592255913, 96419104103, 599176447614, 3739845108057, 23435007764606, 147374772979438, 929790132901804, 5883377105975922, 37328490926964481, 237427707464042693
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
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
|
|
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
|
|
|
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
|
|
EXAMPLE
|
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
|
|
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
|
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 *)
|
|
PROG
|
(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
(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
(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))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|