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.
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, 25, 6, 1, 4279, 2591, 1119, 403, 125, 33, 7, 1, 20793, 12536, 5424, 1976, 630, 176, 42, 8, 1, 103049, 61921, 26832, 9860, 3206, 930, 238, 52, 9, 1, 518859, 310954, 134913, 49912
Offset: 0
Examples
Triangle starts: [0] 1; [1] 1, 1; [2] 3, 2, 1; [3] 11, 7, 3, 1; [4] 45, 28, 12, 4, 1; [5] 197, 121, 52, 18, 5, 1; [6] 903, 550, 237, 84, 25, 6, 1; T(3,1)=7 because we have HH(UD),H(UD)H,(UD)HH,UUDD(UD),(UD)UUDD,(UD)UHD, and UHD(UD) (the peaks UD at height 1 are shown between parentheses). From _Philippe Deléham_, Dec 04 2015: (Start) Production matrix begins: 1, 1; 2, 1, 1; 4, 2, 1, 1; 8, 4, 2, 1, 1; 16, 8, 4, 2, 1, 1; 32, 16, 8, 4, 2, 1, 1; 64, 32, 16, 8, 4, 2, 1, 1; (End)
Links
- Peter Luschny, Row n for n = 0..44.
- Shishuo Fu, Yaling Wang, Bijective recurrences concerning two Schröder triangles, arXiv:1908.03912 [math.CO], 2019.
- E. Pergola and R. A. Sulanke, Schroeder Triangles, Paths and Parallelogram Polyominoes, J. Integer Sequences, 1 (1998), #98.1.7.
- Mark C. Wilson, Diagonal asymptotics for products of combinatorial classes, preprint 2013; Combinatorics, Probability and Computing, Volume 24, Issue 1 (Honouring the Memory of Philippe Flajolet - Part 3) January 2015, pp. 354-372.
Crossrefs
Programs
-
Maple
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 # Alternatively: T_row := proc(n) local c,f,s; c := N -> hypergeom([1-N, N+2], [2], -1); f := n -> 1+add(simplify(c(i))*x^i,i=1..n): s := j -> coeff(series(f(j)/(1-x*t*f(j)),x,j+1),x,j): seq(coeff(s(n),t,j),j=0..n) end: seq(T_row(n),n=0..10); # Peter Luschny, Oct 30 2015
-
Mathematica
T[n_, k_] := (-1)^(n - k) Binomial[n, k] Hypergeometric2F1[k - n, n + 1, k + 2, 2]; Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Peter Luschny, Jan 08 2018 *) -
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 -
Sage
def A104219_row(n): @cached_function def prec(n, k): if k==n: return 1 if k==0: return 0 return prec(n-1,k-1)+sum(prec(n,k+i-1) for i in (2..n-k+1)) return [prec(n, k) for k in (1..n)] for n in (1..9): print(A104219_row(n)) # Peter Luschny, Mar 16 2016
Formula
G.f.: 2/(1+z+sqrt(1-6*z+z^2)-2*z*t).
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
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
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
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
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
T(n, k) = (-1)^(n - k)*binomial(n, k)*hypergeom([k - n, n + 1], [k + 2], 2). - Peter Luschny, Jan 08 2018
Comments