A100100 Triangle T(n,k) = binomial(2*n-k-1, n-k) read by rows.

1, 1, 1, 3, 2, 1, 10, 6, 3, 1, 35, 20, 10, 4, 1, 126, 70, 35, 15, 5, 1, 462, 252, 126, 56, 21, 6, 1, 1716, 924, 462, 210, 84, 28, 7, 1, 6435, 3432, 1716, 792, 330, 120, 36, 8, 1, 24310, 12870, 6435, 3003, 1287, 495, 165, 45, 9, 1, 92378, 48620, 24310, 11440, 5005, 2002

Offset: 0

Author

Paul Barry, Nov 08 2004

Keywords

• easy
• nonn
• tabl

Comments

Sometimes called a Catalan triangle, although there are many other triangles that carry that name - see A009766, A008315, A028364, A033184, A053121, A059365, A062103.

Number of nodes of outdegree k in all ordered trees with n edges. Equivalently, number of ascents of length k in all Dyck paths of semilength n. Example: T(3,2) = 3 because the Dyck paths of semilength 3 are UDUDUD, UD(UU)DD, (UU)DDUD, (UU)DUDD and UUUDDD, where U = (1,1), D = (1,-1), the ascents of length 2 being shown between parentheses. - Emeric Deutsch, Nov 19 2006

Riordan array (f(x), x*g(x)) where f(x) is the g.f. of A088218 and g(x) is the g.f. of A000108. - Philippe Deléham, Jan 23 2010

T(n,k) is the number of nonnegative paths of upsteps U = (1,1) and downsteps D = (1,-1) of length 2*n with k returns to ground level, the horizontal line through the initial vertex. Example: T(2,1) = 2 counts UDUU, UUDD. Also, T(n,k) = number of these paths whose last descent has length k, that is, k downsteps follow the last upstep. Example: T(2,1) = 2 counts UUUD, UDUD. - David Callan, Nov 21 2011

Belongs to the hitting-time subgroup of the Riordan group. Multiplying this triangle by the square Pascal matrix gives A092392 read as a square array. See the example below. - Peter Bala, Nov 03 2015

Examples

			From _Paul Barry_, Mar 15 2010: (Start)
Triangle begins in row n=0 with columns 0<=k<=n as:
    1;
    1,   1;
    3,   2,   1;
   10,   6,   3,  1;
   35,  20,  10,  4,  1;
  126,  70,  35, 15,  5, 1;
  462, 252, 126, 56, 21, 6, 1;
Production matrix begins
  1, 1;
  2, 1, 1;
  3, 1, 1, 1;
  4, 1, 1, 1, 1;
  5, 1, 1, 1, 1, 1;
  6, 1, 1, 1, 1, 1, 1;
  7, 1, 1, 1, 1, 1, 1, 1;
(End)
A092392 as a square array = A100100 * square Pascal matrix:
/1   1  1  1 ...\   / 1          \/1 1  1  1 ...\
|2   3  4  5 ...|   | 1 1        ||1 2  3  4 ...|
|6  10 15 21 ...| = | 3 2 1      ||1 3  6 10 ...|
|20 35 56 84 ...|   |10 6 3 1    ||1 4 10 20 ...|
|70 ...         |   |35 ...      ||1 ...        |
- _Peter Bala_, Nov 03 2015
		

Links

• Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
• Peter Bala, Notes on logarithmic differentiation, the binomial transform and series reversion
• Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
• Gi-Sang Cheon, Hana Kim, and Louis W. Shapiro, An algebraic structure for Faber polynomials, Lin. Alg. Applic. 433 (2010) 1170-1179.
• Tian-Xiao He and Renzo Sprugnoli, Sequence characterization of Riordan arrays, Discrete Math. 309 (2009), no. 12, 3962-3974.

Crossrefs

Row sums are A000984. Equivalent to A092392, to which A088218 has been added as a first column. Columns include A088218, A000984, A001700, A001791, A002054, A002694. Diagonal sums are A100217. Matrix inverse is A100218.

Cf. A059481 (mirrored). Cf. A033184, A094527, A113955.

Programs

Haskell

a100100 n k = a100100_tabl !! n !! n
a100100_row n = a100100_tabl !! n
a100100_tabl = [1] : f a092392_tabl where
   f (us : wss'@(vs : wss)) = (vs !! 1 : us) : f wss'
-- Reinhard Zumkeller, Jan 15 2014

Magma

/* As triangle */ [[Binomial(2*n - k - 1, n - k): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Nov 21 2018

Maple

A100100 := proc(n,k)
    binomial(2*n-k-1,n-1) ;
end proc:
seq(seq(A100100(n,k),k=0..n),n=0..10) ; # R. J. Mathar, Feb 06 2015

Mathematica

Flatten[Table[Binomial[2 n - k - 1, n - k], {n, 0, 11}, {k, 0, n}]] (* Vincenzo Librandi, Nov 21 2018 *)

PARI

T(n,k)=binomial(2*n-k-1,n-k) \\ Charles R Greathouse IV, Jan 16 2012

Formula

From Peter Bala, Sep 06 2015: (Start)

Matrix product A094527 * P^(-1) = A113955 * P^(-2), where P denotes Pascal's triangle A007318.

Essentially, the logarithmic derivative of A033184. (End)

Let column(k) = [T(n, k), n >= k], then the generating function for column(k) is (2/(sqrt(1-4*x)+1))^(k-1)/sqrt(1-4*x). - Peter Luschny, Mar 19 2021

O.g.f. row polynomials R(n, x) := Sum_{k=0..n} T(n, k)*x^k, i.e. o.g.f. of the triangle, G(z,x) = 1/((2 - c(z))*(1 - x*z*c(z))), with c the o.g.f. of A000108 (Catalan). See the Riordan coomment by Philippe Deléham above. - Wolfdieter Lang, Apr 06 2021