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!)
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. 9
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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

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.

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

Triangular array in A011117 transposed. - Philippe Deléham, Mar 16 2005

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.

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

EXAMPLE

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)

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

PROG

(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

CROSSREFS

Row sums are the large Schroeder numbers (A006318). Column 0 yields the little Schroeder numbers (A001003).

Cf. A104967 (matrix inverse), A091370.

Sequence in context: A077756 A115080 A222730 * A123513 A117442 A184182

Adjacent sequences:  A104216 A104217 A104218 * A104220 A104221 A104222

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Mar 14 2005

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 April 16 04:49 EDT 2021. Contains 343030 sequences. (Running on oeis4.)