cp's OEIS Frontend

A247285 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n (n>=1) having k (0<=k<=n-1) upper interactions.

%I A247285 #24 May 27 2015 10:34:13
%S A247285 1,1,1,1,3,1,1,5,7,1,1,7,19,14,1,1,9,36,59,26,1,1,11,58,150,162,46,1,
%T A247285 1,13,85,300,543,408,79,1,1,15,117,523,1335,1771,966,133,1,1,17,154,
%U A247285 833,2747,5303,5335,2184,221,1,1,19,196,1244,5031,12792,19272,15099,4767,364,1
%N A247285 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n (n>=1) having k (0<=k<=n-1) upper interactions.
%C A247285 An upper interaction in a Dyck path is an occurrence of a string d^k u^k for some k>=1; here u = (1,1) and d = (1,-1). For example, the Dyck path uu[d(du)u]dd has 2 upper interactions, shown between parentheses.
%C A247285 Number of entries in row n is n.
%C A247285 Sum of entries in row n is the Catalan number A000108(n).
%C A247285 Sum(k*T(n,k), k>=0) = A172061(n-2).
%C A247285 The statistic "number of lower interactions", mentioned in the Le Borgne reference is basically identical with the statistic "pyramid weight" of the Denise and Simion reference (see A091866 and the bottom of p. 8 of the Le Borgne reference).
%C A247285 T(n+1,n) = A001924(n) for n>=1. - _Alois P. Heinz_, Sep 11 2014
%H A247285 Alois P. Heinz, <a href="/A247285/b247285.txt">Rows n = 1..141, flattened</a>
%H A247285 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.
%H A247285 Y. Le Borgne, <a href="http://www.emis.de/journals/SLC/wpapers/s54leborgne.html">Counting upper interactions in Dyck paths</a>, Sem. Lotharingien de Combinatoire, 54, 2006, Article B54f.
%F A247285 The g.f. A(t,u), where t marks semilength and u marks upper interactions, is given in Proposition 2 of the Le Borgne reference. It is extremely complex; the Maple program follows it (blindly), except that the infinite sums have been replaced by summations from n=0 to n=15.
%e A247285 Row 3 is 1,3,1. Indeed, the number of upper interactions in uuuddd, uududd, uuddud, uduudd, and ududud are 0, 1, 1, 1, and 2, respectively.
%e A247285 Triangle starts:
%e A247285 1;
%e A247285 1,1;
%e A247285 1,3,1;
%e A247285 1,5,7,1;
%e A247285 1,7,19,14,1;
%e A247285 1,9,36,59,26,1;
%p A247285 q := u*t: s := ((1+t-2*q-sqrt((1-t)*(1-t-4*q+4*q^2)))*(1/2))/(t*(1-q)): Q := proc (x, n) options operator, arrow: product(1-q^k*x, k = 0 .. n-1) end proc: A := -t*add(((q-t)*s/(1-q))^n*q^(binomial(n+2, 2)-1)/(Q(q, n)*Q(q*t*s^2, n)), n = 0 .. 15)/add(((q-t)*s/(1-q))^n*q^binomial(n+2, 2)*(1-t*q^n*s)/(Q(q, n)*Q(q*t*s^2, n)*(1-q^n*s)*(1-q^(n+1)*s)), n = 0 .. 15): Aser := simplify(series(A, t = 0, 22)): for n to 16 do P[n] := sort(coeff(Aser, t, n)) end do: for n to 13 do seq(coeff(P[n], u, j), j = 0 .. n-1) end do; # yields sequence in triangular form
%p A247285 # second Maple program:
%p A247285 b:= proc(x, y, t, c) option remember; `if`(y<0 or y>x, 0,
%p A247285      `if`(x=0, 1, expand(b(x-1, y+1, false, max(0, c-1))*
%p A247285      `if`(c>0, z, 1)+b(x-1, y-1, true, 1+`if`(t, c, 0)))))
%p A247285     end:
%p A247285 T:= n-> (p-> seq(coeff(p, z, i), i=0..n-1))(b(2*n, 0, false, 0)):
%p A247285 seq(T(n), n=1..15);  # _Alois P. Heinz_, Sep 11 2014
%t A247285 b[x_, y_, t_, c_] := b [x, y, t, c] = If[y<0 || y>x, 0, If[x == 0, 1, Expand[b[x-1, y+1, False, Max[0, c-1]]*If[c>0, z, 1] + b[x-1, y-1, True, 1 + If[t, c, 0] ] ] ] ]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, n-1}]][b[2*n, 0, False, 0]]; Table[T[n], {n, 1, 25}] // Flatten (* _Jean-François Alcover_, May 27 2015, after _Alois P. Heinz_ *)
%Y A247285 Cf. A000108, A001924, A172061, A091866.
%K A247285 nonn,tabl
%O A247285 1,5
%A A247285 _Emeric Deutsch_, Sep 11 2014