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

%I #86 Sep 08 2022 08:45:15

%S 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,

%T 6,1,1716,924,462,210,84,28,7,1,6435,3432,1716,792,330,120,36,8,1,

%U 24310,12870,6435,3003,1287,495,165,45,9,1,92378,48620,24310,11440,5005,2002

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

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

%C 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

%C 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

%C 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

%C 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

%H Reinhard Zumkeller, <a href="/A100100/b100100.txt">Rows n = 0..125 of triangle, flattened</a>

%H Peter Bala, <a href="/A100100/a100100_1.pdf">Notes on logarithmic differentiation, the binomial transform and series reversion</a>

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Barry/barry321.html">Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices</a>, Journal of Integer Sequences, 19, 2016, #16.3.5.

%H Gi-Sang Cheon, Hana Kim, and Louis W. Shapiro, <a href="https://doi.org/10.1016/j.laa.2010.04.044">An algebraic structure for Faber polynomials</a>, Lin. Alg. Applic. 433 (2010) 1170-1179.

%H Tian-Xiao He and Renzo Sprugnoli, <a href="http://dx.doi.org/10.1016/j.disc.2008.11.021">Sequence characterization of Riordan arrays</a>, Discrete Math. 309 (2009), no. 12, 3962-3974.

%F From _Peter Bala_, Sep 06 2015: (Start)

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

%F Essentially, the logarithmic derivative of A033184. (End)

%F 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

%F 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

%e From _Paul Barry_, Mar 15 2010: (Start)

%e Triangle begins in row n=0 with columns 0<=k<=n as:

%e 1;

%e 1, 1;

%e 3, 2, 1;

%e 10, 6, 3, 1;

%e 35, 20, 10, 4, 1;

%e 126, 70, 35, 15, 5, 1;

%e 462, 252, 126, 56, 21, 6, 1;

%e Production matrix begins

%e 1, 1;

%e 2, 1, 1;

%e 3, 1, 1, 1;

%e 4, 1, 1, 1, 1;

%e 5, 1, 1, 1, 1, 1;

%e 6, 1, 1, 1, 1, 1, 1;

%e 7, 1, 1, 1, 1, 1, 1, 1;

%e (End)

%e A092392 as a square array = A100100 * square Pascal matrix:

%e /1 1 1 1 ...\ / 1 \/1 1 1 1 ...\

%e |2 3 4 5 ...| | 1 1 ||1 2 3 4 ...|

%e |6 10 15 21 ...| = | 3 2 1 ||1 3 6 10 ...|

%e |20 35 56 84 ...| |10 6 3 1 ||1 4 10 20 ...|

%e |70 ... | |35 ... ||1 ... |

%e - _Peter Bala_, Nov 03 2015

%p A100100 := proc(n,k)

%p binomial(2*n-k-1,n-1) ;

%p end proc:

%p seq(seq(A100100(n,k),k=0..n),n=0..10) ; # _R. J. Mathar_, Feb 06 2015

%t Flatten[Table[Binomial[2 n - k - 1, n - k], {n, 0, 11}, {k, 0, n}]] (* _Vincenzo Librandi_, Nov 21 2018 *)

%o (PARI) T(n,k)=binomial(2*n-k-1,n-k) \\ _Charles R Greathouse IV_, Jan 16 2012

%o (Haskell)

%o a100100 n k = a100100_tabl !! n !! n

%o a100100_row n = a100100_tabl !! n

%o a100100_tabl = [1] : f a092392_tabl where

%o f (us : wss'@(vs : wss)) = (vs !! 1 : us) : f wss'

%o -- _Reinhard Zumkeller_, Jan 15 2014

%o (Magma) /* As triangle */ [[Binomial(2*n - k - 1, n - k): k in [0..n]]: n in [0.. 15]]; // _Vincenzo Librandi_, Nov 21 2018

%Y 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.

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

%K easy,nonn,tabl

%O 0,4

%A _Paul Barry_, Nov 08 2004