A104184 a(n) is the number of paths from (0,0) to (n,0) using steps of the form (1,2),(1,1),(1,0),(1,-1) or (1,-2) and staying above the x-axis. Also, a(n) is the number of possible combinations of balls on the lawn after n turns, using a Motzkin variation of the (4,2)-case of the tennis ball problem considered by D. Merlini, R. Sprugnoli and M. C. Verri.

1, 1, 3, 9, 32, 120, 473, 1925, 8034, 34188, 147787, 647141, 2864508, 12796238, 57615322, 261197436, 1191268350, 5462080688, 25162978925, 116414836445, 540648963645, 2519574506595, 11779011525030, 55225888341334, 259612579655392, 1223396051745310

Offset: 0

Author

Nicholas Biller (billern(AT)gmail.com), Mar 11 2005

Keywords

• nonn

Comments

The (4,2)-case of the Motzkin Tennis Ball Problem is a variation of the Tennis Ball Problem that generates a(n). On each turn, i, four balls labeled i are placed in the bucket and then any two are removed and placed on the lawn. We consider all possible combinations of balls on the lawn after n turns.

The number of ways to choose n numbers, ranging from 0 to 4, so that their sum is 2n and so that when you take k numbers from the left, the sum of these numbers is <= 2k (e.g. the combination of {141} is impossible, for 1+4 > 2k). Thus a(1) = {2}; a(2) = {04}, {13} and {22}; a(3) = {024}, {033}, {042}, {114}, {123}, {132}, {204}, {213} and {222}. - Joost Vermeij (joost_vermeij(AT)hotmail.com), Jun 12 2005

Examples

			a(3) = 9, since the possible combinations of balls on the lawn after 3 turns is 111122, 111123, 111133, 111222, 111223, 111233, 112222, 112223, 112233, if on each turn there are 4 identically labeled balls received and 2 selected.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1437
• C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen, and M. Wallner, Explicit formulas for enumeration of lattice paths: basketball and the kernel method, arXiv preprint arXiv:1609.06473 [math.CO], 2016.
• AJ Bu and Doron Zeilberger, Using Symbolic Computation to Explore Generalized Dyck Paths and Their Areas, arXiv:2305.09030 [math.CO], 2023.
• P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 512
• D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), pp. 307-344.

Crossrefs

Cf. A066357, A001006, A005191.

Programs

Maple

a:= proc(n) option remember; `if`(n<5, [1, 1, 3, 9, 32][n+1],
      ((n+1)*(43*n^3-48*n^2-7*n+2)*a(n-1)
      -(124*n^4-370*n^3+255*n^2+15*n-14)*a(n-2)
      +5*(n-2)*(2*n^3-52*n^2+65*n-1)*a(n-3)
      +25*(n-2)*(n-3)*(8*n^2-8*n-1)*a(n-4)
      -125*n*(n-2)*(n-3)*(n-4)*a(n-5))/
       (2*(n-1)*(n+1)*(n+2)*(2*n+1)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 11 2013

Mathematica

CoefficientList[Series[(1 + x + Sqrt[1 - 6*x + 5*x^2] - Sqrt[2]*Sqrt[1 + Sqrt[1 - 6*x + 5*x^2] + x*(-2 - 5*x + Sqrt[1 - 6*x + 5*x^2])])/(4*x^2), {x, 0, 20}], x] (* Vaclav Kotesovec, Sep 09 2014 *)

Maxima

a(n):=((sum(binomial(n+1,l)*sum(binomial(i,2*l-1)*sum(binomial(j,n-j-i-1) *binomial(n-l+1,j),j,0,n-l+1),i,0,n-1),l,1,n+1))+sum(binomial(j,n-j) *binomial(n+1,j),j,0,n+1))/(n+1); /* Vladimir Kruchinin, Jun 26 2015 */

PARI

{a(n)=local(A=1);A=exp(sum(m=1,n+1,polcoeff(((1-x^5)/(1-x) +O(x^(2*m+1)))^m, 2*m)*x^m/m)+x*O(x^n));polcoeff(A,n)} /* Paul D. Hanna */

Formula

G.f. (for offset 1): (1/(4*x))*(1+x+sqrt((1-6*x+5*x^2)) - sqrt(2)*sqrt(1+sqrt((1-6*x+5*x^2)) + x*(-2-5*x+sqrt((1-6*x+5*x^2))))). - N-E. Fahssi, Jan 10 2008

Let M be the infinite pentadiagonal matrix with all 1's in the 1st and 2nd subdiagonals, the main diagonal, and the 1st and 2nd superdiagonals, and with the rest 0's. V = vector [1,0,0,0,...]. The sequence starting with offset 1 = iterates of M*V, leftmost column. - Gary W. Adamson, Jun 06 2011

From Paul D. Hanna, Oct 19 2011: (Start)

Logarithmic derivative yields the central pentanomial coefficients (A005191).

G.f.: exp( Sum_{n>=1} A005191(n)*x^n/n ).

G.f.: (1/x)*Series_Reversion(x*(1-x^5)*(1-x^2)*(1-x)/(1-x^10)).

G.f. satisfies: A(x) = (1-x^10*A(x)^10)/((1-x^5*A(x)^5)*(1-x^2*A(x)^2)*(1-x*A(x))). (See formula from Michael Somos in A005191.) (End)

a(n) ~ (3-sqrt(5)) * 5^(n+1) / (4 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 09 2014

a(n) = ((Sum_{l=1..n+1} (C(n+1,l)*Sum_{i=0..n-1} (C(i,2*l-1) * Sum_{j=0..n-l+1} (C(j,n-j-i-1)*C(n-l+1,j))))) + Sum_{j=0..n+1} (C(j,n-j) * C(n+1,j)))/(n+1). - Vladimir Kruchinin, Jun 26 2015

-2*(n-1)*(2*n+1)*(n+2)*(n+1)*a(n) +(n+1)*(43*n^3-48*n^2-7*n+2)*a(n-1) +(-124*n^4+370*n^3-255*n^2-15*n+14)*a(n-2) +5*(n-2)*(2*n^3-52*n^2+65*n-1)*a(n-3) +25*(n-2)*(n-3)*(8*n^2-8*n-1)*a(n-4) -125*n*(n-2)*(n-3)*(n-4)*a(n-5)=0. - R. J. Mathar, Jul 23 2017