login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A011117 Triangle of numbers S(x,y) = number of lattice paths from (0,0) to (x,y) that use step set { (0,1), (1,0), (2,0), (3,0), ....} and never pass below y = x. 14

%I #45 Feb 22 2020 11:50:51

%S 1,1,1,1,2,3,1,3,7,11,1,4,12,28,45,1,5,18,52,121,197,1,6,25,84,237,

%T 550,903,1,7,33,125,403,1119,2591,4279,1,8,42,176,630,1976,5424,12536,

%U 20793,1,9,52,238,930,3206,9860,26832,61921,103049,1,10,63

%N Triangle of numbers S(x,y) = number of lattice paths from (0,0) to (x,y) that use step set { (0,1), (1,0), (2,0), (3,0), ....} and never pass below y = x.

%C When seen as polynomials with descending coefficients: evaluations are A006318 (x=1), A001003 (x=2).

%C Triangular array in A104219 transposed. - _Philippe Deléham_, Mar 16 2005

%C Triangle T(n,k), 0 <= k <= n, defined by: T(0,0) = 1, T(n,k) = T(n-1,k) + Sum_{j=0..k-1} 2^j*T(n-1,k-1-j). - _Philippe Deléham_, Oct 10 2005

%H E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, <a href="http://www.mat.univie.ac.at/~slc/wpapers/s46rinaldi.html">ECO method and hill-free generalized Motzkin paths</a>, Séminaire Lotharingien de Combinatoire, B46b (2001), 14 pp.

%H 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.

%F S(m, n) = ((n-m+1)/(n+1))*Sum_{i=0..m-1} 2^(m-i-1)*binomial(n+1, i+1)*binomial(m-1, i).

%F Another version of triangle [1, 0, 0, 0, 0, 0, ...] DELTA [0, 1, 2, 1, 2, 1, 2, 1, 2, 1, ...] = 1, 1, 0, 1, 1, 0, 1, 2, 3, 0, 1, 3, 7, 11, 0, 1, 4, 12, 28, 45, 0, 1, ..., where DELTA is Deléham's operator defined in A084938.

%F G.f.: 2/(1 + uv - 2v + sqrt(1 - 6uv + u^2v^2)). - _Emeric Deutsch_, Dec 25 2003

%F Sum_{k = 0..n} T(n, k) = A006318(n), large Schroeder numbers. - _Philippe Deléham_, Jul 10 2004. (This is because T(n, k) = number of royal paths (A006318) of length n with exactly n-k Northeast steps lying on the line y=x. - _David Callan_, Aug 02 2004)

%F S(n,m) = ((n-m+1)/m)*Sum_{k=1..m} binomial(m,k)*binomial(n+k,k-1), n >= m > 1; S(n,0)=1; S(n,m)=0, n < m. See the corresponding formula for A104219. - _Wolfdieter Lang_, Mar 16 2009

%e Triangle starts:

%e [0] [1]

%e [1] [1, 1]

%e [2] [1, 2, 3]

%e [3] [1, 3, 7, 11]

%e [4] [1, 4, 12, 28, 45]

%e [5] [1, 5, 18, 52, 121, 197]

%e [6] [1, 6, 25, 84, 237, 550, 903]

%e [7] [1, 7, 33, 125, 403, 1119, 2591, 4279]

%e [8] [1, 8, 42, 176, 630, 1976, 5424, 12536, 20793]

%e [9] [1, 9, 52, 238, 930, 3206, 9860, 26832, 61921, 103049]

%t f[ x_, y_ ] := f[ x, y ] = Module[ {return}, If[ x == 0, return = 1, If[ y == x-1, return = 0, return = f[ x, y-1 ] + Sum[ f[ k, y ], {k, 0, x-1} ] ] ]; return ]; Do[ Print[ Table[ f[ k, j ], {k, 0, j} ] ], {j, 10, 0, -1} ]

%o (Sage)

%o def A011117_row(n):

%o @cached_function

%o def prec(n, k):

%o if k==n: return 1

%o if k==0: return 0

%o return prec(n-1,k-1)+sum(prec(n,k+i-1) for i in (2..n-k+1))

%o return [prec(n, n-k) for k in (0..n-1)]

%o for n in (1..9): print(A011117_row(n)) # _Peter Luschny_, Mar 16 2016

%Y Cf. A084938.

%Y Right-hand columns show convolutions of little Schroeder numbers with themselves: A001003, A010683, A010736, A010849.

%K nonn,tabl

%O 0,5

%A Robert Sulanke (sulanke(AT)diamond.idbsu.edu)

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 18:04 EDT 2024. Contains 371254 sequences. (Running on oeis4.)