cp's OEIS Frontend

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

%I A125107 #31 Dec 03 2024 05:25:03
%S A125107 0,0,0,1,6,26,100,365,1302,4606,16284,57762,205964,738804,2666248,
%T A125107 9678461,35324902,129579254,477507628,1767001046,6563596132,
%U A125107 24465218444,91480466488,343055419346,1289895758716,4861929624236,18367319517720,69533483807140,263747817532632
%N A125107 Subtract compositions (A011782) from Catalan numbers (A000108).
%C A125107 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
%C A125107 From _Peter Luschny_, Nov 28 2024: (Start)
%C A125107 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."
%C A125107 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)
%H A125107 Nachum Dershowitz, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Dershowitz/dersh3.html">Touchard's Drunkard</a>, Journal of Integer Sequences, Vol. 20 (2017), #17.1.5.
%F A125107 a(n) = A000108(n) - A011782(n).
%F A125107 (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
%F A125107 From _Peter Luschny_, Nov 28 2024: (Start)
%F A125107 a(n) = [x^n] (1 - sqrt(1 - 4*x)) / (2*x) - (1 - x) / (1 - 2*x).
%F A125107 a(n) = n! * [x^n] (exp(2*x)*(BesselI_{0}(2*x) - BesselI_{1}(2*x) - 1/2) - 1/2).
%F A125107 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).
%F A125107 a(n) = Sum_{k=0..n} (A091894(n, k) - A097805(n, n-k)). (End)
%e A125107 A000108 begins 1 1 2 5 14 42 132 429 ...
%e A125107 A011782 begins 1 1 2 4  8 16  32  64 ...
%e A125107 so we get .... 0 0 0 1  6 26 100 365 ...
%e A125107 .
%e A125107 The 26 Touchard walks of length 4 that have at least one N-step are:
%e A125107    NNSS, NSNS, NSEE, NSEW, NSWE, NSWW, NESE, NESW, NWSE,
%e A125107    NWSW, NEES, NEWS, NWES, NWWS, ENSE, ENSW, WNSE, WNSW,
%e A125107    ENES, ENWS, WNES, WNWS, EENS, EWNS, WENS, WWNS.
%p A125107 # From _Peter Luschny_, Nov 28 2024: (Start)
%p A125107 a := n -> ifelse(n = 0, 0, binomial(2*n, n)/(n+1) - 2^(n-1)): seq(a(n), n = 0..28);
%p A125107 # Series expansion:
%p A125107 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);
%p A125107 # Evaluating polynomials:
%p A125107 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)
%t A125107 Table[CatalanNumber[n] - If[n==0, 1, 2^(n-1)], {n, 0, 30}] (* _David Scambler_, Sep 14 2012 *)
%o A125107 (Python)
%o A125107 # Generates the walks (for illustration only).
%o A125107 C = str.count
%o A125107 def aGen(n: int) -> Generator[str, Any, list[str]]:
%o A125107     a = [""]
%o A125107     if n <= 0: return a
%o A125107     for w in a:
%o A125107         if len(w) == n - 1:
%o A125107             if C(w, "N") > 0 and C(w, "N") == C(w, "S"):
%o A125107                 yield w
%o A125107         else:
%o A125107             for j in "NSEW":
%o A125107                 U = w + j
%o A125107                 if C(U, "N") >= C(U, "S"):
%o A125107                     a += [U]
%o A125107     return a
%o A125107 for n in range(6): print([w for w in aGen(n)])  # _Peter Luschny_, Dec 03 2024
%Y A125107 Cf. A000079, A000108, A000110, A011782, A016098, A097805, A091894 (Touchard distribution), A377659 (similar with Motzkin).
%K A125107 easy,nonn
%O A125107 0,5
%A A125107 _Alford Arnold_, Dec 15 2006
%E A125107 More terms from _David Scambler_, Sep 14 2012