|
Search: id:A005700
|
|
|
| A005700 |
|
Number of Dyck paths: a(n) = number of walks of 2n unit steps north, east, south, or west starting and ending at the origin and confined to the first octant.
(Formerly M2975)
|
|
+0
5
|
|
| 1, 1, 3, 14, 84, 594, 4719, 40898, 379236, 3711916, 37975756, 403127256, 4415203280, 49671036900, 571947380775, 6721316278650, 80419959684900, 977737404590100, 12058761323277900, 150656212896017400
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
Image of Catalan numbers (A000108) under "little Hankel" transform that sends [c_0, c_1, ...] to [d_0, d_1, ...] where d_n = c_n^2 - c_{n+1}*c_{n-1}.
The Niederhausen reference counts various classes of first octant paths by number of contacts with the line y=x. - David Callan (callan(AT)stat.wisc.edu), Sep 18 2007
|
|
REFERENCES
|
N. Bonichon, A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths, Discr. Math., 298 (2005), 104-114.
S. J. Cyvin and I. Gutman, Kekule structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 183).
D. Gouyou-Beauchamps, Chemins sous-diagonaux et tableau de Young, pp. 112-125 of "Combinatoire Enumerative (Montreal 1985)", Lect. Notes Math. 1234, 1986.
Heinrich Niederhausen, A Note on the Enumeration of Diffusion Walks in the First Octant by Their Number of Contacts with the Diagonal, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.3.
|
|
LINKS
|
W. Y. C. Cheng, E. Y. P. Deng, R. R. X. Du, R. P. Stanley and C. H. Yan, Crossings and nestings of matchings and partitions
Alec Mihailovs, Enumeration of walks on lattices.
Index entries for sequences related to Young tableaux.
Kiran S. Kedlaya and Andrew V. Sutherland, Hyperelliptic curves, L-polynomials and random matrices.
|
|
FORMULA
|
G.f.: 3_F_2( [ 1, 1/2, 3/2 ]; [ 3, 4 ]; 16 x ).
a(n) = 6*(2*n)!*(2*n+2)!/(n!*(n+1)!*(n+2)!*(n+3)!) (Mihailovs).
a(n)=Det[Table[binomial[i+1, j-i+2], {i, 1, n}, {j, 1, n}]] - David Callan (callan(AT)stat.wisc.edu), Jul 20 2005
a(n)=b(n)b(n+1)/6 where b(n) is the superballot number A007054. - David Callan (callan(AT)stat.wisc.edu), Feb 01 2007
a(n)=A000108(n)*A000108(n+2)-A000108(n+1)^2. - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Apr 11 2007
|
|
EXAMPLE
|
Example: a(2)=3 counts EWEW, EEWW, ENSW.
|
|
CROSSREFS
|
See 138349 for another version.
Adjacent sequences: A005697 A005698 A005699 this_sequence A005701 A005702 A005703
Sequence in context: A121687 A154757 A074535 this_sequence A088717 A111538 A088716
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
EXTENSIONS
|
More terms from James A. Sellers (sellersj(AT)math.psu.edu), Dec 24 1999
Corrected by Vladeta Jovovic (vladeta(AT)Eunet.yu), May 23 2004
Better definition from David Callan (callan(AT)stat.wisc.edu), Sep 18 2007
|
|
|
Search completed in 0.002 seconds
|
