A050144 T(n,k) = M(2n-1,n-1,k-1), 0 <= k <= n, n >= 0, where M(p,q,r) is the number of upright paths from (0,0) to (p,p-q) that meet the line y = x+r and do not rise above it.

0, 1, 0, 1, 1, 1, 2, 3, 4, 1, 5, 9, 14, 6, 1, 14, 28, 48, 27, 8, 1, 42, 90, 165, 110, 44, 10, 1, 132, 297, 572, 429, 208, 65, 12, 1, 429, 1001, 2002, 1638, 910, 350, 90, 14, 1, 1430, 3432, 7072, 6188, 3808, 1700, 544, 119, 16, 1

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• tabl

Comments

Let V=(e(1),...,e(n)) consist of q 1's and p-q 0's; let V(h)=(e(1),...,e(h)) and m(h)=(#1's in V(h))-(#0's in V(h)) for h=1,...,n. Then M(p,q,r)=number of V having r=max{m(h)}.

The interpretation of T(n,k) as RU walks in terms of M(.,.,.) in the NAME is erroneous. There seems to be a pattern along subdiagonals:

M(3,1,1) = 4 = T(3,2); M(3,1,2) = 1 = T(4,4); M(5,2,1) = 20 = T(5,3); M(5,2,2) = 7 = T(6,5); M(5,2,3) = 1 = T(7,7); M(7,3,0) = 165 = T(6,2); M(7,3,1) = 110 = T(7,4); M(7,3,2) = 44 = T(8,6); M(7,3,3) = 10 = T(9,8); M(7,3,4) = 1 = T(10,10); M(9,4,0) = 1001 = T(8,3); M(9,4,1) = 637 = T(9,5); M(9,4,2) = 273 = T(10,7); M(9,4,3) = 77 = T(11,9); M(9,4,4) = 13 = T(12,11); M(9,4,5) = 1 = T(13,13); M(11,5,0) = 6188 = T(10,4); M(11,5,1) = 3808 = T(11,6); M(11,5,2) = 1700 = T(12,8); M(11,5,3) = 544 = T(13,...); M(11,5,4) = 119; M(11,5,5) = 16; M(11,5,6) = 1; M(13,6,0) = 38760 = T(12,5); M(13,6,1) = 23256 = T(13,7); M(13,6,2) = 10659 = T(14,9); - R. J. Mathar, Jul 31 2024

Examples

			Triangle begins:
     0
     1    0
     1    1    1
     2    3    4    1
     5    9   14    6    1
    14   28   48   27    8    1
    42   90  165  110   44   10    1
   132  297  572  429  208   65   12    1
   429 1001 2002 1638  910  350   90   14    1
  1430 3432 7072 6188 3808 1700  544  119   16    1
		

References

• Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.

Links

• Emeric Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
• Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids, English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see p. 29.
• R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.

Crossrefs

{M(2n, 0, k)} is given by A039599. {M(2n+1, n+1, k+1)} is given by A039598.

Cf. A033184, A050153, A000108 (column 0), A000245 (column 1), A002057 (column 2), A000344 (column 3), A003517 (column 4), A000588 (column 5), A003518 (column 6), A001392 (column 7), A003519 (column 8), A000589 (column 9), A090749 (column 10).

Programs

Maple

A050144 := proc(n,k)
    if n < k then
        0;
    elif k =0 then
        if n =0 then
            0 ;
        else
            A000108(n-1) ;
        end if;
    elif k = 1 then
        add( procname(n-1-j,0)*A000108(j+1),j=0..n-1) ;
    elif k = 2 then
        add( procname(n-j,1)*A000108(j),j=0..n) ;
    else
        add( procname(n-1-j,k-1)*A000108(j),j=0..n-1) ;
    end if;
end proc:
seq(seq( A050144(n,k),k=0..n),n=0..12) ; # R. J. Mathar, Jul 30 2024

Mathematica

c[n_] := Binomial[2 n, n]/(n + 1);
t[n_, k_] := Which[k == 0, c[n - 1],
  k == 1, Sum[t[n - 1 - j, 0]*c[j + 1], {j, 0, n - 2}],
  k == 2, Sum[t[n - j, 1]*c[j], {j, 0, n - 1}],
  k > 2, Sum[t[n - 1 - j, k - 1] c[j + 1], {j, 0, n - 2}]]
t[0, 0] = 0;
Column[Table[t[n, k], {n, 0, 10}, {k, 0, n}]]
(* Clark Kimberling, Jul 30 2024 *)

Formula

For n > 0: Sum_{k>=0} T(n, k) = binomial(2*n-1, n); see A001700. - Philippe Deléham, Feb 13 2004 [Erroneous sum-formula deleted. R. J. Mathar, Jul 31 2024]

T(n, k)=0 if n < k; T(0, 0)=0, T(n, 0) = A000108(n-1) for n > 0; T(n, 1) = Sum_{j>=0} T(n-1-j, 0)*A000108(j+1); T(n, 2) = Sum_{j>=0} T(n-j, 1)*A000108(j); for k > 2, T(n, k) = Sum_{j>=0} T(n-1-j, k-1)*A000108(j+1). - Philippe Deléham, Feb 13 2004 [Corrected by Sean A. Irvine, Aug 08 2021]

For the column k=0, g.f.: x*C(x); for the column k=1, g.f.: x*C(x)*(C(x)-1); for the column k, k > 1, g.f.: x*C(x)^2*(C(x)-1)^(k-1); where C(x) = Sum_{n>=0} A000108(n)*x^n is g.f. for Catalan numbers, A000108. - Philippe Deléham, Feb 13 2004

T(n,0) = A033184(n,2). T(n,1) = A033184(n+1,3), T(n,k) = A033184(n+2,k+2) for k>=2. - R. J. Mathar, Jul 31 2024