login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A075436 Right- or upward-moving paths connecting opposite corners of an n X n chessboard, visiting the diagonal in 0 up to (n-2) intermediate points between start and finish. Equivalently, subdivide the chessboard into 1 up to (n-1) blocks along the diagonal in all possible ways and sum the path-count over all sub-blocks. 4
2, 10, 52, 274, 1452, 7716, 41064, 218722, 1165564, 6213100, 33125336, 176629268, 941884088, 5022886536, 26786945232, 142857244674, 761881733148, 4063282813596, 21670523246712, 115574945807004, 616395334890408, 3287425475237496, 17532874879557552 (list; graph; refs; listen; history; text; internal format)
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

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

Cf. A075435, A000984.

Sequence in context: A019475 A020042 A307208 * A319325 A074612 A104497

Adjacent sequences:  A075433 A075434 A075435 * A075437 A075438 A075439

KEYWORD

easy,nonn

AUTHOR

Wouter Meeussen, Sep 15 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 5 07:29 EDT 2020. Contains 336209 sequences. (Running on oeis4.)