|
| |
|
|
A005700
|
|
The number of closed walks of 2n unit steps north, east, south, or west starting and ending at the origin and confined to the first octant.
(Formerly M2975)
|
|
11
| |
|
|
1, 1, 3, 14, 84, 594, 4719, 40898, 379236, 3711916, 37975756, 403127256, 4415203280, 49671036900, 571947380775, 6721316278650, 80419959684900, 977737404590100, 12058761323277900, 150656212896017400
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| 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
In Sloane and Plouffe (1995) this was incorrectly described as "Dyck paths".
|
|
|
REFERENCES
| 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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
| Vincenzo Librandi, Table of n, a(n) for n = 0..200
N. Bonichon, A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths, Discr. Math., 298 (2005), 104-114.
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, arxiv:math.CO/0501230
Kiran S. Kedlaya and Andrew V. Sutherland, Hyperelliptic curves, L-polynomials and random matrices, arXiv:0803.4462
Alec Mihailovs, Enumeration of walks on lattices, (1998).
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.
Index entries for sequences related to Young tableaux.
|
|
|
FORMULA
| G.f.: 3F2( [ 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
G.f.: (1/(4*x^2)) * (1+6*x - (16*x-1)^4*hypergeom([5/2, 7/2],[2],16*x)) [From Mark van Hoeij (hoeij(AT)math.fsu.edu), Nov 02 2009]
|
|
|
EXAMPLE
| Example: a(2)=3 counts EWEW, EEWW, ENSW.
|
|
|
MATHEMATICA
| CoefficientList[ Series[1 + (HypergeometricPFQ[{1, 1/2, 3/2}, {3, 4}, 16 x] - 1), {x, 0, 19}], x]
|
|
|
PROG
| (MAGMA[6*Factorial(2*n)*Factorial(2*n+2)/(Factorial(n)*Factorial(n+1)*Factorial(n+2)*Factorial(n+3)): n in [0..25]]; // Vincenzo Librandi, Aug 04 2011
(PARI) a(n)=6*binomial(2*n+2, n)*(2*n)!/(n+1)!/(n+3)! \\ Charles R Greathouse IV, Aug 04 2011
|
|
|
CROSSREFS
| A column of the triangle in A179898. A diagonal of the triangle in A185249.
Row sums of A193691, A193692. - Alois P. Heinz, Aug 03 2011
See A138349 for another version.
Sequence in context: A154757 A074535 A190761 * A088717 A111538 A160881
Adjacent sequences: A005697 A005698 A005699 * A005701 A005702 A005703
|
|
|
KEYWORD
| nonn,walk,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.rs), May 23 2004
Better definition from David Callan (callan(AT)stat.wisc.edu), Sep 18 2007
|
| |
|
|
