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

1, 2, 23, 377, 7229, 151491, 3361598, 77635093, 1846620581, 44930294909, 1113015378438, 27976770344941, 711771461238122, 18293652115906958, 474274581883631615, 12388371266483017545, 325714829431573496525, 8613086428709348334675, 228925936056388155632081

Offset: 0

Author

Philippe Flajolet, May 12 2001

Keywords

• nice
• nonn

Comments

A generalization of the ballot numbers.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..500
• C. Banderier, Home page
• Cyril Banderier and Philippe Flajolet, Basic Analytic Combinatorics of Lattice Paths, Theoret. Comput. Sci. 281 (2002), 37-80.
• D. Bevan, D. Levin, P. Nugent, J. Pantone, and L. Pudwell, Pattern avoidance in forests of binary shrubs, arXiv preprint arXiv:1510:08036 [math.CO], 2015.
• Daniel Birmajer, Juan B. Gil, Peter R. W. McNamara, and Michael D. Weiner, Enumeration of colored Dyck paths via partial Bell polynomials, arXiv:1602.03550 [math.CO], 2016.
• M. T. L. Bizley, 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, Journal of the Institute of Actuaries, Vol. 80, No. 1 (1954): 55-62.
• M. T. L. Bizley, 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, Journal of the Institute of Actuaries, Vol. 80, No. 1 (1954): 55-62. [Cached copy]
• M. T. L. Bizley, Annotated copy of page 59
• M. Bousquet-Mélou and A. Jehanne, Polynomial equations with one catalytic variable, algebraic series and map enumeration, arXiv:math/0504018 [math.CO], 2005.
• P. Duchon, Home Page
• Philippe Duchon, On the enumeration and generation of generalized Dyck words, Discrete Mathematics 225, 2000, 121-135.
• Bryan Ek, Lattice Walk Enumeration, arXiv:1803.10920 [math.CO], 2018.
• Bryan Ek, Unimodal Polynomials and Lattice Walk Enumeration with Experimental Mathematics, arXiv:1804.05933 [math.CO], 2018.
• P. Flajolet, Home page
• Don Knuth, 20th Anniversary Christmas Tree Lecture [A060941 is mentioned after about 65 minutes - _N. J. A. Sloane_, Dec 09 2014]
• Michael Wallner, Combinatorics of lattice paths and tree-like structures (Dissertation, Institut für Diskrete Mathematik und Geometrie, Technische Universität Wien), 2016.

Crossrefs

Cf. A000108, A001450, A001764, A002294, A300386 - A300389, A322634.

See A293946 for a closely related sequence, also from the Bizley paper.

Programs

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

Maple

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

Mathematica

a[n_] := ((5n)!*(5n + 1)!*HypergeometricPFQRegularized[{-n, 5n/2 + 1/2, 5n/2 + 1}, {4n + 2, 5n + 2}, -4])/n!; a /@ Range[0, 16]
(* Jean-François Alcover, Jun 30 2011, after given formula *)

Sage

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))
[A060941(n).simplify() for n in range(19)] # Peter Luschny, Oct 05 2014

Formula

a(n) = Sum_{i=0..n} 1/(5*n+i+1) * C(5*n+1, n-i) * C(5*n+2*i, i).

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

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]

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

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

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

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

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

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

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). [Added 23 Oct 2024: More generally, let r be an integer and s a positive integer and define a sequence u(n) by u(n) = [x^(s*n)] A(x)^(r*n). Then we conjecture that the supercongruences u(n*p^k) == u(n*p^(k-1)) (mod p^(3*k)) hold for all primes p >= 7 and positive integers n and k.] - Peter Bala, Sep 12 2021

Inductively define a family of sequences {a(i,n) : n >= 0}, i >= 1, by setting a(1,n) = a(n) and, for i >= 2, a(i,n) = [x^n] ( exp(Sum_{k >= 1} a(i-1,k)*x^k/k) )^n. We conjecture that the sequences {a(i,n) : n >= 0}, i >= 2, also satisfy the supercongruences u(n*p^k) == u(n*p^(k-1)) (mod p^(3*k)) for primes p >= 7 and positive integers n and k. - Peter Bala, Oct 24 2024