A104184 -id:A104184 - cp's OEIS frontend

A187430 Number of nonnegative walks of n steps with step sizes 1 and 2, starting and ending at 0.

1, 0, 2, 2, 11, 24, 93, 272, 971, 3194, 11293, 39148, 139687, 497756, 1798002, 6517194, 23807731, 87336870, 322082967, 1192381270, 4431889344, 16527495396, 61831374003, 231973133544, 872598922407, 3290312724374, 12434632908623, 47089829065940, 178672856753641

Offset: 0

Franklin T. Adams-Watters, Mar 09 2011

Equivalently, the number of paths from (0,0) to (n,0) using steps of the form (1,2),(1,1),(1,-1) or (1,-2) and staying on or above the x-axis.
Self-convolution of A055113. - Paul D. Hanna, May 31 2015
Logarithmic derivative yields A092765 (with offset 1). - Paul D. Hanna, May 31 2015

			The 11 length-4 walks are 0,2,4,2,0; 0,2,3,2,0; 0,2,3,1,0; 0,2,1,2,0; 0,2,0,2,0; 0,2,0,1,0; 0,1,3,2,0; 0,1,3,1,0; 0,1,2,1,0; 0,1,0,2,0; and 0,1,0,1,0.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
C. Banderier, Analytic combinatorics of random walks and planar maps, PhD Thesis, 2001 , Example 11.
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.
Jean-Luc Baril and José L. Ramírez, Knight's paths towards Catalan numbers, Univ. Bourgogne Franche-Comté (2022).

Cf. A126120, A104184, A001006, A055113, A092765.

a:= proc(n) option remember; `if`(n<3, (n-1)*(3*n-2)/2,
     ((n+1)*(115*n^3-137*n^2-10*n+8) *a(n-1)
      +4*(2*n-1)*(5*n^3+36*n^2-26*n-12) *a(n-2)
      -36*(n-2)*(2*n-1)*(2*n-3)*(5*n+1) *a(n-3))
      / (2*(5*n-4)*(2*n+1)*(n+2)*(n+1)))
    end:
seq(a(n), n=0..30); # Alois P. Heinz, May 16 2013

a[n_] := (Sum[Binomial[n+1, l]*Sum[Binomial[n-2*i-1, 2*l-1]*Binomial[n-l+1, i], {i, 0, (n-1)/2}], {l, 0, n+1}] + (((-1)^n+1)*Binomial[n+1, n/2])/2)/(n+1); Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Oct 24 2016, after Vladimir Kruchinin *)

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

al(n)={local(r,p);
r=vector(n);r[1]=p=1;
for(k=2,n,p*=1+x+x^3+x^4;p=(p-polcoeff(p,0)-polcoeff(p,1)*x)/x^2;r[k]=polcoeff(p,0));
r}

G.f.: 1/(2*x)-(1+(1-4*x)^(1/2))*((2+2*(1-4*x)^(1/2)+12*x)^(1/2)-2)/(8*x^2). - Mark van Hoeij, May 16 2013
a(n) ~ (3/sqrt(5)-1) * 2^(2*n+1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 09 2014
G.f.: exp( Sum_{n>=1} A092765(n)*x^n/n ), where A092765(n) = Sum_{k=0..n} binomial(n,k)*binomial(n,2*n-3*k). - Paul D. Hanna, May 31 2015
a(n) = ((Sum_{l=0..n+1} (C(n+1,l)*Sum_{i=0..(n-1)/2}(C(n-2*i-1,2*l-1)*C(n-l+1,i))))+(((-1)^n+1)/2*C(n+1,n/2)))/(n+1). - Vladimir Kruchinin, Jun 26 2015
Sum_{n>=0} a(n)*x^(n+1) is the compositional inverse of x*(1-x^2)^2/(1+x^3)^2. - Ira M. Gessel, Sep 19 2017
Conjecture: 1 + Sum_{n>=0} a(n)*(-1)^n x^(n+1)/(1-x)^(2*n+2) = C(x), the g.f. for the Catalan numbers A000108. - Benedict W. J. Irwin, Jan 13 2017
D-finite with recurrence 2*(2*n+1)*(n+2)*(n+1)*a(n) +(n+1)*(n^2-27*n+2)*a(n-1) +2*(-73*n^3+204*n^2-167*n+6)*a(n-2) +12*(n-3)*(2*n-3)*(4*n-7)*a(n-3) +216*(2*n-5)*(n-3)*(2*n-3)*a(n-4)=0. - R. J. Mathar, Sep 29 2020
From Seiichi Manyama, Jan 17 2024: (Start)
G.f.: (1/x) * Series_Reversion( x * (1-x)^2 / (1-x+x^2)^2 ).
a(n) = (1/(n+1)) * Sum_{k=0..floor(n/2)} binomial(2*n+2,k) * binomial(n-k-1,n-2*k). (End)

A204213 T(n,k) = Number of length n+1 nonnegative integer arrays starting and ending with 0 with adjacent elements differing by no more than k.

Original entry on oeis.org

1, 1, 2, 1, 3, 4, 1, 4, 9, 9, 1, 5, 16, 32, 21, 1, 6, 25, 78, 120, 51, 1, 7, 36, 155, 404, 473, 127, 1, 8, 49, 271, 1025, 2208, 1925, 323, 1, 9, 64, 434, 2181, 7167, 12492, 8034, 835, 1, 10, 81, 652, 4116, 18583, 51945, 72589, 34188, 2188, 1, 11, 100, 933, 7120, 41363, 164255, 387000, 430569, 147787, 5798

Offset: 1

R. H. Hardin, Jan 12 2012

Table starts
...1....1.....1......1.......1.......1........1........1........1.........1
...2....3.....4......5.......6.......7........8........9.......10........11
...4....9....16.....25......36......49.......64.......81......100.......121
...9...32....78....155.....271.....434......652......933.....1285......1716
..21..120...404...1025....2181....4116.....7120....11529....17725.....26136
..51..473..2208...7167...18583...41363....82440...151125...259459....422565
.127.1925.12492..51945..164255..431445...991152..2057553..3945655...7098949
.323.8034.72589.387000.1493142.4629851.12262470.28832499.61766005.122779448

			Some solutions for n=5 k=3
..0....0....0....0....0....0....0....0....0....0....0....0....0....0....0....0
..3....0....1....2....2....2....1....3....0....3....1....2....2....3....2....1
..5....0....4....5....1....1....4....4....2....4....0....4....5....1....0....1
..5....1....2....4....3....0....1....1....3....1....1....2....5....3....2....2
..2....3....1....2....0....2....0....0....1....3....1....2....2....1....2....1
..0....0....0....0....0....0....0....0....0....0....0....0....0....0....0....0

R. H. Hardin, Table of n, a(n) for n = 1..9999

Column 1 is A001006; column 2 is A104184; column 3 is A204208.

Row 4 is A051662.

T[n_, k_] := T[n, k] = If[n == 0, 1, Sum[(Sum[Binomial[i, j]*(-1)^j* Binomial[-j*(2*k + 1) + i*(k + 1) - 1, i*k - j*(2*k + 1)], {j, 0, (i*k)/(2*k + 1)}])*T[n - i, k], {i, 1, n}]/n];
Table[T[n - k + 1, k], {n, 1, 11}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Sep 24 2019, after Vladimir Kruchinin *)

T(n,k):=if n=0 then 1 else sum((sum(binomial(i,j)*(-1)^j*binomial(-j*(2*k+1)+i*(k+1)-1,i*k-j*(2*k+1)),j,0,(i*k)/(2*k+1)))*T(n-i,k),i,1,n)/n;  /* Vladimir Kruchinin, Apr 06 2017 */

{L(n,k)=polcoeff( ( (1-x^(2*k+1))/(1-x) +x*O(x^(k*n)) )^n, k*n)}
{T(n,k)=polcoeff(exp(sum(m=1, n, L(m,k)*x^m/m)+x*O(x^n)), n)}
for(n=1, 10,for(k=1,10, print1(T(n,k), ", "));print("")) \\ Paul D. Hanna, Aug 01 2013

Empirical for rows:
T(1,k) = 1
T(2,k) = k + 1
T(3,k) = k^2 + 2*k + 1
T(4,k) = (4/3)*k^3 + (7/2)*k^2 + (19/6)*k + 1
T(5,k) = (23/12)*k^4 + (37/6)*k^3 + (91/12)*k^2 + (13/3)*k + 1
T(6,k) = (44/15)*k^5 + (133/12)*k^4 + 17*k^3 + (161/12)*k^2 + (167/30)*k + 1
T(7,k) = (841/180)*k^6 + (101/5)*k^5 + (1325/36)*k^4 + (73/2)*k^3 + (946/45)*k^2 + (34/5)*k + 1
...
G.f. for column k: exp( Sum_{n>=1} L(n,k)*x^n/n ) - 1, where L(n,k) = central coefficient of (1+x+x^2+x^3+...+x^(2*k))^n. - Paul D. Hanna, Aug 01 2013
T(n,k):=Sum_{i=1..n}((Sum_{j=0..(i*k)/(2*k+1)}(binomial(i,j)*(-1)^j*binomial(-j*(2*k+1)+i*(k+1)-1,i*k-j*(2*k+1))))*T(n-i,k))/n, T(0,k)=1. - Vladimir Kruchinin, Apr 06 2017

A104632 1/n times A104631(n), the coefficient of x^(2n+1) in the expansion of (1+x+x^2+x^3+x^4)^n.

Original entry on oeis.org

1, 2, 6, 20, 73, 281, 1125, 4635, 19525, 83710, 364070, 1602327, 7123041, 31937010, 144255802, 655804649, 2998354717, 13777825186, 63596593430, 294743653360, 1371017707245, 6398580086645, 29952930770185, 140604572777250, 661708404611603, 3121439743413256, 14756658303857332

Offset: 1

T. D. Noe, Mar 17 2005

This sequence may be viewed as a higher-order form of the Motzkin numbers, A001006, which are 1/n times the coefficient of x^(n+1) in the expansion of (1+x+x^2)^n. According to Superseeker, this sequence is the INVERT transform of A104184, which is related to Motzkin numbers also. See A104631 for additional comments.

Alternatively, this sequence corresponds to the number of positive walks with n steps {-2,-1,0,1,2} starting at the origin, ending at altitude 1, and staying strictly above the x-axis. - David Nguyen, Dec 01 2016

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.

Cf. A005717 (coefficient of x^(n+1) in the expansion of (1+x+x^2)^n).

f=1; Table[f=Expand[f(x^4+x^3+x^2+x+1)]; Coefficient[f, x, 2n+1]/n, {n, 30}]
a[ n_] := If[ n < 1, 0, Coefficient[ (1 + x + x^2 + x^3 + x^4)^n, x, 2 n + 1] / n]; (* Michael Somos, Dec 01 2016 *)

a(n):=sum((-1)^i*binomial(n,i)*binomial(3*n-5*i,n-1),i,0,(2*n+1)/5)/n; /* Vladimir Kruchinin, Apr 06 2017 */

a(n) = polcoeff((1+x+x^2+x^3+x^4)^n, 2*n+1)/n \\ Michel Marcus, Sep 24 2016

a(n) = Sum_{i=0..(2*n+1)/5}((-1)^i*binomial(n,i)*binomial(3*n-5*i,n-1))/n. - Vladimir Kruchinin, Apr 06 2017

Conjecture: 2*n*(2*n+1)*(n-1)*a(n) -(n-1)*(19*n^2-19*n+2)*a(n-1) -5*(n-2)*(2*n^2-3*n-1)*a(n-2) +25*n*(n-2)*(n-3)*a(n-3)=0. - R. J. Mathar, Jul 23 2017

cp's OEIS Frontend

A187430 Number of nonnegative walks of n steps with step sizes 1 and 2, starting and ending at 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

A204213 T(n,k) = Number of length n+1 nonnegative integer arrays starting and ending with 0 with adjacent elements differing by no more than k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

A104632 1/n times A104631(n), the coefficient of x^(2n+1) in the expansion of (1+x+x^2+x^3+x^4)^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula