login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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
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
F. Cai, Q.-H. Hou, Y. Sun, and A. L. B. Yang, Combinatorial identities related to 2x2 submatrices of recursive matrices, arXiv:1808.05736 [math.CO], 2018, Table 1.3.
Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.
Johann Cigler, Some elementary observations on Narayana polynomials and related topics, arXiv:1611.05252 [math.CO], 2016. See p. 7.
Sheng-Liang Yang, Yan-Ni Dong, and Tian-Xiao He, Some matrix identities on colored Motzkin paths, Discrete Mathematics 340.12 (2017): 3081-3091.
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).
Sum_{k>=0} T(m, k)*T(n, k)*2^k = T(m+n, 0) = A001003(m+n+1). - Philippe Deléham, Sep 14 2005
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
Sum_{k=0..n} T(n,k)*(2^(k + 1) - 1) = 6^n. - Philippe Deléham, Nov 29 2009
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)
def A110440_triangle(dim):
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
A110440_triangle(9) # Peter Luschny, Sep 20 2012
(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]
-- Reinhard Zumkeller, Nov 21 2013
CROSSREFS
Cf. A232246 (central terms), A001003 (left column), A065096 (2nd column?), A225887 (row sums?).
Sequence in context: A113955 A110165 A111965 * A135574 A008969 A199577
KEYWORD
easy,nice,nonn,tabl
AUTHOR
Asamoah Nkwanta (nkwanta(AT)jewel.morgan.edu), Aug 08 2005
STATUS
approved