cp's OEIS Frontend

A104219 Triangle read by rows: T(n,k) is number of Schroeder paths of length 2n and having k peaks at height 1, for 0 <= k <= n.

%I A104219 #66 Mar 05 2020 16:59:32
%S A104219 1,1,1,3,2,1,11,7,3,1,45,28,12,4,1,197,121,52,18,5,1,903,550,237,84,
%T A104219 25,6,1,4279,2591,1119,403,125,33,7,1,20793,12536,5424,1976,630,176,
%U A104219 42,8,1,103049,61921,26832,9860,3206,930,238,52,9,1,518859,310954,134913,49912
%N A104219 Triangle read by rows: T(n,k) is number of Schroeder paths of length 2n and having k peaks at height 1, for 0 <= k <= n.
%C A104219 A Schroeder path is a lattice path starting from (0,0), ending at a point on the x-axis, consisting only of steps U = (1,1), D = (1,-1) and H = (2,0) and never going below the x-axis. Schroeder paths are counted by the large Schroeder numbers (A006318).
%C A104219 This is an example of a Riordan (lower triangular) matrix. See the Shapiro et al. reference quoted under A053121. More precisely, this ordinary convolution triangle belongs to the Bell subgroup of the Riordan group. In the Shapiro et al. notation this is a Bell matrix (g(x), x*g(x)) with g(x) = (1+x-sqrt(1-6*x+x^2))/(4*x), the o.g.f. of A001003(n), n >= 0.
%C A104219 The g.f. for the row polynomials p(n,x) = Sum_{k=0..n} a(n,k)*x^k is g(y)/(1-x*y*g(y)) = (1-2*x*y+y-sqrt(1-6*y+y^2))/(2*y*(2-x-x*y+x^2*y)).
%C A104219 Triangular array in A011117 transposed. - _Philippe Deléham_, Mar 16 2005
%H A104219 Peter Luschny, <a href="/A104219/b104219.txt">Row n for n = 0..44</a>.
%H A104219 Shishuo Fu, Yaling Wang, <a href="https://arxiv.org/abs/1908.03912">Bijective recurrences concerning two Schröder triangles</a>, arXiv:1908.03912 [math.CO], 2019.
%H A104219 E. Pergola and R. A. Sulanke, <a href="https://cs.uwaterloo.ca/journals/JIS/PergolaSulanke/">Schroeder Triangles, Paths and Parallelogram Polyominoes</a>, J. Integer Sequences, 1 (1998), #98.1.7.
%H A104219 Mark C. Wilson, <a href="http://www.cs.auckland.ac.nz/~mcw/Research/Outputs/Wils2013.pdf">Diagonal asymptotics for products of combinatorial classes</a>, preprint 2013; Combinatorics, Probability and Computing, Volume 24, Issue 1 (Honouring the Memory of Philippe Flajolet - Part 3) January 2015, pp. 354-372.
%F A104219 G.f.: 2/(1+z+sqrt(1-6*z+z^2)-2*z*t).
%F A104219 Another version of the triangle T(n, k), 0 <= k <= n, read by rows; given by [0, 1, 2, 1, 2, 1, 2, 1, 2, 1, ...] DELTA [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...] = 1; 0, 1; 0, 1, 1; 0, 3, 2, 1; 0, 11, 7, 3, 1; 0, 45, 28, 12, 4, 1; ... where DELTA is the operator defined in A084938. - _Philippe Deléham_, Mar 16 2005
%F A104219 a(n, k) = (k+1)*hypergeom([1-n+k, n+2], [2], -1) if n > k; a(n, n)=1; a(n, k)=0 if n < k. - _Wolfdieter Lang_, Sep 12 2005
%F A104219 a(n, k) = ((k+1)/(n-k))*Sum_{p=1..n-k} binomial(n-k, p)*binomial(n+p, p-1) if n > k; a(n, n)=1; a(n, k)=0 if n < k. Proof with Lagrange's inversion theorem based on eq. y = 1+x*(1-2/y) where y=1/g(x), with g(x) the o.g.f. of A001003(n), n >= 0. Use G(k;y):=1/y^(k+1), k >= 0 to find the coefficients a(n, k) of x^n of G(k;1/g(x)). For this method see also the Larcombe and French paper on Catalan convolutions quoted under A033184. - _Wolfdieter Lang_, Sep 12 2005
%F A104219 G.f.: 1/(1-x*y-x/(1-x-x/(1-x-x/(1-x-x/(1-x-x/(1-... (continued fraction). - _Paul Barry_, Feb 01 2009
%F A104219 T((m+1)*n+r-1,m*n+r-1)*r/(m*n+r) = Sum_{k=1..n} (k/n)*T((m+1)*n-k-1,m*n-1)*(r+k,r), n >= m > 1, also T(n-1,m-1) = (m/n)*Sum_{k=1..n-m+1} k*A001003(k-1)*T(n-k-1,m-2), n >= m > 1. - _Vladimir Kruchinin_, Mar 17 2011
%F A104219 T(n, k) = (-1)^(n - k)*binomial(n, k)*hypergeom([k - n, n + 1], [k + 2], 2). - _Peter Luschny_, Jan 08 2018
%e A104219 Triangle starts:
%e A104219   [0]   1;
%e A104219   [1]   1,   1;
%e A104219   [2]   3,   2,   1;
%e A104219   [3]  11,   7,   3,  1;
%e A104219   [4]  45,  28,  12,  4,  1;
%e A104219   [5] 197, 121,  52, 18,  5, 1;
%e A104219   [6] 903, 550, 237, 84, 25, 6, 1;
%e A104219 T(3,1)=7 because we have HH(UD),H(UD)H,(UD)HH,UUDD(UD),(UD)UUDD,(UD)UHD, and
%e A104219 UHD(UD) (the peaks UD at height 1 are shown between parentheses).
%e A104219 From _Philippe Deléham_, Dec 04 2015: (Start)
%e A104219 Production matrix begins:
%e A104219    1,  1;
%e A104219    2,  1,  1;
%e A104219    4,  2,  1, 1;
%e A104219    8,  4,  2, 1, 1;
%e A104219   16,  8,  4, 2, 1, 1;
%e A104219   32, 16,  8, 4, 2, 1, 1;
%e A104219   64, 32, 16, 8, 4, 2, 1, 1; (End)
%p A104219 G:=2/(1+z+sqrt(1-6*z+z^2)-2*z*t): Gser:=simplify(series(G,z=0,13)): P[0]:=1: for n from 1 to 13 do P[n]:=coeff(Gser,z^n) od: for n from 0 to 11 do seq(coeff(t*P[n],t^k),k=1..n+1) od; # yields sequence in triangular form
%p A104219 # Alternatively:
%p A104219 T_row := proc(n) local c,f,s;
%p A104219 c := N -> hypergeom([1-N, N+2], [2], -1);
%p A104219 f := n -> 1+add(simplify(c(i))*x^i,i=1..n):
%p A104219 s := j -> coeff(series(f(j)/(1-x*t*f(j)),x,j+1),x,j):
%p A104219 seq(coeff(s(n),t,j),j=0..n) end:
%p A104219 seq(T_row(n),n=0..10); # _Peter Luschny_, Oct 30 2015
%t A104219 T[n_, k_] := (-1)^(n - k) Binomial[n, k] Hypergeometric2F1[k - n, n + 1, k + 2, 2];
%t A104219 Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* _Peter Luschny_, Jan 08 2018 *)
%o A104219 (PARI) {T(n,k)=local(X=x+x*O(x^n),Y=y+y*O(y^k)); polcoeff(polcoeff(2/(1+X+sqrt(1-6*X+X^2)-2*X*Y),n,x),k,y)} \\ _Paul D. Hanna_, Mar 30 2005
%o A104219 (Sage)
%o A104219 def A104219_row(n):
%o A104219     @cached_function
%o A104219     def prec(n, k):
%o A104219         if k==n: return 1
%o A104219         if k==0: return 0
%o A104219         return prec(n-1,k-1)+sum(prec(n,k+i-1) for i in (2..n-k+1))
%o A104219     return [prec(n, k) for k in (1..n)]
%o A104219 for n in (1..9): print(A104219_row(n)) # _Peter Luschny_, Mar 16 2016
%Y A104219 Row sums are the large Schroeder numbers (A006318). Column 0 yields the little Schroeder numbers (A001003).
%Y A104219 Cf. A104967 (matrix inverse), A091370.
%K A104219 nonn,tabl
%O A104219 0,4
%A A104219 _Emeric Deutsch_, Mar 14 2005