login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 1
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, 1, 13, 85, 300, 543, 408, 79, 1, 1, 15, 117, 523, 1335, 1771, 966, 133, 1, 1, 17, 154, 833, 2747, 5303, 5335, 2184, 221, 1, 1, 19, 196, 1244, 5031, 12792, 19272, 15099, 4767, 364, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

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.

Number of entries in row n is n.

Sum of entries in row n is the Catalan number A000108(n).

Sum(k*T(n,k), k>=0) = A172061(n-2).

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

T(n+1,n) = A001924(n) for n>=1. - Alois P. Heinz, Sep 11 2014

LINKS

Alois P. Heinz, Rows n = 1..141, flattened

A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155-176.

Y. Le Borgne, Counting upper interactions in Dyck paths, Sem. Lotharingien de Combinatoire, 54, 2006, Article B54f.

FORMULA

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.

EXAMPLE

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.

Triangle starts:

1;

1,1;

1,3,1;

1,5,7,1;

1,7,19,14,1;

1,9,36,59,26,1;

MAPLE

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

# second Maple program:

b:= proc(x, y, t, c) option remember; `if`(y<0 or 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)))))

    end:

T:= n-> (p-> seq(coeff(p, z, i), i=0..n-1))(b(2*n, 0, false, 0)):

seq(T(n), n=1..15);  # Alois P. Heinz, Sep 11 2014

MATHEMATICA

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

CROSSREFS

Cf. A000108, A001924, A172061, A091866.

Sequence in context: A145661 A119258 A099608 * A047969 A047812 A129392

Adjacent sequences:  A247282 A247283 A247284 * A247286 A247287 A247288

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Sep 11 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 27 02:00 EDT 2021. Contains 348270 sequences. (Running on oeis4.)