cp's OEIS Frontend

A110440 Triangular array formed by the little Schröder numbers s(n,k).

%I A110440 #83 Jan 20 2025 20:50:45
%S A110440 1,3,1,11,6,1,45,31,9,1,197,156,60,12,1,903,785,360,98,15,1,4279,3978,
%T A110440 2061,684,145,18,1,20793,20335,11529,4403,1155,201,21,1,103049,104856,
%U A110440 63728,27048,8270,1800,266,24,1,518859,545073,350136,161412,55458,14202
%N A110440 Triangular array formed by the little Schröder numbers s(n,k).
%C A110440 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.
%C A110440 The sequence factors A038255 into a product of Riordan arrays.
%H A110440 Reinhard Zumkeller, <a href="/A110440/b110440.txt">Rows n = 0..125 of triangle, flattened</a>
%H A110440 F. Cai, Q.-H. Hou, Y. Sun, and A. L. B. Yang, <a href="http://arxiv.org/abs/1808.05736">Combinatorial identities related to 2x2 submatrices of recursive matrices</a>, arXiv:1808.05736 [math.CO], 2018, Table 1.3.
%H A110440 Naiomi T. Cameron and Asamoah Nkwanta, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Cameron/cameron46.html">On Some (Pseudo) Involutions in the Riordan Group</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.
%H A110440 Johann Cigler, <a href="https://arxiv.org/abs/1611.05252">Some elementary observations on Narayana polynomials and related topics</a>, arXiv:1611.05252 [math.CO], 2016. See p. 7.
%H A110440 Sheng-Liang Yang, Yan-Ni Dong, and Tian-Xiao He, <a href="http://dx.doi.org/10.1016/j.disc.2017.07.006">Some matrix identities on colored Motzkin paths</a>, Discrete Mathematics 340.12 (2017): 3081-3091.
%F A110440 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]
%F A110440 Riordan array ((1 - 3z - sqrt(1-6z+z^2))/4z*z, (1 - 3z - sqrt(1-6z+z^2))/4z).
%F A110440 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
%F A110440 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
%F A110440 Sum_{k=0..n} T(n,k)*(2^(k + 1) - 1) = 6^n. - _Philippe Deléham_, Nov 29 2009
%F A110440 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
%F A110440 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
%F A110440 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
%e A110440 Triangle starts:
%e A110440 [0]      1;
%e A110440 [1]      3,      1;
%e A110440 [2]     11,      6,      1;
%e A110440 [3]     45,     31,      9,      1;
%e A110440 [4]    197,    156,     60,     12,     1;
%e A110440 [5]    903,    785,    360,     98,    15,     1;
%e A110440 [6]   4279,   3978,   2061,    684,   145,    18,    1;
%e A110440 [7]  20793,  20335,  11529,   4403,  1155,   201,   21,   1;
%e A110440 [8] 103049, 104856,  63728,  27048,  8270,  1800,  266,  24,  1;
%e A110440 [9] 518859, 545073, 350136, 161412, 55458, 14202, 2646, 340, 27, 1;
%p A110440 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
%t A110440 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_ *)
%o A110440 (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
%o A110440 (Maxima)
%o A110440 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 */
%o A110440 (Sage)
%o A110440 def A110440_triangle(dim):
%o A110440     T = matrix(ZZ,dim,dim)
%o A110440     for n in range(dim): T[n,n] = 1
%o A110440     for n in (1..dim-1):
%o A110440         for k in (0..n-1):
%o A110440             T[n,k] = T[n-1,k-1]+3*T[n-1,k]+2*T[n-1,k+1]
%o A110440     return T
%o A110440 A110440_triangle(9) # _Peter Luschny_, Sep 20 2012
%o A110440 (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 */
%o A110440 (Haskell)
%o A110440 a110440 n k = a110440_tabl !! n !! k
%o A110440 a110440_row n = a110440_tabl !! n
%o A110440 a110440_tabl = iterate (\xs ->
%o A110440    zipWith (+) ([0] ++ xs) $
%o A110440    zipWith (+) (map (* 3) (xs ++ [0]))
%o A110440                (map (* 2) (tail xs ++ [0,0]))) [1]
%o A110440 -- _Reinhard Zumkeller_, Nov 21 2013
%Y A110440 Cf. A232246 (central terms), A001003 (left column), A065096 (2nd column?), A225887 (row sums?).
%K A110440 easy,nice,nonn,tabl
%O A110440 0,2
%A A110440 Asamoah Nkwanta (nkwanta(AT)jewel.morgan.edu), Aug 08 2005