login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 6
1, 2, 23, 377, 7229, 151491, 3361598, 77635093, 1846620581, 44930294909, 1113015378438, 27976770344941, 711771461238122, 18293652115906958, 474274581883631615, 12388371266483017545, 325714829431573496525, 8613086428709348334675, 228925936056388155632081 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

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, Philippe Flajolet, Basic Analytic Combinatorics of Lattice Paths, Theoret. Comput. Sci. 281 (2002), 37-80.

D. Bevan, D. Levin, P. Nugent, J. Pantone, 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, 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.

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.

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 wrong value 0.0887). - Vaclav Kotesovec, Oct 05 2014

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

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

PROG

(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

(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

CROSSREFS

Cf. A000108, A001450, A002294.

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

Sequence in context: A234868 A239109 A266923 * A219890 A119774 A074649

Adjacent sequences:  A060938 A060939 A060940 * A060942 A060943 A060944

KEYWORD

nice,nonn

AUTHOR

Philippe Flajolet, May 12 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 21 12:43 EST 2017. Contains 295001 sequences.