OFFSET
0,4
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
LINKS
Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
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.
FORMULA
From Peter Bala, Sep 06 2015: (Start)
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
EXAMPLE
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)
/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
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 *)
PROG
(PARI) T(n, k)=binomial(2*n-k-1, n-k) \\ Charles R Greathouse IV, Jan 16 2012
(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
CROSSREFS
KEYWORD
AUTHOR
Paul Barry, Nov 08 2004
STATUS
approved