OFFSET
0,5
COMMENTS
Apparently the number of Dyck n-paths with more than half of the path lying between the first and last peaks. - David Scambler, Sep 14 2012
From Peter Luschny, Nov 28 2024: (Start)
A Touchard walk T(n) of length n is, as defined by Dershowitz, "a sequence of n steps, each of which is one of N/S/E/W, such that at each point along the way the number of N-steps that have been taken is never less than the number of S-steps, and are in the end equal."
There are Sum_{k=0..n} binomial(n, k) Touchard walks that have no N/S-steps at all and since by Touchard's identity T(n) = Catalan(n+1), it follows that a(n) = T(n-1) - Sum_{k=0..n-1} binomial(n-1, k) = Catalan(n) - 2^(n-1) for n >= 1. Thus a(n+1) is the number of Touchard walks of length n that have at least one N-step. (End)
LINKS
Nachum Dershowitz, Touchard's Drunkard, Journal of Integer Sequences, Vol. 20 (2017), #17.1.5.
FORMULA
(n+1)*a(n) + 2*(1-4*n)*a(n-1) + 4*(5*n-7)*a(n-2) + 8*(5-2*n)*a(n-3) = 0. - R. J. Mathar, Aug 10 2013
From Peter Luschny, Nov 28 2024: (Start)
a(n) = [x^n] (1 - sqrt(1 - 4*x)) / (2*x) - (1 - x) / (1 - 2*x).
a(n) = n! * [x^n] (exp(2*x)*(BesselI_{0}(2*x) - BesselI_{1}(2*x) - 1/2) - 1/2).
a(n) = p(n, 1) for n >= 1, where p(n, x) = 2^(n-1)*(hypergeom([1-n/2, (1-n)/2], [2], x) - 1).
EXAMPLE
A000108 begins 1 1 2 5 14 42 132 429 ...
A011782 begins 1 1 2 4 8 16 32 64 ...
so we get .... 0 0 0 1 6 26 100 365 ...
.
The 26 Touchard walks of length 4 that have at least one N-step are:
NNSS, NSNS, NSEE, NSEW, NSWE, NSWW, NESE, NESW, NWSE,
NWSW, NEES, NEWS, NWES, NWWS, ENSE, ENSW, WNSE, WNSW,
ENES, ENWS, WNES, WNWS, EENS, EWNS, WENS, WWNS.
MAPLE
# From Peter Luschny, Nov 28 2024: (Start)
a := n -> ifelse(n = 0, 0, binomial(2*n, n)/(n+1) - 2^(n-1)): seq(a(n), n = 0..28);
# Series expansion:
gf := (1 - sqrt(1 - 4*x)) / (2*x) - (1 - x) / (1 - 2*x): ser := series(gf, x, 30): seq(coeff(ser, x, n), n = 0..28);
# Evaluating polynomials:
p := (n, x) -> ifelse(n = 0, 0, 2^(n-1)*(hypergeom([1 - n/2, 1/2 - n/2], [2], x) - 1)): seq(subs(x = 1, expand(simplify(p(n, x)))), n = 0..28); # (End)
MATHEMATICA
Table[CatalanNumber[n] - If[n==0, 1, 2^(n-1)], {n, 0, 30}] (* David Scambler, Sep 14 2012 *)
PROG
(Python)
# Generates the walks (for illustration only).
C = str.count
def aGen(n: int) -> Generator[str, Any, list[str]]:
a = [""]
if n <= 0: return a
for w in a:
if len(w) == n - 1:
if C(w, "N") > 0 and C(w, "N") == C(w, "S"):
yield w
else:
for j in "NSEW":
U = w + j
if C(U, "N") >= C(U, "S"):
a += [U]
return a
for n in range(6): print([w for w in aGen(n)]) # Peter Luschny, Dec 03 2024
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Alford Arnold, Dec 15 2006
EXTENSIONS
More terms from David Scambler, Sep 14 2012
STATUS
approved