A271777 a(n) = Sum_{k=1..n} ((-1)^(n-k) * k / ((n+1)^2 + (k-1)*(n+1))) * binomial(n+1, k+1) * binomial(n+k, k)^2.

0, 1, 3, 16, 105, 771, 6083, 50464, 434493, 3849715, 34895685, 322239204, 3021922137, 28710585099, 275827551795, 2675584398912, 26173225402437, 257940602058051, 2558852771578817, 25534696636443160, 256164209036422239, 2582189471692118101, 26142642319644094293

Offset: 0

Author

Vladimir Kruchinin, Apr 14 2016

Keywords

• nonn
• nice
• easy

Comments

a(n) is the number of Motzkin paths (A001006) with n upsteps U = (1,1), n flatsteps F = (1,0), and n downsteps D = (1,-1) that begin with an F, contain no DUs and no FDs, and end with D. For example, a(2) = 3 counts FFUUDD, FUDFUD, FUFUDD. Proof. Such a path is obtained from a Dyck path (A000108) of semilength n by inserting zero or more F's before each U as follows. There are n "spaces" available for the F's, one immediately preceding each U. An F must be inserted before the initial U, and before each valley U (else a DU would be present). If there are k peaks, hence k-1 valleys, this leaves n-k F's to be distributed arbitrarily among the n "spaces" -- binomial(2*n-1-k,n-k) choices. There are Narayana(n,k) (A001263) Dyck n-paths with k peaks, hence the total number of Motzkin paths meeting the specifications is Sum_{k=1..n} binomial(2*n-1-k, n-k)*Narayana(n,k). Peter Bala has shown that Maple's sumtools:-sumrecursion command produces the same second-order recurrence for this sum and for the titular binomial sum. QED - David Callan, Feb 15 2022

Crossrefs

Cf. A000108, A000984, A001622, A208675.

Programs

Maple

a := proc(n) option remember; if n < 3 then return [0, 1, 3][n+1] fi;
(3*(-n^3 + 8*n^2 - 19*n + 12)*a(n-3) + (-32*n^3 + 194*n^2 - 386*n + 252)* a(n-2) + (2*n - 2)*(7*n^2 - 10*n + 1)*a(n-1))/(n^3 - n) end:
seq(a(n), n = 0..20); # Peter Luschny, Feb 15 2022

Mathematica

a[n_] := Sum[(-1)^(n-k)*k / ((n+1)^2 + (k-1)*(n+1))*Binomial[n+1, k+1] * Binomial[n+k, k]^2, {k, 1, n}];
Table[a[n], {n, 0, 20}] (* Vaclav Kotesovec, Apr 14 2016 *)
h[n_, k_] := HypergeometricPFQ[{n, -n, n + 1}, {1, k}, 1];
A271777[n_] := If[n == 0, 0, (-1)^n (h[n, 1] - h[n, 2]) / n];
Table[A271777[n], {n, 0, 22}] (* Peter Luschny, Feb 15 2022 *)
A271777[n_] := (-1)^(n + 1) Binomial[n + 1, 2] HypergeometricPFQ[{1 - n, n + 1, n + 2}, {2, 3}, 1]; Table[A271777[n], {n, 0, 22}] (* Peter Luschny, Feb 18 2022 *)

Maxima

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

PARI

a(n) = sum(k=0,n,((-1)^(n-k)*k/((n+1)^2+(k-1)*(n+1))*binomial(n+1, k+1)*binomial(n+k, k)^2)) \\ Felix Fröhlich, Jul 14 2016

Formula

a(n) ~ sqrt(17 - 38/sqrt(5)) * ((1+sqrt(5))/2)^(5*(n+1)) / (2*Pi*(n+1)^2). - Vaclav Kotesovec, Apr 14 2016. Equivalently, a(n) ~ n^(-2)*phi^(5*n + 1/2)/(2*Pi*5^(1/4)), where phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Dec 06 2021

Recurrence: a(n)*((n+1)*n*(n-1)*(5*n-6)) = ((n-2)*(n-3)*(5*n-1)*n*a(n-2) + (55*n^3 - 121*n^2 + 64*n - 12)*(n-1)*a(n-1)). - Vaclav Kotesovec, Apr 14 2016

From David Callan, Feb 15 2022: (Start)

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

a(n) = Sum_{k=1..n} (-1)^(n-k)*binomial(n+k, 2*k)*binomial(n+k-1, k-1)* CatalanNumber(k) where CatalanNumber is A000108. (End)

a(n) = (-1)^(n+1)*binomial(n+1, 2)*hypergeom([1-n, n+1, n+2], [2, 3], 1). - Peter Luschny, Feb 18 2022

Extensions

Offset set to 0 and then changed a(0) = 0 by Peter Luschny, Feb 18 2022