cp's OEIS Frontend

A091977 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k exterior pairs.

%I A091977 #14 Dec 03 2014 04:00:31
%S A091977 1,1,2,4,1,8,5,1,16,18,7,1,32,56,34,9,1,64,160,138,55,11,1,128,432,
%T A091977 500,275,81,13,1,256,1120,1672,1205,481,112,15,1,512,2816,5264,4797,
%U A091977 2471,770,148,17,1,1024,6912,15808,17738,11403,4536,1156,189,19,1,2048,16640
%N A091977 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k exterior pairs.
%C A091977 A pyramid in a Dyck word (path) is a factor of the form u^h d^h, h being the height of the pyramid. A pyramid in a Dyck word w is maximal if, as a factor in w, it is not immediately preceded by a u and immediately followed by a d.
%C A091977 The pyramid weight of a Dyck path (word) is the sum of the heights of its maximal pyramids. An exterior pair in a Dyck path is a pair consisting of a u and its matching d (when viewed as parentheses) which do not belong in any pyramid. Clearly, for a given Dyck path, the sum of its pyramid weight and the number of its exterior pairs is equal to the semilength of the path.
%C A091977 Triangle, with zeros omitted, given by (1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, ...) DELTA (0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, ...) where DELTA is the operator defined in A084938. - _Philippe Deléham_, Feb 06 2012
%H A091977 A. Denise and R. Simion, <a href="http://dx.doi.org/10.1016/0012-365X(93)E0147-V">Two combinatorial statistics on Dyck paths</a>, Discrete Math., 137, 1995, 155-176.
%F A091977 G.f.=G=G(t, z) satisfies tz(1-z)G^2-(1+tz-2z)G+1-z=0.
%e A091977 T(4,1)=5 because the Dyck paths of semilength 4 having 1 exterior pair are: ud(u)udud(d), (u)udud(d)ud, (u)ududud(d), (u)uduudd(d) and (u)uuuddud(d) [the u and d that form the unique exterior pair are shown between parentheses].
%e A091977 Triangle begins:
%e A091977 [1],
%e A091977 [1],
%e A091977 [2],
%e A091977 [4, 1],
%e A091977 [8, 5, 1],
%e A091977 [16, 18, 7, 1],
%e A091977 [32, 56, 34, 9, 1],
%e A091977 [64, 160, 138, 55, 11, 1],
%e A091977 [128, 432, 500, 275, 81, 13, 1]
%e A091977 Triangle (1,1,0,1,1,0,1,1,...) DELTA (0,0,1,0,0,1,0,0,1,...) begins :
%e A091977 1
%e A091977 1, 0
%e A091977 2, 0, 0
%e A091977 4, 1, 0, 0
%e A091977 8, 5, 1, 0, 0
%e A091977 16, 18, 7, 1, 0, 0
%e A091977 32, 56, 34, 9, 1, 0, 0
%e A091977 64, 160, 138, 55, 11, 1, 0, 0...- _Philippe Deléham_, Feb 06 2012
%Y A091977 T(n, k)=A091866(n, n-k), T(n, 0)=2^(n-1) (n>0), T(n, 1)=A001793(n-2), row sums give the Catalan numbers (A000108).
%Y A091977 Cf. A091866, A001793, A000108.
%K A091977 nonn,tabf
%O A091977 0,3
%A A091977 _Emeric Deutsch_, Mar 15 2004