|
|
A100100
|
|
Triangle T(n,k) = binomial(2*n-k-1, n-k) read by rows.
|
|
22
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
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
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
|
|
|
FORMULA
|
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
|
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 ... |
|
|
MAPLE
|
binomial(2*n-k-1, n-1) ;
end proc:
|
|
MATHEMATICA
|
Flatten[Table[Binomial[2 n - k - 1, n - k], {n, 0, 11}, {k, 0, n}]] (* Vincenzo Librandi, Nov 21 2018 *)
|
|
PROG
|
(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'
(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
|
|
|
STATUS
|
approved
|
|
|
|