|
|
A110440
|
|
Triangular array formed by the little Schröder numbers s(n,k).
|
|
6
|
|
|
1, 3, 1, 11, 6, 1, 45, 31, 9, 1, 197, 156, 60, 12, 1, 903, 785, 360, 98, 15, 1, 4279, 3978, 2061, 684, 145, 18, 1, 20793, 20335, 11529, 4403, 1155, 201, 21, 1, 103049, 104856, 63728, 27048, 8270, 1800, 266, 24, 1, 518859, 545073, 350136, 161412, 55458, 14202
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
s(n,k) is the number of unit step restricted paths (i.e., they never go below the x-axis) from the origin (0,0) to (n-1,k-1) using up step U(1,1), three types of level steps L(1,0), L'(1,0), L"(1,0) and two types of down steps D(1,-1), D'(1,-1). s(0,0)=1 and the leftmost column s(n,0) is A001003.
The sequence factors A038255 into a product of Riordan arrays.
|
|
LINKS
|
|
|
FORMULA
|
s(n+1,0) = 3s(n,0) + 2s(n,1) and for k > 0: s(n+1,k) = s(n,k-1) + 3s(n,k) + 2s(n,k+1). [Typo fixed by Reinhard Zumkeller, Nov 21 2013]
Riordan array ((1 - 3z - sqrt(1-6z+z^2))/4z*z, (1 - 3z - sqrt(1-6z+z^2))/4z).
G.f.: 2/( 1 - x*L -2*x*y*U + sqrt( (1 - x*L)^2 - 4*x^2*D*U ) ) where L=3, U = 1, D = 2. - Michael Somos, Mar 31 2007
T(n,k) = Sum_{i=0..k + 1} i*(-1)^(k-i+1)*C(k+1,i)*Sum_{j=0..n+1} (-1)^j*2^(n+1-j)*(2*n+i-j+1)!/((n+i-j+1)!*j!*(n-j+1)!))). - Vladimir Kruchinin, Oct 17 2011
T(n,k) = (k+1)/(n+1)*Sum_{j=ceiling((n+k+2)/2)..n + 1} C(j,2*j-n-k-2)*3^(2*j-n-k- 2)*2^(n+1-j)*C(n+1,j)). - Vladimir Kruchinin, Jan 28 2013
T(n,k) = ((k+1)/(n+1))*Sum_{m=0..n} 2^(n-m)*C(n+1,m+1)*C(n+1,m-k). - Vladimir Kruchinin, Jan 09 2022
|
|
EXAMPLE
|
Triangle starts:
[0] 1;
[1] 3, 1;
[2] 11, 6, 1;
[3] 45, 31, 9, 1;
[4] 197, 156, 60, 12, 1;
[5] 903, 785, 360, 98, 15, 1;
[6] 4279, 3978, 2061, 684, 145, 18, 1;
[7] 20793, 20335, 11529, 4403, 1155, 201, 21, 1;
[8] 103049, 104856, 63728, 27048, 8270, 1800, 266, 24, 1;
[9] 518859, 545073, 350136, 161412, 55458, 14202, 2646, 340, 27, 1;
|
|
MAPLE
|
T := (n, k) -> ((k + 1)/(n + 1))*add(2^(n - m)*binomial(n+1, m+1)*binomial(n+1, m-k), m = 0..n): seq(seq(T(n, k), k = 0..n), n = 0..9); # Peter Luschny, Jan 09 2022
|
|
MATHEMATICA
|
nmax = 9; t[n_, k_] := Sum[(i*(-1)^(k-i+1)*Binomial[k+1, i]*Sum[(-1)^j*2^(n+1-j)*(2n+i-j+1)! / ((n+i-j+1)!*j!*(n-j+1)!), {j, 0, n+1}]), {i, 0, k+1}]; Flatten[ Table[ t[n, k], {n, 0, nmax}, {k, 0, n}]] (* Jean-François Alcover, Nov 14 2011, after Vladimir Kruchinin *)
|
|
PROG
|
(PARI) {T(n, k)= if(n<0|| k>n, 0, polcoeff(polcoeff( 2/(1 -3*x -2*x*y +sqrt( 1 -6*x +x^2 +x*O(x^n)) ), n), k))} \\ Michael Somos, Mar 31 2007
(Maxima)
T(n, k):=sum((i*(-1)^(k-i+1)*binomial(k+1, i)*sum((-1)^j*2^(n+1-j)*(2*n+i-j+1)!/((n+i-j+1)!*j!*(n-j+1)!), j, 0, n+1)), i, 0, k+1); /* Vladimir Kruchinin, Oct 17 2011 */
(Sage)
T = matrix(ZZ, dim, dim)
for n in range(dim): T[n, n] = 1
for n in (1..dim-1):
for k in (0..n-1):
T[n, k] = T[n-1, k-1]+3*T[n-1, k]+2*T[n-1, k+1]
return T
(Maxima) T(n, k):=((k+1)/(n+1)*sum(binomial(j, -n-k+2*j-2)*3^(-n-k+2*j-2)*2^(n+1-j)*binomial(n+1, j), j, ceiling((n+k+2)/2), n+1)); \\ Vladimir Kruchinin, Jan 28 2013
(Haskell)
a110440 n k = a110440_tabl !! n !! k
a110440_row n = a110440_tabl !! n
a110440_tabl = iterate (\xs ->
zipWith (+) ([0] ++ xs) $
zipWith (+) (map (* 3) (xs ++ [0]))
(map (* 2) (tail xs ++ [0, 0]))) [1]
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
Asamoah Nkwanta (nkwanta(AT)jewel.morgan.edu), Aug 08 2005
|
|
STATUS
|
approved
|
|
|
|