A125107 Subtract compositions (A011782) from Catalan numbers (A000108).

0, 0, 0, 1, 6, 26, 100, 365, 1302, 4606, 16284, 57762, 205964, 738804, 2666248, 9678461, 35324902, 129579254, 477507628, 1767001046, 6563596132, 24465218444, 91480466488, 343055419346, 1289895758716, 4861929624236, 18367319517720, 69533483807140, 263747817532632

Offset: 0

Author

Alford Arnold, Dec 15 2006

Keywords

• easy
• nonn

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)

Examples

			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.
		

Links

• Nachum Dershowitz, Touchard's Drunkard, Journal of Integer Sequences, Vol. 20 (2017), #17.1.5.

Crossrefs

Cf. A000079, A000108, A000110, A011782, A016098, A097805, A091894 (Touchard distribution), A377659 (similar with Motzkin).

Programs

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 *)

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

Formula

a(n) = A000108(n) - A011782(n).

(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).

a(n) = Sum_{k=0..n} (A091894(n, k) - A097805(n, n-k)). (End)

Extensions

More terms from David Scambler, Sep 14 2012