|
| |
|
|
A175934
|
|
Number of lattice paths from (0,0) to (n,n) using steps S={(1,0),(0,1),(r,r)|0<r<=2} which never go above the line y=x.
|
|
4
|
|
|
|
1, 2, 7, 27, 116, 532, 2554, 12675, 64507, 334836, 1765833, 9434779, 50962640, 277839361, 1526834471, 8448751385, 47035469902, 263260232668, 1480527858436, 8361881707770, 47409359120684, 269736194796537, 1539547726712437, 8812663513352489, 50579825742416942, 291012706492224315, 1678146650028389023
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
REFERENCES
|
J. P. S. Kung and A. de Mier, Catalan lattice paths with rook, bishop and spider steps, Journal of Combinatorial Theory, Series A 120 (2013) 379-389. - From N. J. A. Sloane, Dec 27 2012
|
|
|
LINKS
|
Table of n, a(n) for n=0..26.
|
|
|
FORMULA
|
G.f.: (1-x-x^2-sqrt(x^4+2*x^3-x^2-6*x+1))/(2*x). - Mark van Hoeij, Apr 16 2013
|
|
|
EXAMPLE
|
a(2)=7 because we can reach (2,2) in the following ways:
(1,0),(1,0),(0,1),(0,1)
(1,0),(0,1),(1,0),(0,1)
(1,0),(0,1),(1,1)
(1,0),(1,1),(0,1)(1,1),(1,0),(0,1)
(1,1),(1,1)
(2,2)
|
|
|
PROG
|
sage: (replace dots with spaces)
n=20
M=[]
for posx in range(0, n+1):
........for posy in range(0, n+1):
............if posx==0:
................if posy==0:
....................M.append([1])
................else:
....................M.append([0])
............else:
................if posy==0:
....................M[0].append(0)
....................M[0][posx]=M[0][posx]+M[0][posx-1]
................else:
....................if posy>posx:
........................M[posy].append(0)
....................else:
........................M[posy].append(0)
........................M[posy][posx]=M[posy][posx-1]+M[posy][posx]
........................M[posy][posx]=M[posy-1][posx]+M[posy][posx]
........................for r in range(1, min(posx, posy, 2)+1):
............................M[posy][posx]=M[posy-r][posx-r]+M[posy][posx]
L=[]
for k in range(0, n+1):
....L.append(M[k][k])
print L
|
|
|
CROSSREFS
|
Cf. A175935, A175936, A175937, A175939.
Sequence in context: A150638 A150639 A150640 * A150641 A150642 A150643
Adjacent sequences: A175931 A175932 A175933 * A175935 A175936 A175937
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Eric Werley, Dec 06 2010
|
|
|
STATUS
|
approved
|
| |
|
|
