|
%I #118 Feb 17 2022 00:10:10
%S 1,2,23,377,7229,151491,3361598,77635093,1846620581,44930294909,
%T 1113015378438,27976770344941,711771461238122,18293652115906958,
%U 474274581883631615,12388371266483017545,325714829431573496525,8613086428709348334675,228925936056388155632081
%N Duchon's numbers: the number of paths of length 5*n from the origin to the line y = 2*x/3 with unit East and North steps that stay below the line or touch it.
%C A generalization of the ballot numbers.
%H Alois P. Heinz, <a href="/A060941/b060941.txt">Table of n, a(n) for n = 0..500</a>
%H C. Banderier, <a href="http://algo.inria.fr/banderier/index.html">Home page</a>
%H Cyril Banderier and Philippe Flajolet, <a href="http://dx.doi.org/10.1016/S0304-3975(02)00007-5">Basic Analytic Combinatorics of Lattice Paths</a>, Theoret. Comput. Sci. 281 (2002), 37-80.
%H D. Bevan, D. Levin, P. Nugent, J. Pantone, and L. Pudwell, <a href="http://arxiv.org/abs/1510.08036">Pattern avoidance in forests of binary shrubs</a>, arXiv preprint arXiv:1510:08036 [math.CO], 2015.
%H Daniel Birmajer, Juan B. Gil, Peter R. W. McNamara, and Michael D. Weiner, <a href="http://arxiv.org/abs/1602.03550">Enumeration of colored Dyck paths via partial Bell polynomials</a>, arXiv:1602.03550 [math.CO], 2016.
%H M. T. L. Bizley, <a href="http://bergeron.math.uqam.ca/wp-content/uploads/2014/09/Bizley.pdf">Derivation of a new formula for the number of minimal lattice paths from (0, 0) to (km, kn) having just t contacts with the line my = nx and having no points above this line; and a proof of Grossman's formula for the number of paths which may touch but do not rise above this line</a>, Journal of the Institute of Actuaries, Vol. 80, No. 1 (1954): 55-62.
%H M. T. L. Bizley, <a href="/A060941/a060941.pdf">Derivation of a new formula for the number of minimal lattice paths from (0, 0) to (km, kn) having just t contacts with the line my = nx and having no points above this line; and a proof of Grossman's formula for the number of paths which may touch but do not rise above this line</a>, Journal of the Institute of Actuaries, Vol. 80, No. 1 (1954): 55-62. [Cached copy]
%H M. T. L. Bizley, <a href="/A060941/a060941.png">Annotated copy of page 59</a>
%H M. Bousquet-Mélou and A. Jehanne, <a href="https://arxiv.org/abs/math/0504018">Polynomial equations with one catalytic variable, algebraic series and map enumeration</a>, arXiv:math/0504018 [math.CO], 2005.
%H P. Duchon, <a href="http://www.labri.fr/perso/duchon/">Home Page</a>
%H Philippe Duchon, <a href="http://dx.doi.org/10.1016/S0012-365X(00)00150-3">On the enumeration and generation of generalized Dyck words</a>, Discrete Mathematics 225, 2000, 121-135.
%H Bryan Ek, <a href="https://arxiv.org/abs/1803.10920">Lattice Walk Enumeration</a>, arXiv:1803.10920 [math.CO], 2018.
%H Bryan Ek, <a href="https://arxiv.org/abs/1804.05933">Unimodal Polynomials and Lattice Walk Enumeration with Experimental Mathematics</a>, arXiv:1804.05933 [math.CO], 2018.
%H P. Flajolet, <a href="http://algo.inria.fr/flajolet/">Home page</a>
%H Don Knuth, <a href="https://www.youtube.com/watch?v=P4AaGQIo0HY">20th Anniversary Christmas Tree Lecture</a> [A060941 is mentioned after about 65 minutes - _N. J. A. Sloane_, Dec 09 2014]
%H Michael Wallner, <a href="http://dmg.tuwien.ac.at/mwallner/files/Dissertation_Wallner.pdf"> Combinatorics of lattice paths and tree-like structures</a> (Dissertation, Institut für Diskrete Mathematik und Geometrie, Technische Universität Wien), 2016.
%F a(n) = Sum_{i=0..n} 1/(5*n+i+1) * C(5*n+1, n-i) * C(5*n+2*i, i).
%F a(n) = Sum_{i=0..2*n} (-1)^i/(5*i+1) * C((5*i+1)/2, i) * 1/(1+5*(2*n-i)) * C((1+5*(2*n-i))/2, 2*n-i).
%F G.f. A(z) satisfies: A(z) = 1+2*z*A^5-z*A^6+z*A^7+z^2*A^10. [Corrected by _Bryan T. Ek_, Oct 30 2017]
%F G.f.: A(z) = exp(C(5,2)*z/5 + C(10,4)*z^2/10 + C(15,6)*z^3/15 + ...). - _Don Knuth_, Oct 05 2014
%F Recurrence: 216*(n-1)*n*(2*n-1)*(3*n-4)*(3*n-2)*(3*n-1)*(3*n+1)*(6*n-1)*(6*n+1)*(5625*n^4 - 38550*n^3 + 97425*n^2 - 107784*n + 44044)*a(n) = 540*(n-1)*(3*n-4)*(3*n-2)*(126562500*n^10 - 1373625000*n^9 + 6557484375*n^8 - 18192221250*n^7 + 32549973750*n^6 - 39248008800*n^5 + 32203028675*n^4 - 17641491134*n^3 + 6113558828*n^2 - 1191132600*n + 96112128)*a(n-1) - 450*(5*n-9)*(5*n-8)*(5*n-7)*(5*n-6)*(63281250*n^9 - 718453125*n^8 + 3556125000*n^7 - 10046426250*n^6 + 17765816250*n^5 - 20240090325*n^4 + 14698993900*n^3 - 6468702396*n^2 + 1533535184*n - 142988160)*a(n-2) + 78125*(n-2)*(5*n-14)*(5*n-13)*(5*n-12)*(5*n-11)*(5*n-9)*(5*n-8)*(5*n-7)*(5*n-6)*(5625*n^4 - 16050*n^3 + 15525*n^2 - 6084*n + 760)*a(n-3). - _Vaclav Kotesovec_, Oct 05 2014
%F Asymptotics (Duchon, 2000): a(n) ~ c * (3125/108)^n / n^(3/2), where c = 0.0876612192439026461763141944768209255550234422281635788... (constant corrected, in the reference "On the enumeration and generation of generalized Dyck words", p.132 is a wrong value 0.0887). - _Vaclav Kotesovec_, Oct 05 2014, c = sqrt(5*(10^(2/3) - 5^(1/3)/2^(2/3) - 2))/(18*sqrt(Pi)). - _Vaclav Kotesovec_, Sep 16 2021
%F a(n) = Gamma(n+4/5)*Gamma(n+3/5)*Gamma(n+2/5)*3125^n*hypergeom([-n, (5/2)*n+1, (5/2)*n+1/2], [5*n+2, 4*n+2], -4)*Gamma(n+1/5)/ (Pi^2*csc((2/5)*Pi)*csc((1/5)*Pi)*Gamma(4*n+2)). - _Robert Israel_, Oct 05 2014
%F a(n) = A002294(n)*hypergeom([-n,5*n/2+1/2,5*n/2+1],[4*n+2,5*n+2],-4). - _Peter Luschny_, Oct 05 2014
%F O.g.f. A(x) satisfies: A(x)^5 = 1/x*series reversion( x/((1+x)*C(x))^5 ), where C(x) = (1 - sqrt(1 - 4*x))/(2*x) is the o.g.f. for the Catalan numbers A000108. See A001450. - _Peter Bala_, Oct 05 2015
%F The sequence defined by b(n) := [x^n] A(x)^n begins [1, 2, 50, 1415, 42258, 1300727, 40820837, 1298493730, ...] and conjecturally satisfies the congruence b(p) == b(1) (mod p^3) for prime p >= 7 (checked up to p = 101). - _Peter Bala_, Sep 12 2021
%p A060941 := n -> hypergeom([-n,5*n/2+1/2,5*n/2+1],[4*n+2,5*n+2],-4)* binomial(5*n,n)/(4*n+1); seq(simplify(A060941(n)),n=0..18); # _Peter Luschny_, Oct 05 2014
%t a[n_] := ((5n)!*(5n + 1)!*HypergeometricPFQRegularized[{-n, 5n/2 + 1/2, 5n/2 + 1}, {4n + 2, 5n + 2}, -4])/n!; a /@ Range[0, 16]
%t (* _Jean-François Alcover_, Jun 30 2011, after given formula *)
%o (Sage)
%o A060941 = lambda n : hypergeometric([-n,5*n/2+1/2,5*n/2+1],[4*n+2,5*n+2],-4)*gamma(1+5*n)/(gamma(1+n)*gamma(2+4*n))
%o [A060941(n).simplify() for n in range(19)] # _Peter Luschny_, Oct 05 2014
%o (Magma) [&+[1/(5*n+i+1)*Binomial(5*n+1, n-i)*Binomial(5*n+2*i, i): i in [0..n]]: n in [0..30]]; // _Vincenzo Librandi_, Feb 12 2016
%Y Cf. A000108, A001450, A001764, A002294, A300386 - A300389, A322634.
%Y See A293946 for a closely related sequence, also from the Bizley paper.
%K nice,nonn
%O 0,2
%A _Philippe Flajolet_, May 12 2001
|
