cp's OEIS Frontend

A096793 Triangle read by rows: a(n,k) is the number of Dyck n-paths containing k odd-length ascents.

%I A096793 #10 Jul 23 2019 02:02:38
%S A096793 1,0,1,1,0,1,0,4,0,1,3,0,10,0,1,0,21,0,20,0,1,12,0,84,0,35,0,1,0,120,
%T A096793 0,252,0,56,0,1,55,0,660,0,630,0,84,0,1,0,715,0,2640,0,1386,0,120,0,1,
%U A096793 273,0,5005,0,8580,0,2772,0,165,0,1,0,4368,0,25025,0,24024,0,5148,0,220,0,1
%N A096793 Triangle read by rows: a(n,k) is the number of Dyck n-paths containing k odd-length ascents.
%C A096793 a(n,k)=0 unless k and n have the same parity and 0 <= k <= n.
%C A096793 From _Emeric Deutsch_, Oct 05 2008: (Start)
%C A096793 Sum_{k=0..n} k*a(n,k) = A014300(n).
%C A096793 For the case of even-length ascents see A143950. (End)
%F A096793 a(n, k) = binomial((n+k)/2, (n-k)/2)*binomial((3n-k)/2+1, (n+k)/2)/((3n-k)/2+1).
%F A096793 Equivalently, a(2n+k, k) = binomial(3n+k, k)*T(n) where T(n) = binomial(3n, n)/(2n+1) is A001764. Proof: Given a Dyck (2n+k)-path with k ascents of odd length, delete the peaks (UD) that terminate odd-length ascents. This is a mapping to Dyck (2n)-paths all of whose ascents have even length; there are T[n] such paths. The mapping is clearly onto and is binomial(3n+k, k)-to-1 as follows. A Dyck (2n)-path all of whose ascents have even length has exactly 3n+1 vertices that are (i) not incident with an upstep, or (ii) incident with an upstep and at even distance (possibly 0) from the start of the ascent they lie in. The k deleted UDs can be inserted arbitrarily at these vertices, repetition allowed, to get the preimages -- binomial(3n+k, k) choices.
%F A096793 G.f.: G(z, t) + H(z, t) where G satisfies G^3*(t^2 - 1)*z^2 - G^2*t*z*(2 + t*z) + G*(1 + 2*t*z) - 1 = 0 and H satisfies H^3*(t^2 - 1)*z^2 + H^2*t*z*(2 + t*z) - H*t^2*(1 - t*z) + t^3*z = 0. Here z marks size (n) and t marks number of odd-length ascents (k). G is gf for paths that start with an even-length ascent and H is gf for paths that start with an odd-length ascent. - _David Callan_, Sep 03 2005
%F A096793 From _Emeric Deutsch_, Oct 05 2008: (Start)
%F A096793 G.f. G=G(t,z) satisfies G = 1 + zG(t + zG)/(1 - z^2*G^2).
%F A096793 The trivariate g.f. H=H(t,s,z), where t(s) marks odd-length (even-length) ascents satisfies H = 1 + zH(t+szH)/(1-z^2*H^2). (End)
%e A096793 Table begins
%e A096793 .
%e A096793 n |k = 0    1    2    3    4    5    6    7    8
%e A096793 --+---------------------------------------------
%e A096793 0 |    1
%e A096793 1 |    0,   1
%e A096793 2 |    1,   0,   1
%e A096793 3 |    0,   4,   0,   1
%e A096793 4 |    3,   0,  10,   0,   1
%e A096793 5 |    0,  21,   0,  20,   0,   1
%e A096793 6 |   12,   0,  84,   0,  35,   0,   1
%e A096793 7 |    0, 120,   0, 252,   0,  56,   0,   1
%e A096793 8 |   55,   0, 660,   0, 630,   0,  84,   0,   1
%e A096793 .
%e A096793 a(4,0)=3 because the Dyck 4-paths containing no odd-length ascents are UUUUDDDD,UUDUUDDD,UUDDUUDD.
%t A096793 bi[n_, k_] := If[IntegerQ[k], Binomial[n, k], 0]; TableForm[Table[bi[(n+k)/2, (n-k)/2]bi[(3n-k)/2+1, (n+k)/2]/((3n-k)/2+1), {n, 0, 10}, {k, 0, n}]]
%Y A096793 The nonzero entries in column k=0 give A001764, in k=1 give A045721, in k=2 give A090763. The row sums are the Catalan numbers A000108.
%Y A096793 Cf. A143950. - _Emeric Deutsch_, Oct 05 2008
%K A096793 nonn,tabl
%O A096793 0,8
%A A096793 _David Callan_, Aug 17 2004