OFFSET
2,1
COMMENTS
Invert transform gives the central binomial coefficients A000984.
If it is required that the paths stay at the same side of the diagonal between intermediate points, then the count of intermediate points becomes an exact count of crossings and one gets the central binomial coefficients A000984.
Row sums of A075435.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 2..200
Cyril Banderier, Markus Kuba, and Michael Wallner, Analytic Combinatorics of Composition schemes and phase transitions with mixed Poisson distributions, arXiv:2103.03751 [math.PR], 2021.
FORMULA
G.f.: x*(1-sqrt(1-4*x)-8*x)/(-3+16*x).
Recurrence (for n>3): 3*(n-1)*a(n) = 2*(14*n-23)*a(n-1)-32*(2*n-5)*a(n-2). - Vaclav Kotesovec, Oct 13 2012
a(n) ~ 2^(4*n-4)/3^n. - Vaclav Kotesovec, Oct 13 2012
a(n) = 2^(4*n-7)/3^(n-2) * (1 - Sum_{k=2..n-1} C(2*k-1,k)*3^(k-2)/((2*k-1) * 2^(4*k-4)) ), for n>2. - Vaclav Kotesovec, Oct 28 2012
G.f.: 2/(Q(0)-4*x), where Q(k) = 2*x + (k+1)/(2*k+1) - 2*x*(k+1)/(2*k+1)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 03 2013
EXAMPLE
a(3) = 10 because 0 intermediate points produces 6 paths on a 3 X 3 board and 1 intermediate points produces 4 paths:
1 . 1
1 . 2 . 2
. . 2 . 4
or 6 + 4 = 10 paths in total.
MATHEMATICA
Rest[CoefficientList[Series[(1-Sqrt[1-4*x]-8*x)/(-3+16*x), {x, 0, 24}], x]] (* corrected by Vaclav Kotesovec, Oct 28 2012 *) or combinatorially: Plus@@@Table[Table[Plus@@Apply[Times, Compositions[n-1-k, k]+1 /. i_Integer->Binomial[2i, i], {1}], {k, 1, n-1}], {n, 2, 12}]
Flatten[{2, Table[2^(4*n-7)/3^(n-2)*(1-Sum[Binomial[2*k-1, k]*3^(k-2)/((2*k-1)*2^(4*k-4)), {k, 2, n-1}] ), {n, 3, 20}]}] (* Vaclav Kotesovec, Oct 28 2012 *)
PROG
(PARI) x='x+O('x^66); Vec(x*(1-sqrt(1-4*x)-8*x)/(-3+16*x)) \\ Joerg Arndt, May 07 2013
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Wouter Meeussen, Sep 15 2002
STATUS
approved