login
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).
3
1, 3, 17, 119, 929, 7755, 67745, 611567, 5660033, 53415251, 512072241, 4972855783, 48817414177, 483649249179, 4829637141825, 48559914920927, 491195889610241, 4995080271452067, 51037379418765905, 523695644006188887, 5394266374440159649, 55756104288043890667
OFFSET
1,2
COMMENTS
These are the small nu-Schröder numbers with nu=NE(NEE)^(n-1).
LINKS
M. von Bell and M. Yip, Schröder combinatorics and nu-associahedra, arXiv:2006.09804 [math.CO], 2020.
FORMULA
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
EXAMPLE
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.
MAPLE
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
MATHEMATICA
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 *)
PROG
(PARI) 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
CROSSREFS
Sequence in context: A074544 A165976 A368965 * A121572 A340993 A249924
KEYWORD
nonn,easy
AUTHOR
Matias von Bell, May 22 2021
STATUS
approved