A108424 -id:A108424 - cp's OEIS frontend

A002003 a(n) = 2 * Sum_{k=0..n-1} binomial(n-1, k)*binomial(n+k, k).

0, 2, 8, 38, 192, 1002, 5336, 28814, 157184, 864146, 4780008, 26572086, 148321344, 830764794, 4666890936, 26283115038, 148348809216, 838944980514, 4752575891144, 26964373486406, 153196621856192, 871460014012682, 4962895187697048, 28292329581548718

Offset: 0

N. J. A. Sloane

nonn

a(n) is the number of order-preserving partial self maps of {1,...,n}. For example, a(2) = 8 because there are 8 order-preserving partial self maps of {1,2}: (1 2), (1 1), (2 2), (1 -), (2 -), (- 1), (- 2), (- -). Here for example (2 -) represents the partial map which maps 1 to 2 but does not include 2 in its domain. - James East, Oct 25 2005
From Peter Bala, Mar 02 2020: (Start)
For fixed m = 1,2,3,..., we conjecture that the sequence b(n) := a(m*n) satisfies a recurrence of the form P(2*m,n)*b(n+1) + P(2*m,-n)*b(n-1) = Q(2*m,n)*b(n), where the polynomials P(2*m,n) and Q(2*m,n) have degree 2*m. Conjecturally, the polynomial Q(2*m,n) is an even function of n; its 2*m zeros seem to belong to the interval [-1, 1] and 2*m - 2 of these zeros appear to lie close to the rational numbers of the form +-(2*k + 1)/(2*m), where 0 <= k <= m - 2. Cf. A103885. (End)
a(n), n>0, is the number of points at L1 distance = n from any given point in Z^n.  The sequence is also the difference between the central diagonal (A001850) and +-1 diagonal (A002002) of the Delannoy number triangle (A008288).  - Shel Kaphan, Feb 15 2023

			G.f. = 2*x + 8*x^2 + 38*x^3 + 192*x^4 + 1002*x^5 + 5336*x^6 + 28814*x^7 + ...

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Seiichi Manyama, Table of n, a(n) for n = 0..1000 (terms 0..200 from T. D. Noe)
Peter Bala, A supercongruence for A002003
J. Brzozowski, M. Szykula, Large Aperiodic Semigroups, arXiv preprint arXiv:1401.0157 [cs.FL], 2013-2014.
Milan Janjić, On Restricted Ternary Words and Insets, arXiv:1905.04465 [math.CO], 2019.
G. Rutledge and R. D. Douglass, Integral functions associated with certain binomial coefficient sums, Amer. Math. Monthly, 43 (1936), 27-32.

Cf. A002002, A006318, A027307, A108424, A103885.

A064861 := proc(n,k) option remember; if n = 1 then 1; elif k = 0 then 0; else A064861(n,k-1)+(3/2-1/2*(-1)^(n+k))*A064861(n-1,k); fi; end; seq(A064861(i,i-1),i=1..40);

Flatten[{0,Table[SeriesCoefficient[((1+x)/Sqrt[1-6*x+x^2]-1)/2,{x,0,n}],{n,1,20}]}] (* Vaclav Kotesovec, Oct 04 2012 *)
a[ n_] := If[ n < 1, 0, Hypergeometric2F1[ n, -n, 1, -1]]; (* Michael Somos, Aug 24 2014 *)
Table[2*Sum[Binomial[n-1,k]Binomial[n+k,k],{k,0,n-1}],{n,0,30}] (* Harvey P. Dale, Sep 18 2024 *)

{a(n) = if( n<1, 0, polcoeff( ((1 - x^2) / (1 - x)^2 + x * O(x^n))^n, n))} /* Michael Somos, Sep 24 2003 */

from math import comb
def A002003(n): return sum(comb(n,k)**2*k<Chai Wah Wu, Mar 22 2023

a(n) = 2*A047781(n).
From Vladeta Jovovic, Mar 28 2004: (Start)
G.f.: ((1+x)/sqrt(1-6*x+x^2)-1)/2.
E.g.f.: exp(3*x)*(2*BesselI(0, 2*sqrt(2)*x)+sqrt(2)*BesselI(1, 2*sqrt(2)*x)). (End)
a(n) = T(n, n-1), array T as in A064861.
a(n) = T(n, n-2), array T as in A049600.
a(n+1) = A110110(2n+1). - Tilman Neumann, Feb 05 2009
a(n) = 2 * JacobiP(n-1,0,1,3) = ((7*n+3)*LegendreP(n,3) - (n+1)*LegendreP(n+1,3)) /(2*n) for n > 0. - Mark van Hoeij, Jul 12 2010
Logarithmic derivative of A006318, the large Schroeder numbers. - Paul D. Hanna, Oct 25 2010
D-finite with recurrence: 4*(3*n^2-6*n+2)*a(n-1) - (n-2)*(2*n-1)*a(n-2) - n*(2*n-3)*a(n)=0. - Vaclav Kotesovec, Oct 04 2012
a(n) ~ (3+2*sqrt(2))^n/(2^(3/4)*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 04 2012
Recurrence (an alternative): n*a(n) = (6-n)*a(n-6) + 2*(5*n-27)*a(n-5) + (84-15*n)*a(n-4) + 52*(3-n)*a(n-3) + 3*(2-5*n)*a(n-2) + 2*(5*n-3)*a(n-1), n>=7. - Fung Lam, Feb 05 2014
a(n) = Hyper2F1([-n, n], [1], -1) for n > 0. - Peter Luschny, Aug 02 2014
a(n) = [x^n] ((1+x)/(1-x))^n for n > 0. - Seiichi Manyama, Jun 07 2018
From Peter Bala, Mar 13 2020: (Start)
a(n) = 2 * Sum_{k = 0..n-1}  2^k*C(n,k+1)*C(n-1,k).
a(n) = 2 * (-1)^(n+1) * Sum_{k = 0..n-1} (-2)^k*C(n+k,n-1)*C(n-1,k).
a(n) = Sum_{k = 0..n} C(n,k)*C(2*n-k-1,n-1).
Conjecture: a(n) = - [x^n] (1 - F(x))^n, where F(x) = 2*x + 6*x^2 + 34*x^3 + 238*x^4 + ... is the o.g.f. of A108424. Equivalently, a(n) = -[x^n](G(x))^(-n), where G(x) = 1 + 2*x + 10*x^2 + 66*x^3 + 498*x^4 + ... is the o.g.f. of A027307.
a(p) == 2 ( mod p^3 ) for prime p >= 5. (End)
a(n) = Sum_{k = 1..n} C(n, k) * C(n-1, k-1) * 2^k. - Michael Somos, May 23 2021
a(n) = A001850(n) - A002002(n), for n > 0. - Shel Kaphan, Feb 15 2023

More terms from Barbara Haas Margolius (b.margolius(AT)csuohio.edu), Oct 10 2001

A364394 G.f. satisfies A(x) = 1 + x/A(x)*(1 + 1/A(x)).

Original entry on oeis.org

1, 2, -6, 34, -238, 1858, -15510, 135490, -1223134, 11320066, -106830502, 1024144482, -9945711566, 97634828354, -967298498358, 9659274283650, -97119829841854, 982391779220482, -9990160542904134, 102074758837531810, -1047391288012377774, 10788532748880319298

Offset: 0

Seiichi Manyama, Jul 22 2023

sign

Cf. A112478, A364396, A364398.

Cf. A027307, A087197, A108424.

A364394 := proc(n)
    if n = 0 then
        1;
    else
    (-1)^(n-1)*add( binomial(n,k) * binomial(2*n+k-2,n-1),k=0..n)/n ;
    end if;
end proc:
seq(A364394(n),n=0..80); # R. J. Mathar, Jul 25 2023

a(n) = if(n==0, 1, (-1)^(n-1)*sum(k=0, n, binomial(n, k)*binomial(2*n+k-2, n-1))/n);

G.f.: A(x) = 1/B(-x) where B(x) is the g.f. of A027307.
a(n) = (-1)^(n-1) * (1/n) * Sum_{k=0..n} binomial(n,k) * binomial(2*n+k-2,n-1) = (-1)^(n-1) * A108424(n) for n > 0.
D-finite with recurrence n*(2*n-1)*a(n) +3*(6*n^2-10*n+3)*a(n-1) +(-46*n^2+227*n-279)*a(n-2) +2*(n-3)*(2*n-7)*a(n-3)=0. - R. J. Mathar, Jul 25 2023
a(n) ~ c*(-1)^(n-1)*4^n*2F1([-n, 2*n-1], [n], -1)*n^(-3/2), with c = 1/(4*sqrt(Pi)) = A087197/4. - Stefano Spezia, Oct 21 2023

A344553 Number of lattice paths from (0,0) to (2n-1,n) using steps E=(1,0), N=(0,1), and D=(1,1) which stay weakly above the line through (0,0) and (2n-1,n).

Original entry on oeis.org

1, 3, 17, 119, 929, 7755, 67745, 611567, 5660033, 53415251, 512072241, 4972855783, 48817414177, 483649249179, 4829637141825, 48559914920927, 491195889610241, 4995080271452067, 51037379418765905, 523695644006188887, 5394266374440159649, 55756104288043890667

Offset: 1

Matias von Bell, May 22 2021

These are the small nu-Schröder numbers with nu=NE(NEE)^(n-1).

			For n=2 the a(2)=3 paths are NENE, NDE, and NNEE.
For n=3 the a(3)=17 paths are NENEENEE, NENEDEE, NENENEEE, NENDEEE, NENNEEEE, NDEENEE, NDEDEE, NDENEEE, NDDEEE, NDNEEEE, NNEEENEE, NNEEDEE, NNEENEEE, NNEDEEE, NNENEEEE, NNDEEEE, NNNEEEEE.

M. von Bell and M. Yip, Schröder combinatorics and nu-associahedra, arXiv:2006.09804 [math.CO], 2020.

Cf. A001622, A108424.

a := n -> binomial(3*n - 2, 2*n - 1)*hypergeom([2 - 2*n, 1 - n], [2 - 3*n], -1)/n:
seq(simplify(a(n)), n = 1..22); # Peter Luschny, Jun 14 2021

Table[Sum[Binomial[2*n - 2, i]*Binomial[3*n - 2 - i, 2*n - 1], {i, 0, 2*n - 2}]/n, {n, 1, 20}] (* Vaclav Kotesovec, May 23 2021 *)

a(n) = {sum(i=0, n, binomial(2*n-2,i)*binomial(3*n-2-i,2*n-1))/n} \\ Andrew Howroyd, May 23 2021

a(n) = Sum_{i>=0} (1/n)*binomial(2*n-2,i)*binomial(3*n-2-i,2*n-1).
a(n) = A108424(n)/2.
a(n) ~ phi^(5*n - 1) / (4 * 5^(1/4) * sqrt(Pi) * n^(3/2)), where phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, May 23 2021
a(n) = binomial(3*n - 2, 2*n - 1)*hypergeom([2 - 2*n, 1 - n], [2 - 3*n], -1) / n. - Peter Luschny, Jun 14 2021
D-finite with recurrence (n+1)*(2*n+1)*a(n) +3*(-6*n^2-2*n+1)*a(n-1) +(-46*n^2+135*n-98)*a(n-2) -2*(n-2)*(2*n-5)*a(n-3)=0. - R. J. Mathar, Jul 27 2022
P-recursive: n*(2*n - 1)*(5*n - 8)*a(n) = (110*n^3 - 396*n^2 + 445*n - 150)*a(n-1) + (n - 2)*(2*n - 5)*(5*n - 3)*a(n-2) with a(1) = 1 and a(2) = 3. - Peter Bala, Jun 17 2023

A108435 Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1),U=(1,2), or d=(1,-1) and have k returns to the x-axis.

Original entry on oeis.org

2, 6, 4, 34, 24, 8, 238, 172, 72, 16, 1858, 1360, 624, 192, 32, 15510, 11444, 5520, 1952, 480, 64, 135490, 100520, 50040, 19136, 5600, 1152, 128, 1223134, 911068, 463512, 186416, 60320, 15168, 2688, 256, 11320066, 8457504, 4371808, 1821312, 629440, 178176, 39424, 6144, 512

Offset: 1

Emeric Deutsch, Jun 04 2005

Number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1),U=(1,2), or d=(1,-1) and have k steps up to the first peak. Example: T(2,2)=4 because we have uudd, uUddd, Uuddd and UUdddd. Row sums yield A027307. T(n,1)=A108424(n). T(n,n)=2^n.

			T(2,2)=4 because u(d)u(d), u(d)Ud(d), Ud(d)u(d) and Ud(d)Ud(d) (the steps d that return to the x-axis are shown between parentheses).
Triangle begins:
  2;
  6,4;
  34,24,8;
  238,172,72,16;
  1858,1360,624,192,32;
  ...

Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.

Cf. A027307, A108424, A108436.

Maple
```
T:=proc(n,k) if k
				
```

T[n_, k_] := Which[k < n, (k/(n - k))*(3*2^k*Binomial[n - 1, k] + Sum[2^(n - 1 - j)*(5*n - 2*k + j + 1)*Binomial[n - 1, j]*Binomial[2*n - k - 1, n + j]/(n + j + 1), {j, 0, n - k - 2}]), k == n, 2^n, True, 0];
Table[T[n, k], {n, 1, 9}, {k, 1, n}] // Flatten (* Jean-François Alcover, Aug 11 2024, after Maple code. *)

T(n, k)=[k/(n-k)][3*2^k*binomial(n-1, k)+sum(2^(n-1-j)*(5n-2k+j+1)binomial(n-1, j)binomial(2n-k-1, n+j)/(n+j+1), j=0..n-k-2)] if kA027307).

Keyword tabf changed to tabl by Michel Marcus, Apr 09 2013

A108439 Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1), U=(1,2), or d=(1,-1) and having abscissa of first return equal to 3k.

Original entry on oeis.org

2, 4, 6, 20, 12, 34, 132, 60, 68, 238, 996, 396, 340, 476, 1858, 8132, 2988, 2244, 2380, 3716, 15510, 69940, 24396, 16932, 15708, 18580, 31020, 135490, 624132, 209820, 138244, 118524, 122628, 155100, 270980, 1223134, 5725124, 1872396, 1188980

Offset: 1

Emeric Deutsch, Jun 05 2005

Row sums yield A027307. T(n,n) = A108424(n).

			T(2,1)=4 because we have u(d)ud, u(d)Udd, Ud(d)ud and Ud(d)Udd, the d step of the first return being shown between parentheses.
Triangle begins:
2;
4,6;
20,12,34;
132,60,68,238;
...

Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.

Cf. A027307, A108424, A108435.

a:=n->sum(2^(i+1)*binomial(2*n,i)*binomial(n,i+1),i=0..n-1)/n: b:=proc(n) if n=1 then 2 else (n*2^n*binomial(2*n,n)/((2*n-1)*(n+1)))*sum(binomial(n-1,j)^2/2^j/binomial(n+j+1,j),j=0..n-1): fi end: T:=proc(n,k) if k=n then b(n) else b(k)*a(n-k) fi end:for n from 1 to 9 do seq(T(n,k),k=1..n) od; > # yields sequence in triangular form

G.f.: tzA(z)A(tz)+tzA(z)A^2(tz), where A=1+zA^2+zA^3=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3 (the g.f. of A027307).

T(n, k) = A108424(k)*A027307(n-k) (there are explicit formulas in A108424 and A027307).

cp's OEIS Frontend

A002003 a(n) = 2 * Sum_{k=0..n-1} binomial(n-1, k)*binomial(n+k, k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A364394 G.f. satisfies A(x) = 1 + x/A(x)*(1 + 1/A(x)).

Views

Author

Keywords

Crossrefs

Programs

Maple

PARI

Formula

A344553 Number of lattice paths from (0,0) to (2n-1,n) using steps E=(1,0), N=(0,1), and D=(1,1) which stay weakly above the line through (0,0) and (2n-1,n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A108435 Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1),U=(1,2), or d=(1,-1) and have k returns to the x-axis.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A108439 Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1), U=(1,2), or d=(1,-1) and having abscissa of first return equal to 3k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula