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!)
A075435 T(n,k) = right- or upward-moving paths connecting opposite corners of a n*n chessboard, visiting the diagonal at k points between start and finish. 2
2, 6, 4, 20, 24, 8, 70, 116, 72, 16, 252, 520, 456, 192, 32, 924, 2248, 2496, 1504, 480, 64, 3432, 9520, 12624, 9728, 4480, 1152, 128, 12870, 39796, 60792, 56400, 33440, 12480, 2688, 256, 48620, 164904, 283208, 304704, 218720, 105600, 33152, 6144 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

2,1

COMMENTS

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 table A039598. Row sums give A075436.

LINKS

Table of n, a(n) for n=2..45.

FORMULA

G.f.: [2*x*c(x)/(1-x*c(x))]^m=sum(n>=m T(n,m)*x^n) where c(x) is the g.f. of A000108, also T(n,m)=sum(k=m..n, k/n*binomial(2*n-k-1,n-1)*2^k*binomial(k-1,m-1)), n>=m>0. [Vladimir Kruchinin, Mar 30 2011]

EXAMPLE

{2},

{6, 4},

{20, 24, 8},

{70, 116, 72, 16},

{252, 520, 456, 192, 32},

...

MATHEMATICA

Table[Table[Plus@@Apply[Times, Compositions[n-1-k, k]+1 /. i_Integer->Binomial[2i, i], {1}], {k, 1, n-1}], {n, 2, 12}]

PROG

(Maxima)

T(n, m):=sum(k/n*binomial(2*n-k-1, n-1)*2^k*binomial(k-1, m-1), k, m, n); /* Vladimir Kruchinin, Mar 30 2011 */

(Sage)

@cached_function

def T(k, n):

    if k==n: return 2^n

    if k==0: return 0

    return sum(binomial(2*i, i)*T(k-1, n-i) for i in (1..n-k+1))

A075435 = lambda n, k: T(k, n)

for n in (1..9): print([A075435(n, k) for k in (1..n)]) # Peter Luschny, Mar 12 2016

CROSSREFS

Cf. A075436, A039598.

Sequence in context: A079579 A309243 A112326 * A069875 A202962 A019088

Adjacent sequences:  A075432 A075433 A075434 * A075436 A075437 A075438

KEYWORD

easy,nonn,tabl

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.)